IDEAS home Printed from https://ideas.repec.org/a/eee/apmaco/v389y2021ics0096300320305312.html
   My bibliography  Save this article

Improving the sampling process in the interval Branch-and-Prune algorithm for the discretizable molecular distance geometry problem

Author

Listed:
  • Lavor, Carlile
  • Souza, Michael
  • Carvalho, Luiz M.
  • Gonçalves, Douglas S.
  • Mucherino, Antonio

Abstract

Protein structure determination using Nuclear Magnetic Resonance (NMR) experiments is one of the most important applications of Distance Geometry, called the Molecular Distance Geometry Problem (MDGP). Using special atomic orders on the protein molecule, the MDGP can be solved iteratively using a combinatorial method, called Branch-and-Prune (BP). In order to deal with uncertainties of NMR data, there is an extension of the BP algorithm, called interval BP, where the idea is to sample values from the interval distances associated to such uncertainties. We propose a method to improve this sampling process, by reducing the interval of uncertain distances before taking the samples. All the mathematical details necessary to understand the proposal and its implementation are provided, along with some computational experiments that indicate the proposed strategy improves the interval BP algorithm.

Suggested Citation

  • 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).
    • Handle: RePEc:eee:apmaco:v:389:y:2021:i:c:s0096300320305312
    DOI: 10.1016/j.amc.2020.125586
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0096300320305312
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.amc.2020.125586?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. 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.
    2. 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.
    3. Antonio Mucherino & Carlile Lavor & Leo Liberti & Nelson Maculan, 2012. "The Discretizable Molecular Distance Geometry Problem," Post-Print hal-00756940, HAL.
    4. 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.
    5. 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.
    6. 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.
    7. Antonio Mucherino & Carlile Lavor & Leo Liberti, 2012. "The Discretizable Distance Geometry Problem," Post-Print hal-00756943, HAL.
    8. 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.
    9. 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)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. 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.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. Yves Crama & Michel Grabisch & Silvano Martello, 2022. "Preface," Annals of Operations Research, Springer, vol. 314(1), pages 1-3, July.
    13. Yves Crama & Michel Grabisch & Silvano Martello, 2022. "Sixty-one surveys in operations research," Annals of Operations Research, Springer, vol. 314(1), pages 5-13, July.
    14. Moira MacNeil & Merve Bodur, 2022. "Integer Programming, Constraint Programming, and Hybrid Decomposition Approaches to Discretizable Distance Geometry Problems," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 297-314, January.
    15. Yves Crama & Michel Grabisch & Silvano Martello, 2018. "Sweet sixteen," 4OR, Springer, vol. 16(1), pages 1-13, March.
    16. Yves Crama & Michel Grabisch & Silvano Martello, 2021. "4OR comes of age," 4OR, Springer, vol. 19(1), pages 1-13, March.
    17. Carlile Lavor, 2020. "Comments 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 340-345, July.

    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:eee:apmaco:v:389:y:2021:i:c:s0096300320305312. 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: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    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.