Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 21

Proceedings of the 2020 Federated Conference on Computer Science and Information Systems

MD-jeep: a New Release for Discretizable Distance Geometry Problems with Interval Data

, , , , ,

DOI: http://dx.doi.org/10.15439/2020F35

Citation: Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 21, pages 289294 ()

Full text

Abstract. With the most recent releases of MD-JEEP, new relevant features have been included to our software tool. MD-JEEP solves instances of the class of Discretizable Distance Geometry Problems (DDGPs), which ask to find possible realizations, in a Euclidean space, of a simple weighted undirected graph for which distance constraints between vertices are given, and for which a discretization of the search space can be supplied. Since its version 0.3.0, MD-JEEP is able to deal with instances containing interval data. We focus in this short paper on the most recent release MD-JEEP 0.3.2: among the new implemented features, we will focus our attention on three features: (i) an improved procedure for the generation and update of the boxes used in the coarse-grained representation (necessary to deal with instances containing interval data); (ii) a new procedure for the selection of the so-called discretization vertices (necessary to perform the discretization of the search space); (iii) the implementation of a general parser which allows the user to easily load DDGP instances in a given specified format. The source code of MD-JEEP 0.3.2 is available on GitHub, where the reader can find all additional details about the implementation of such new features, as well as verify the effectiveness of such features by comparing MD- JEEP 0.3.2 with its previous releases.


  1. F.C.L. Almeida, A.H. Moraes, F. Gomes-Neto, An Overview on Protein Structure Determination by NMR, Historical and Future Perspectives of the Use of Distance Geometry Methods. In:
  2. , 377–412, 2013.
  3. E.G. Birgin, J.M. Martı́nez, M. Raydan, Nonmonotone Spectral Projected Gradient Methods on Convex Sets, SIAM Journal on Optimization 10, 1196–1211, 2000.
  4. D.S. Gonçalves, A. Mucherino, Optimal Partial Discretization Orders for Discretizable Distance Geometry, International Transactions in Operational Research 23(5), 947–967, 2016.
  5. N. Krislock, H. Wolkowicz, Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions, SIAM Journal on Optimization 20, 2679–2708, 2010.
  6. L. Liberti, C. Lavor, N. Maculan, A Branch-and-Prune Algorithm for the Molecular Distance Geometry Problem, International Transactions in Operational Research 15, 1–17, 2008.
  7. L. Liberti, C. Lavor, N. Maculan, A. Mucherino, Euclidean Distance Geometry and Applications, SIAM Review 56(1), 3–69, 2014.
  8. D. Maioli, C. Lavor, D. Gonçalves, A Note on Computing the Intersection of Spheres in Rn , ANZIAM Journal 59, 271–279, 2017.
  9. A. Mucherino, C. Lavor, L. Liberti, The Discretizable Distance Geometry Problem, Optimization Letters 6(8), 1671–1686, 2012.
  10. A. Mucherino, C. Lavor, L. Liberti, N. Maculan (Eds.), Distance Geometry: Theory, Methods and Applications, 410 pages, Springer, 2013.
  11. 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 rdof the 3 International Congress on Mathematical Software (ICMS10), Kobe, Japan, 186—197, 2010.
  12. A. Mucherino, J-H. Lin, An Efficient Exhaustive Search for the Discretizable Distance Geometry Problem with Interval Data, IEEE Conference Proceedings, Federated Conference on Computer Science and Information Systems (FedCSIS19), Workshop on Computational Optimization (WCO19), Leipzig, Germany, 135–141, 2019.
  13. 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 (IWB-BIO19), Part I, Granada, Spain, 3–13, 2019.
  14. J. Omer, A. Mucherino, Referenced Vertex Ordering Problem: Theory, Applications and Solution Methods, HAL open archives (hal-02509522, version 1), March 2020.