Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
151 lines (119 sloc) 8.3 KB
*** MD-jeep, version 0.3.0 ***
The Branch & Prune algorithm for Discretizable Distance Geometry
Copyright (C) 2019, Mucherino, Goncalves, Lavor, Liberti, Lin, Maculan
GNU General Public License v.3
This program is free software: you can redistribute it and/or modify it under the terms of the
GNU General Public License as published by the Free Software Foundation, either version 3 of the License,
or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License along with this program.
If not, see <https://www.gnu.org/licenses/>.
From the current version (0.3.0), MDjeep solves instances containing both exact and interval distance values.
Although initially written for problems arising in the context of structural biology, MDjeep is a general solver
capable to solve instances from various applications. General "graph" notions are therefore employed (vertex,
distance edge).
Discretizable Distance Geometry consists of a subclass of problems for which the search space can be discretized
and reduced to a tree. Given a graph G=(V,E,d), with vertex set V, edge set E indicating whether the distance
between two vertices is known or not, and a weight function d providing the numerical values for such distances,
a problem instance falls in our special subclass where there exist a vertex order on V such that:
1. the first 3 vertices in the order form a clique with exact distances
2. for all other vertices with rank i > 3, there must exist three reference vertices j1, j2 and j3, such that:
j1 < i, j2 < i, j3 < i, (j1,i) \in E, (j2,i) \in E, (j3,i) \in E.
In this version, we suppose that only one of the three distances d(j1,i), d(j2,i) and d(j3,i) can be represented
by an interval, while the others are supposed to be exact. For more information, please refer to our list of
publications below.
syntax: ./mdjeep [options] instance.nmr
NMR file format (.nmr) basically consists of a list of distances, with some additional information about the vertices.
Every line of the text file should contain (in this specific order):
- an integer label for the first vertex (unsigned int)
- an integer label for the second vertex (unsigned int)
- an integer label for the group of the first vertex (unsigned int)
- an integer label for the group of the second vertex (unsigned int)
- the distance lower bound (double)
- the distance upper bound (double)
- a string label for the first vertex (char[max 20])
- a string label for the second vertex (char[max 20])
- a string label for the group of the first vertex (char[max 20])
- a string label for the group of the second vertex (char[max 20])
Important to notice:
- the integer vertex labels need to be consecutive, but the smallest label is not supposed to be equal to 0 (neither to 1);
the only constraint for the smallest label is that it needs to be nonnegative
- this format is not completely compatible with previous MDjeep versions: to load instances in the previous format,
please use the option -v (see below)
MDjeep options (you can access to this list by running MDjeep without arguments):
-v | change input data format to previous versions (argument 0.1 or 0.2, with the same effect)
-e | sets the tolerance epsilon (needs an extra argument, double, default is 0.001)
-r | sets the resolution parameter (needs an extra argument, double, default is 1.0)
-sym | only one symmetric half of the tree is explored (argument 1 or 2)
-1 | the algorithm stops at the first solution
-p | prints the best found solution in a text file
-P | prints all found solutions (in the same text file)
| (when using -1, options -p and -P have the same effect)
-f | specifies the output format (default is "txt", may be changed to "pdb")
-nomonitor | does no show the current layer number during the execution to improve performace
Notice that the use of option -nomonitor can actually improve MDjeep performances; moreover, it is recommended
to use it when redirecting stdout to a file.
If MDjeep takes too long to solve your instance, you can terminate it with the ^C signal and verify the current partial
solution in the output file (it will be created before termination if one of the two options -p or -P were used).
If you refer to this sofware in your publications, please cite the appropriate paper(s).
Follows a list of main publications:
[1] A. Mucherino, J-H. Lin,
An Efficient Exhaustive Search for the Discretizable Distance Geometry Problem with Interval Data,
to appear in IEEE Conference Proceedings, Federated Conference on Computer Science and Information Systems (FedCSIS19),
Workshop on Computational Optimization (WCO19),
Leipzig, Germany, September 2019. (in "publication.ref.pdf")
[2] A. Mucherino, J-H. Lin, D.S. Gonçalves,
A Coarse-Grained Representation for Discretizable Distance Geometry with Interval Data,
Lecture Notes in Computer Science 11465, Lecture Notes in Bioinformatics series, I. Rojas et al (Eds.),
Proceedings of the 7th International Work-Conference on Bioinformatics and Biomedical Engineering (IWBBIO19), Part I,
Granada, Spain, 3-13, 2019.
[3] D.S. Gonçalves, A. Mucherino, C. Lavor, L. Liberti,
Recent Advances on the Interval Distance Geometry Problem,
Journal of Global Optimization 69(3), 525-545, 2017.
[4] D.S. Gonçalves, A. Mucherino,
Discretization Orders and Efficient Computation of Cartesian Coordinates for Distance Geometry,
Optimization Letters 8(7), 2111-2125, 2014.
[5] V. Costa, A. Mucherino, C. Lavor, A. Cassioli, L.M. Carvalho, N. Maculan,
Discretization Orders for Protein Side Chains,
Journal of Global Optimization 60(2), 333-349, 2014.
[6] L. Liberti, C. Lavor, N. Maculan, A. Mucherino,
Euclidean Distance Geometry and Applications,
SIAM Review 56(1), 3-69, 2014.
[7] D.S. Gonçalves, A. Mucherino, C. Lavor,
An Adaptive Branching Scheme for the Branch & Prune Algorithm applied to Distance Geometry,
IEEE Conference Proceedings, Federated Conference on Computer Science and Information Systems (FedCSIS14),
Workshop on Computational Optimization (WCO14),
Warsaw, Poland, 463-469, 2014.
[8] A. Mucherino, C. Lavor, L. Liberti, N. Maculan (Eds.),
Distance Geometry: Theory, Methods and Applications,
410 pages, Springer, 2013.
[9] C. Lavor, L. Liberti, A. Mucherino,
The interval Branch-and-Prune Algorithm for the Discretizable Molecular Distance Geometry Problem with Inexact Distances,
Journal of Global Optimization 56(3), 855-871, 2013.
[10] A. Mucherino,
On the Identification of Discretization Orders for Distance Geometry with Intervals,
Lecture Notes in Computer Science 8085, F. Nielsen and F. Barbaresco (Eds.),
Proceedings of Geometric Science of Information (GSI13),
Paris, France, 231-238, 2013.
[11] A. Mucherino, C. Lavor, L. Liberti,
The Discretizable Distance Geometry Problem,
Optimization Letters 6(8), 1671-1686, 2012.
[12] A. Mucherino, C. Lavor, L. Liberti,
Exploiting Symmetry Properties of the Discretizable Molecular Distance Geometry Problem,
Journal of Bioinformatics and Computational Biology 10(3), 1242009(1-15), 2012.
[13] C. Lavor, L. Liberti, N. Maculan, A. Mucherino,
The Discretizable Molecular Distance Geometry Problem,
Computational Optimization and Applications 52, 115-146, 2012.
[14] C. Lavor, L. Liberti, A. Mucherino,
On the Solution of Molecular Distance Geometry Problems with Interval Data,
IEEE Conference Proceedings, International Workshop on Computational Proteomics (IWCP10),
International Conference on Bioinformatics & Biomedicine (BIBM10),
Hong Kong, 77-82, 2010.
[15] A. Mucherino, L. Liberti, C. Lavor,
MD-jeep: an Implementation of a Branch & Prune Algorithm for Distance Geometry Problems,
Lectures Notes in Computer Science 6327, K. Fukuda et al. (Eds.),
Proceedings of the 3rd International Congress on Mathematical Software (ICMS10),
Kobe, Japan, 186-197, 2010.
The complete list of publications can be found at https://www.antoniomucherino.it/en/publications.php
You can’t perform that action at this time.