We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The discretizable molecular distance geometry problem.
- Authors
Lavor, Carlile; Liberti, Leo; Maculan, Nelson; Mucherino, Antonio
- Abstract
Given a simple weighted undirected graph G=( V, E, d) with d: E→ℝ, the Molecular Distance Geometry Problem (MDGP) consists in finding an embedding x: V→ℝ such that | x− x|= d for each { u, v}∈ 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.
- Subjects
DISTANCE geometry; GRAPHIC methods; ALGORITHMS; GEOMETRY; METRIC spaces
- Publication
Computational Optimization & Applications, 2012, Vol 52, Issue 1, p115
- ISSN
0926-6003
- Publication type
Academic Journal
- DOI
10.1007/s10589-011-9402-6