The Discretizable Molecular Distance Geometry Problem

Details The Discretizable Molecular Distance Geometry Problem The Discretizable Molecular Distance Geometry Problem

2006-08-05

arxiv.org/abs/q-bio/0608012v1

Biology

Quantitative Biology

Biomolecules

23 pages, 9 figures

Scientific paper

Given a weighted undirected graph $G=(V,E,d)$, the Molecular Distance Geometry Problem (MDGP) is that of finding a function $x:G\to \mathbb{R}^{3}$, where $||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 \textbf{NP}-complete and we propose an algorithm, called Branch-and-Prune (BP), which solves the DMDGP exactly. The BP algorithm performs exceptionally well in terms of solution accuracy and can find all solutions to any DMDGP instance. We successfully test the BP algorithm on several randomly generated instances.

Affiliated with

Also associated with

No associations

Rating

The Discretizable Molecular Distance Geometry Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Discretizable Molecular Distance Geometry Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Discretizable Molecular Distance Geometry Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-629409