IDEAS home Printed from https://ideas.repec.org/p/hal/journl/hal-00756940.html
   My bibliography  Save this paper

The Discretizable Molecular Distance Geometry Problem

Author

Listed:
  • Antonio Mucherino

    (GenScale - Scalable, Optimized and Parallel Algorithms for Genomics - Inria Rennes – Bretagne Atlantique - Inria - Institut National de Recherche en Informatique et en Automatique - IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE - IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires - UR - Université de Rennes - INSA Rennes - Institut National des Sciences Appliquées - Rennes - INSA - Institut National des Sciences Appliquées - UBS - Université de Bretagne Sud - ENS Rennes - École normale supérieure - Rennes - Inria - Institut National de Recherche en Informatique et en Automatique - Télécom Bretagne - CentraleSupélec - CNRS - Centre National de la Recherche Scientifique, IMECC - Instituto de Matemática, Estatística e Computação Científica [Brésil] - UNICAMP - Universidade Estadual de Campinas = University of Campinas)

  • Carlile Lavor

    (IMECC - Instituto de Matemática, Estatística e Computação Científica [Brésil] - UNICAMP - Universidade Estadual de Campinas = University of Campinas)

  • Leo Liberti

    (LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau] - X - École polytechnique - CNRS - Centre National de la Recherche Scientifique)

  • Nelson Maculan

    (COPPE-UFRJ - Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia - UFRJ - Universidade Federal do Rio de Janeiro [Brasil] = Federal University of Rio de Janeiro [Brazil] = Université fédérale de Rio de Janeiro [Brésil])

Abstract

Given a simple weighted undirected graph G=(V,E,d), the Molecular Distance Geometry Problem (MDGP) consists in finding an embedding x such that ||x_u - x_v|| = d(u,v) for each (u,v) in E. We show that under a few assumptions usually satisfied in proteins, the MDGP can be formulated as a search in a discrete space. We call this MDGP subclass the Discretizable MDGP (DMDGP). We show that the DMDGP is NP-hard and we propose a solution algorithm called Branch-and-Prune (BP). The BP algorithm performs remarkably well in practice in terms of speed and solution accuracy, and can be easily modified to find all incongruent solutions to a given DMDGP instance. We show computational results on several artificial and real-life instances.

Suggested Citation

  • Antonio Mucherino & Carlile Lavor & Leo Liberti & Nelson Maculan, 2012. "The Discretizable Molecular Distance Geometry Problem," Post-Print hal-00756940, HAL.
    • Handle: RePEc:hal:journl:hal-00756940
    DOI: 10.1007/s10589-011-9402-6
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a search for a similarly titled item that would be available.

    Citations

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


    Cited by:

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

    More about this item

    Statistics

    Access and download statistics

    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:hal:journl:hal-00756940. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    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.