An efficient exhaustive search for the discretizable Distance Geometry Problem with interval data

• Autorzy: Mucherino A. , Lin J.-H.

Identyfikatory

DOI

10.15439/2019F62

• Konferencja: Federated Conference on Computer Science and Information Systems (14 ; 01-04.09.2019 ; Leipzig, Germany)
• Języki publikacji: EN

Abstrakty

EN

The Distance Geometry Problem (DGP) asks whether a simple weighted undirected graph can be realized in a given space (generally Euclidean) so that a given set of distance constraints (associated to the edges of the graph) is satisfied. The Discretizable DGP (DDGP) represents a subclass of instances where the search space can be reduced to a discrete domain having the structure of a tree. In the ideal case where all distances are precise, the tree is binary and one singleton, representing one possible position for a vertex of the graph, is associated to every tree node. When the distance information is however not precise, the uncertainty on the distance values implies that a three-dimensional region of the search space needs to be assigned to some nodes of the tree. By using a recently proposed coarse-grained representation for DDGP solutions, we extend in this work the branch-and-prune (BP) algorithm so that it can efficiently perform an exhaustive search of the search domain, even when the uncertainty on the distances is important. Instead of associating singletons to nodes, we consider a pair consisting of a box and of a most-likely position for the vertex in this box. Initial estimations of the vertex positions in every box can be subsequently refined by using local optimization. The aim of this paper is two-fold: (i) we propose a new simple method for the computation of the three-dimensional boxes to be associated to the nodes of the search tree; (ii) we introduce the resolution parameter ρ, with the aim of controling the similarity between pairs of solutions in the solution set. Some initial computational experiments show that our algorithm extension, differently from previously proposed variants of the BP algorithm, is actually able to terminate the enumeration of the solution set by providing solutions that differ from one another accordingly to the given resolution parameter.

Słowa kluczowe

EN

geometry; optimisation; search problems; exhaustive search

PL

geometria; optymalizacja; problemy wyszukiwawcze

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2019
• Tom: Vol. 18
• Strony: 135--141
• Opis fizyczny: Bibliogr. 27 poz., wz., rys.

Twórcy

autor

Mucherino A.

• IRISA, University of Rennes 1, Rennes, France

autor

Lin J.-H.

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

Bibliografia

