The Discretizable Distance Geometry Problem

Antonio Mucherino (), Carlile Lavor and Leo Liberti ()
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
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

Post-Print from HAL

Abstract: We introduce the Discretizable Distance Geometry Problem in R^3 (DDGP3), which consists in a subclass of instances of the Distance Geometry Problem for which an embedding in R^3 can be found by means of a discrete search. We show that the DDGP3 is a generalization of the Discretizable Molecular Distance Geometry Problem (DMDGP), and we discuss the main differences between the two problems. We prove that the DDGP3 is NP-hard and we extend the Branch & Prune (BP) algorithm, previously used for the DMDGP, for solving instances of the DDGP3. Protein graphs may or may not be in DMDGP and/or DDGP3 depending on vertex orders and edge density. We show experimentally that as distance thresholds decrease, PDB protein graphs which fail to be in the DMDGP still belong to DDGP3, which means that they can still be solved using a discrete search.

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

Published in Optimization Letters, 2012, 6 (8), pp.1671-1686. ⟨10.1007/s11590-011-0358-3⟩

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-00756943

DOI: 10.1007/s11590-011-0358-3

Access Statistics for this paper

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