The Discretizable Distance Geometry Problem

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.
Type de document :
Article dans une revue
Optimization Letters, Springer Verlag, 2012, 6 (8), pp.1671-1686
Liste complète des métadonnées
Contributeur : Antonio Mucherino <>
Soumis le : samedi 24 novembre 2012 - 13:36:57
Dernière modification le : jeudi 7 février 2019 - 17:16:38


  • HAL Id : hal-00756943, version 1


Antonio Mucherino, Carlile Lavor, Leo Liberti. The Discretizable Distance Geometry Problem. Optimization Letters, Springer Verlag, 2012, 6 (8), pp.1671-1686. 〈hal-00756943〉



Consultations de la notice