IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v87y2024i2d10.1007_s10589-023-00526-8.html
   My bibliography  Save this article

A numerical-and-computational study on the impact of using quaternions in the branch-and-prune algorithm for exact discretizable distance geometry problems

Author

Listed:
  • Felipe Fidalgo

    (Universidade Federal de Santa Catarina)

  • Emerson Castelani

    (Universidade Estadual de Maringá)

  • Guilherme Philippi

    (Universidade Federal de Santa Catarina)

Abstract

Distance geometry is a branch of Mathematics which studies geometric relations having distances as primitive elements. Its fundamental problem, the distance geometry problem, consists in determining point positions in $$\mathbb {R}^K$$ R K such that their Euclidean distances match those in a given list of inter-point distances. Such problem can be cast as a global optimization problem which is often tackled with continuous optimization techniques. If $$K=3$$ K = 3 , it is called molecular DGP (MDGP). Under assumptions on the available distances in this list, the search space for the MDGP can be discretized so that it is able to be designed as a binary tree, giving birth to the discretized MDGP. The main method to solve it is the Branch-and-Prune Algorithm, a recursive and combinatorial tool that explores such tree in a depth-first search and whose classical formulation is based in a homogeneous matrix product that encodes one translation and two rotations. This paper presents a numerical study on the theoretical computational effort to do that task together with a quaternionic proposal as an alternative for the formulation of BP and the respective analogous numerical study, for comparing with the matrix one. Additionally, best-and-worst-case analyzes for both approaches are displayed. Finally, in order to validate the new formulation as having better computational performance for BP, a set of computational experiments are shown using artificial Lavor instances and pre-processed proteic examples which have been generated from structures withdrawn from the worldwide protein data bank.

Suggested Citation

  • Felipe Fidalgo & Emerson Castelani & Guilherme Philippi, 2024. "A numerical-and-computational study on the impact of using quaternions in the branch-and-prune algorithm for exact discretizable distance geometry problems," Computational Optimization and Applications, Springer, vol. 87(2), pages 501-530, March.
  • Handle: RePEc:spr:coopap:v:87:y:2024:i:2:d:10.1007_s10589-023-00526-8
    DOI: 10.1007/s10589-023-00526-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-023-00526-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10589-023-00526-8?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Leo Liberti, 2020. "Rejoinder on: Distance geometry and data science," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 350-357, July.
    2. Carlile Lavor & Leo Liberti & Nelson Maculan & Antonio Mucherino, 2012. "The discretizable molecular distance geometry problem," Computational Optimization and Applications, Springer, vol. 52(1), pages 115-146, May.
    3. Carlile Lavor & Leo Liberti & Antonio Mucherino, 2013. "The interval Branch-and-Prune algorithm for the discretizable molecular distance geometry problem with inexact distances," Journal of Global Optimization, Springer, vol. 56(3), pages 855-871, July.
    4. Leo Liberti, 2020. "Distance geometry and data science," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 271-339, July.
    5. Lavor, Carlile & Liberti, Leo & Maculan, Nelson & Mucherino, Antonio, 2012. "Recent advances on the Discretizable Molecular Distance Geometry Problem," European Journal of Operational Research, Elsevier, vol. 219(3), pages 698-706.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Maurizio Bruglieri & Roberto Cordone & Leo Liberti, 2022. "Maximum feasible subsystems of distance geometry constraints," Journal of Global Optimization, Springer, vol. 83(1), pages 29-47, May.
    2. Lavor, Carlile & Souza, Michael & Carvalho, Luiz M. & Gonçalves, Douglas S. & Mucherino, Antonio, 2021. "Improving the sampling process in the interval Branch-and-Prune algorithm for the discretizable molecular distance geometry problem," Applied Mathematics and Computation, Elsevier, vol. 389(C).
    3. Virginia Costa & Antonio Mucherino & Carlile Lavor & Andrea Cassioli & Luiz Carvalho & Nelson Maculan, 2014. "Discretization orders for protein side chains," Journal of Global Optimization, Springer, vol. 60(2), pages 333-349, October.
    4. Farid Alizadeh & Douglas Gonçalves & Nathan Krislock & Leo Liberti, 2018. "Preface: Special issue dedicated to Distance Geometry," Journal of Global Optimization, Springer, vol. 72(1), pages 1-4, September.
    5. Felipe Fidalgo & Douglas S. Gonçalves & Carlile Lavor & Leo Liberti & Antonio Mucherino, 2018. "A symmetry-based splitting strategy for discretizable distance geometry problems," Journal of Global Optimization, Springer, vol. 71(4), pages 717-733, August.
    6. Simon J. L. Billinge & Phillip M. Duxbury & Douglas S. Gonçalves & Carlile Lavor & Antonio Mucherino, 2018. "Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures," Annals of Operations Research, Springer, vol. 271(1), pages 161-203, December.
    7. Douglas S. Gonçalves & Antonio Mucherino & Carlile Lavor & Leo Liberti, 2017. "Recent advances on the interval distance geometry problem," Journal of Global Optimization, Springer, vol. 69(3), pages 525-545, November.
    8. Leo Liberti, 2020. "Distance geometry and data science," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 271-339, July.
    9. Martello, Silvano & Pinto Paixão, José M., 2012. "A look at the past and present of optimization – An editorial," European Journal of Operational Research, Elsevier, vol. 219(3), pages 638-640.
    10. Emilio Carrizosa & Cristina Molero-Río & Dolores Romero Morales, 2021. "Mathematical optimization in classification and regression trees," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 5-33, April.
    11. Simon J. L. Billinge & Phillip M. Duxbury & Douglas S. Gonçalves & Carlile Lavor & Antonio Mucherino, 2016. "Assigned and unassigned distance geometry: applications to biological molecules and nanostructures," 4OR, Springer, vol. 14(4), pages 337-376, December.
    12. Phil Duxbury & Carlile Lavor & Leo Liberti & Luiz Leduino Salles-Neto, 2022. "Unassigned distance geometry and molecular conformation problems," Journal of Global Optimization, Springer, vol. 83(1), pages 73-82, May.
    13. Emilio Carrizosa & Dolores Romero Morales, 2024. "Guest editorial to the Special Issue on Machine Learning and Mathematical Optimization in TOP-Transactions in Operations Research," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 32(3), pages 351-353, October.
    14. Bradley Worley & Florent Delhommel & Florence Cordier & Thérèse E. Malliavin & Benjamin Bardiaux & Nicolas Wolff & Michael Nilges & Carlile Lavor & Leo Liberti, 2018. "Tuning interval Branch-and-Prune for protein structure determination," Journal of Global Optimization, Springer, vol. 72(1), pages 109-127, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:87:y:2024:i:2:d:10.1007_s10589-023-00526-8. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.