• 1. R. Alves, C. Lavor, Geometric Algebra to Model Uncertainties in the Discretizable Molecular Distance Geometry Problem, Advances in Applied Clifford Algebra 27, 439–452, 2017.
• 2. H. Berman, J. Westbrook, Z. Feng, G. Gilliland, T. Bhat, H. Weissig, I. Shindyalov, P. Bourne, The Protein Data Bank, Nucleic Acids Research 28, 235–242, 2000.
• 3. E.G. Birgin, J.M. Martı́nez, M. Raydan, Spectral Projected Gradient methods: Review and Perspectives, Journal of Statistical Software 60(i03), 21 pages, 2014.
• 4. A. Bondi, van der Waals Volumes and Radii, Journal of Physical Chemistry 68(3), 441–451, 1964.
• 5. D.A. Case, R.M. Betz, D.S. Cerutti, T.E. Cheatham III, T.A. Darden, R.E. Duke, T.J. Giese, H. Gohlke, A.W. Goetz, N. Homeyer, S. Izadi, P. Janowski, J. Kaus, A. Kovalenko, T.S. Lee, S. LeGrand, P. Li, C. Lin, T. Luchko, R. Luo, B. Madej, D. Mermelstein, K.M. Merz, G. Monard, H. Nguyen, H.T. Nguyen, I. Omelyan, A. Onufriev, D.R. Roe, A. Roitberg, C. Sagui, C.L. Simmerling, W.M. Botello-Smith, J. Swails, R.C. Walker, J. Wang, R.M. Wolf, X. Wu, L. Xiao, P.A. Kollman, AMBER 2016, University of California, San Francisco, 2016.
• 6. A. Cassioli, B. Bardiaux, G. Bouvier, A. Mucherino, R. Alves, L. Liberti, M. Nilges, C. Lavor, T.E. Malliavin, An Algorithm to Enumerate all Possible Protein Conformations verifying a Set of Distance Restraints, BMC Bioinformatics 16:23, 15 pages, 2015.
• 7. G.M. Crippen, T.F. Havel, Distance Geometry and Molecular Conformation, John Wiley & Sons, 1988.
• 8. N.M. Freris, S.R. Graham, P.R. Kumar, Fundamental Limits on Synchronizing Clocks Over Networks, IEEE Transactions on Automatic Control 56(6), 1352–1364, 2010.
• 9. D.S. Gonçalves, A. Mucherino, Discretization Orders and Efficient Computation of Cartesian Coordinates for Distance Geometry, Optimization Letters 8(7), 2111–2125, 2014.
• 10. D.S. Gonçalves, A. Mucherino, Optimal Partial Discretization Orders for Discretizable Distance Geometry, International Transactions in Operational Research 23(5), 947–967, 2016.
• 11. 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.
• 12. 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.
• 13. M.C. Hout, M.H. Papesh, S.D. Goldinger, Multidimensional Scaling, Wiley Interdisciplinary Reviews: Cognitive Science 4(1), 93–103, 2013.
• 14. C. Lavor, L. Liberti, N. Maculan, A. Mucherino, The Discretizable Molecular Distance Geometry Problem, Computational Optimization and Applications 52, 115–146, 2012.
• 15. 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.
• 16. C. Lavor, L. Liberti, A. Mucherino, N. Maculan, On a Discretizable Subclass of Instances of the Molecular Distance Geometry Problem, ACM Conference Proceedings, 24th Annual ACM Symposium on Applied Computing, Hawaii, USA, 804–805, 2009.
• 17. 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.
• 18. L. Liberti, C. Lavor, N. Maculan, A. Mucherino, Euclidean Distance Geometry and Applications, SIAM Review 56(1), 3–69, 2014.
• 19. L. Liberti, C. Lavor, A. Mucherino, N. Maculan, Molecular Distance Geometry Methods: from Continuous to Discrete, International Transactions in Operational Research 18(1), 33–51, 2011.
• 20. J. Mongan, C. Simmerling, J.A. McCammon, D.A. Case, A. Onufriev, Generalized Born with a Simple, Robust Molecular Volume Correction, Journal of Chemical Theory and Computation 3, 156–169, 2007.
• 21. 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.
• 22. A. Mucherino, D.S. Gonçalves, An Approach to Dynamical Distance Geometry, Lecture Notes in Computer Science 10589, F. Nielsen, F. Barbaresco (Eds.), Proceedings of Geometric Science of Information (GSI17), Paris, France, 821–829, 2017.
• 23. A. Mucherino, C. Lavor, L. Liberti, The Discretizable Distance Geometry Problem, Optimization Letters 6(8), 1671–1686, 2012.
• 24. A. Mucherino, J-H. Lin, D.S. Gonçalves, Coarse-Grained Representation for Discretizable Distance Geometry with Interval Data, to appear in Lecture Notes in Computer Science, 2019.
• 25. A. Mucherino, J. Omer, L. Hoyet, P. Robuffo Giordano, F. Multon, An Application-based Characterization of Dynamical Distance Geometry Problems, to appear in Optimization Letters, Springer, 2019.
• 26. J. Saxe, Embeddability of Weighted Graphs in k-Space is Strongly NP-hard, Proceedings of 17th Allerton Conference in Communications, Control and Computing, 480–489, 1979.
• 27. J. Wang, R.K. Ghosh, S.K. Das, A Survey on Sensor Localization, Journal of Control Theory and Applications 8(1), 2–11, 2010.

Uwagi

1. Track 1: Artificial Intelligence and Applications

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

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