×

MD-jeep: an implementation of a branch and prune algorithm for distance geometry problems. (English) Zbl 1294.68144

Fukuda, Komei (ed.) et al., Mathematical software – ICMS 2010. Third international congress on mathematical software, Kobe, Japan, September 13–17, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15581-9/pbk). Lecture Notes in Computer Science 6327, 186-197 (2010).
Summary: 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).
For the entire collection see [Zbl 1196.68008].

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
51K99 Distance geometry
90C27 Combinatorial optimization
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)

Software:

MD-jeep
PDFBibTeX XMLCite
Full Text: DOI