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

• Autorzy: Mucherino Antonio , Gonçalves Douglas S. , Liberti Leo , Lin Jung-Hsin , Lavor Carlile , Maculan Nelson

Identyfikatory

DOI

10.15439/2020F35

• Konferencja: Federated Conference on Computer Science and Information Systems (15 ; 06-09.09.2020 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

computational geometry; graph theory; software tools

PL

geometria obliczeniowa; teoria grafów; narzędzia programowe

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2020
• Tom: Vol. 21
• Strony: 289--294
• Opis fizyczny: Bibliogr. 14 poz., wz., il., tab.

Twórcy

autor

Mucherino Antonio

• IRISA, University of Rennes 1, Rennes, France.

autor

Gonçalves Douglas S.

• Centro de Ciências Físicas e Matemáticas, Universidade Federal de Santa Catarina, Florianópolis, Brazil

autor

Liberti Leo

• LIX, Ĕcole Polytechnique, Palaiseau, France

autor

Lin Jung-Hsin

• Research Center for Applied Sciences, Academia Sinica, Taipei, Taiwan

autor

Lavor Carlile

• Department of Applied Mathematics (IMECC-UNICAMP), University of Campinas, Campinas (SP), Brazil

autor

Maculan Nelson

• COPPE, Federal University of Rio de Janeiro, Rio de Janeiro (RJ), Brazil

Bibliografia

• 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.

Uwagi

1. Track 1: Artificial Intelligence

2. Technical Session: 13th International Workshop on Computational Optimization

3. Imiona autorów zaczerpnięte ze strony: https://annals-csis.org/Volume_21/drp/35.html

4. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).