MD-jeep: An implementation of a Branch and Prune algorithm for distance geometry problems

Antonio Mucherino; Leo Liberti; Carlile Lavor

doi:10.1007/978-3-642-15582-6_34

MD-jeep: An implementation of a Branch and Prune algorithm for distance geometry problems

Antonio Mucherino
, Leo Liberti
, Carlile Lavor

INRIA Institut National de Recherche en Informatique et en Automatique
Department of Applied Mathematics
University of Campinas (UNICAMP)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

23 Citations (Scopus)

Abstract

We present MD-jeep, an implementation of a Branch & Prune (BP) algorithm, which we employ for the solution of distance geometry problems related to molecular conformations. We consider the problem of finding the conformation of a molecule from the distances between some pairs of its atoms, which can be estimated by experimental techniques. We reformulate this problem as a combinatorial optimization problem, and describe a branch and prune solution strategy. We discuss its software implementation, and its complexity in terms of floating-point operations and memory requirements. MD-jeep has been developed in the C programming language. The sources of the presented software are available on the Internet under the GNU General Public License (v.2).

Original language	English
Title of host publication	Mathematical Software, ICMS 2010 - Third International Congress on Mathematical Software, Proceedings
Publisher	Springer Verlag
Pages	186-197
Number of pages	12
ISBN (Print)	3642155812, 9783642155819
DOIs	https://doi.org/10.1007/978-3-642-15582-6_34
Publication status	Published - 1 Jan 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6327 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-642-15582-6_34

Cite this

Mucherino, A., Liberti, L., & Lavor, C. (2010). MD-jeep: An implementation of a Branch and Prune algorithm for distance geometry problems. In Mathematical Software, ICMS 2010 - Third International Congress on Mathematical Software, Proceedings (pp. 186-197). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6327 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-15582-6_34

Mucherino, Antonio ; Liberti, Leo ; Lavor, Carlile. / MD-jeep : An implementation of a Branch and Prune algorithm for distance geometry problems. Mathematical Software, ICMS 2010 - Third International Congress on Mathematical Software, Proceedings. Springer Verlag, 2010. pp. 186-197 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{688127d6f909468fa2a5a45830381a51,

title = "MD-jeep: An implementation of a Branch and Prune algorithm for distance geometry problems",

abstract = "We present MD-jeep, an implementation of a Branch \& Prune (BP) algorithm, which we employ for the solution of distance geometry problems related to molecular conformations. We consider the problem of finding the conformation of a molecule from the distances between some pairs of its atoms, which can be estimated by experimental techniques. We reformulate this problem as a combinatorial optimization problem, and describe a branch and prune solution strategy. We discuss its software implementation, and its complexity in terms of floating-point operations and memory requirements. MD-jeep has been developed in the C programming language. The sources of the presented software are available on the Internet under the GNU General Public License (v.2).",

author = "Antonio Mucherino and Leo Liberti and Carlile Lavor",

year = "2010",

month = jan,

day = "1",

doi = "10.1007/978-3-642-15582-6\_34",

language = "English",

isbn = "3642155812",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "186--197",

booktitle = "Mathematical Software, ICMS 2010 - Third International Congress on Mathematical Software, Proceedings",

}

Mucherino, A, Liberti, L & Lavor, C 2010, MD-jeep: An implementation of a Branch and Prune algorithm for distance geometry problems. in Mathematical Software, ICMS 2010 - Third International Congress on Mathematical Software, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6327 LNCS, Springer Verlag, pp. 186-197. https://doi.org/10.1007/978-3-642-15582-6_34

MD-jeep: An implementation of a Branch and Prune algorithm for distance geometry problems. / Mucherino, Antonio; Liberti, Leo; Lavor, Carlile.
Mathematical Software, ICMS 2010 - Third International Congress on Mathematical Software, Proceedings. Springer Verlag, 2010. p. 186-197 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6327 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - MD-jeep

T2 - An implementation of a Branch and Prune algorithm for distance geometry problems

AU - Mucherino, Antonio

AU - Liberti, Leo

AU - Lavor, Carlile

PY - 2010/1/1

Y1 - 2010/1/1

N2 - We present MD-jeep, an implementation of a Branch & Prune (BP) algorithm, which we employ for the solution of distance geometry problems related to molecular conformations. We consider the problem of finding the conformation of a molecule from the distances between some pairs of its atoms, which can be estimated by experimental techniques. We reformulate this problem as a combinatorial optimization problem, and describe a branch and prune solution strategy. We discuss its software implementation, and its complexity in terms of floating-point operations and memory requirements. MD-jeep has been developed in the C programming language. The sources of the presented software are available on the Internet under the GNU General Public License (v.2).

AB - We present MD-jeep, an implementation of a Branch & Prune (BP) algorithm, which we employ for the solution of distance geometry problems related to molecular conformations. We consider the problem of finding the conformation of a molecule from the distances between some pairs of its atoms, which can be estimated by experimental techniques. We reformulate this problem as a combinatorial optimization problem, and describe a branch and prune solution strategy. We discuss its software implementation, and its complexity in terms of floating-point operations and memory requirements. MD-jeep has been developed in the C programming language. The sources of the presented software are available on the Internet under the GNU General Public License (v.2).

U2 - 10.1007/978-3-642-15582-6_34

DO - 10.1007/978-3-642-15582-6_34

M3 - Conference contribution

AN - SCOPUS:78149236724

SN - 3642155812

SN - 9783642155819

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 186

EP - 197

BT - Mathematical Software, ICMS 2010 - Third International Congress on Mathematical Software, Proceedings

PB - Springer Verlag

ER -

Mucherino A, Liberti L, Lavor C. MD-jeep: An implementation of a Branch and Prune algorithm for distance geometry problems. In Mathematical Software, ICMS 2010 - Third International Congress on Mathematical Software, Proceedings. Springer Verlag. 2010. p. 186-197. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-15582-6_34

MD-jeep: An implementation of a Branch and Prune algorithm for distance geometry problems

Abstract

Publication series

Access to Document

Fingerprint

Cite this