The Discretizable Molecular Distance Geometry Problem

Antonio Mucherino (), Carlile Lavor, Leo Liberti () and Nelson Maculan
Additional contact information
Antonio Mucherino: GenScale - Scalable, Optimized and Parallel Algorithms for Genomics - Centre Inria de l'Université de Rennes - 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 - IP Paris - Institut Polytechnique de Paris - 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]

Post-Print from HAL

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.

Date: 2012
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Published in Computational Optimization and Applications, 2012, 24th International Federation for Information Processing-7th Technical Committee Conference on System Modeling and Optimization Jul 2009 Buenos Aires, 52, pp.115-146. ⟨10.1007/s10589-011-9402-6⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-00756940

DOI: 10.1007/s10589-011-9402-6

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().