Fiche du document
2012
- handle: 10670/1.mubqnj
- hal: hal-00756940
- ARXIV: q-bio/0608012
- doi: 10.1007/s10589-011-9402-6
Ce document est lié à :
info:eu-repo/semantics/altIdentifier/arxiv/q-bio/0608012
Ce document est lié à :
info:eu-repo/semantics/altIdentifier/doi/10.1007/s10589-011-9402-6
Sujets proches
Abstract metrics Metric topologyCiter ce document
Antonio Mucherino et al., « The Discretizable Molecular Distance Geometry Problem », HAL-SHS : droit et gestion, ID : 10.1007/s10589-011-9402-6
Métriques
Partage / Export
Résumé
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.