dorsal/arxiv
View SchemaThe Discretizable Molecular Distance Geometry Problem
| Authors | Carlile Lavor, Leo Liberti, Nelson Maculan |
|---|---|
| Categories | |
| ArXiv ID | q-bio/0608012 |
| URL | https://arxiv.org/abs/q-bio/0608012 |
Abstract
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.
{
"annotation_id": "194b94b8-0d20-4dc4-a1f4-3d20b7fceaf1",
"date_created": "2026-03-02T18:01:34.672000Z",
"date_modified": "2026-03-02T18:01:34.672000Z",
"file_hash": "ff5544b458f3a949e34332c7a3ce27eccfa5307f7d3eba8b38855549c5e2b5fd",
"private": false,
"record": {
"abstract": "Given a weighted undirected graph $G=(V,E,d)$, the Molecular Distance\nGeometry Problem (MDGP) is that of finding a function $x:G\\to \\mathbb{R}^{3}$,\nwhere $||x(u)-x(v)||=d(u,v)$ for each $\\{u,v\\}\\in E$. We show that under a few\nassumptions usually satisfied in proteins, the MDGP can be formulated as a\nsearch in a discrete space. We call this MDGP subclass the Discretizable MDGP\n(DMDGP). We show that the DMDGP is \\textbf{NP}-complete and we propose an\nalgorithm, called Branch-and-Prune (BP), which solves the DMDGP exactly. The BP\nalgorithm performs exceptionally well in terms of solution accuracy and can\nfind all solutions to any DMDGP instance. We successfully test the BP algorithm\non several randomly generated instances.",
"arxiv_id": "q-bio/0608012",
"authors": [
"Carlile Lavor",
"Leo Liberti",
"Nelson Maculan"
],
"categories": [
"q-bio.BM",
"q-bio.QM"
],
"title": "The Discretizable Molecular Distance Geometry Problem",
"url": "https://arxiv.org/abs/q-bio/0608012"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "655c75c9-bda9-4143-af46-95bc2bc32273",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}