Abstract
We propose a coarse-grained representation for the solutions of discretizable instances of the Distance Geometry Problem (DGP). In several real-life applications, the distance information is not provided with high precision, but an approximation is rather given. We focus our attention on protein instances where inter-atomic distances can be either obtained from the chemical structure of the molecule (which are exact), or through experiments of Nuclear Magnetic Resonance (which are generally represented by real-valued intervals). The coarse-grained representation allows us to extend a previously proposed algorithm for the Discretizable DGP (DDGP), the branch-and-prune (BP) algorithm. In the standard BP, atomic positions are fixed to unique positions at every node of the search tree: we rather represent atomic positions by a pair consisting of a feasible region, together with a most-likely position for the atom in this region. While the feasible region is a constant during the search, the associated position can be refined by considering the new distance constraints that appear at further layers of the search tree. To perform the refinement task, we integrate the BP algorithm with a spectral projected gradient algorithm. Some preliminary computational experiments on artificially generated instances show that this new approach is quite promising to tackle real-life DGPs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Almeida, F.C.L., Moraes, A.H., Gomes-Neto, F.: An overview on protein structure determination by NMR, historical and future perspectives of the use of distance geometry methods. In: Mucherino, A., Lavor, C., Liberti, L., Maculan, N. (eds.) Distance Geometry: Theory, Methods and Applications, pp. 377–412. Springer, New York (2013). https://doi.org/10.1007/978-1-4614-5128-0_18
Alves, R., Lavor, C.: Geometric algebra to model uncertainties in the discretizable molecular distance geometry problem. Adv. Appl. Clifford Algebra 27, 439–452 (2017)
Barzilai, J., Borwein, J.: Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988)
Berman, H., et al.: The protein data bank. Nucleic Acids Res. 28, 235–242 (2000)
Billinge, S.J.L., Duxbury, Ph.M., Gonçalves, D.S., Lavor, C., Mucherino, A.: Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures. Ann. Oper. Res. (2018, to appear)
Birgin, E.G., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10, 1196–1211 (2000)
Cassioli, A., et al.: An algorithm to enumerate all possible protein conformations verifying a set of distance restraints. BMC Bioinform. 16, 23 (2015). p. 15
Crippen, G.M., Havel, T.F.: Distance Geometry and Molecular Conformation. Wiley, Hoboken (1988)
de Leeuw, J.: Convergence of the majorization method for multidimensional scaling. J. Classif. 5, 163–180 (1988)
Glunt, W., Hayden, T.L., Raydan, M.: Molecular conformations from distance matrices. J. Comput. Chem. 14(1), 114–120 (1993)
Glunt, W., Hayden, T.L., Raydan, M.: Preconditioners for distance matrix algorithms. J. Comput. Chem. 15, 227–232 (1994)
Gonçalves, D.S., Mucherino, A.: Optimal partial discretization orders for discretizable distance geometry. Int. Trans. Oper. Res. 23(5), 947–967 (2016)
Gonçalves, D.S., Mucherino, A., Lavor, C.: An adaptive branching scheme for the Branch & Prune algorithm applied to distance geometry. In: IEEE Conference Proceedings, Federated Conference on Computer Science and Information Systems (FedCSIS 2014), Workshop on Computational Optimization (WCO 2014), Warsaw, Poland, pp. 463–469 (2014)
Gonçalves, D.S., Mucherino, A., Lavor, C., Liberti, L.: Recent advances on the interval distance geometry problem. J. Global Optim. 69(3), 525–545 (2017)
Gramacho, W., Mucherino, A., Lin, J.-H., Lavor, C.: A new approach to the discretization of multidimensional scaling. In: IEEE Conference Proceedings, Federated Conference on Computer Science and Information Systems (FedCSIS 2016), Workshop on Computational Optimization (WCO 2016), Gdansk, Poland, pp. 601–609 (2016)
Lavor, C., Liberti, L., Maculan, N., Mucherino, A.: Recent advances on the discretizable molecular distance geometry problem. Eur. J. Oper. Res. 219, 698–706 (2012)
Lavor, C., Liberti, L., Mucherino, A.: The interval Branch-and-Prune algorithm for the discretizable molecular distance geometry problem with inexact distances. J. Global Optim. 56(3), 855–871 (2013)
Liberti, L., Lavor, C., Maculan, N.: A Branch-and-Prune algorithm for the molecular distance geometry problem. Int. Trans. Oper. Res. 15, 1–17 (2008)
Liberti, L., Lavor, C., Maculan, N., Mucherino, A.: Euclidean distance geometry and applications. SIAM Rev. 56(1), 3–69 (2014)
Liberti, L., Lavor, C., Mucherino, A.: The discretizable molecular distance geometry problem seems easier on proteins. In: Mucherino, A., Lavor, C., Liberti, L., Maculan, N. (eds.) Distance Geometry: Theory, Methods and Applications, pp. 47–60. Springer, New York (2013). https://doi.org/10.1007/978-1-4614-5128-0_3
Liberti, L., Lavor, C., Mucherino, A., Maculan, N.: Molecular distance geometry methods: from continuous to discrete. Int. Trans. Oper. Res. 18(1), 33–51 (2011)
Mucherino, A.: On the identification of discretization orders for distance geometry with intervals. In: Nielsen, F., Barbaresco, F. (eds.) GSI 2013. LNCS, vol. 8085, pp. 231–238. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40020-9_24
Mucherino, A.: A pseudo de Bruijn graph representation for discretization orders for distance geometry. In: Ortuño, F., Rojas, I. (eds.) IWBBIO 2015. LNCS, vol. 9043, pp. 514–523. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-16483-0_50
Mucherino, A., Gonçalves, D.S.: An approach to dynamical distance geometry. In: Nielsen, F., Barbaresco, F. (eds.) GSI 2017. LNCS, vol. 10589, pp. 821–829. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68445-1_94
Mucherino, A., Lavor, C., Liberti, L.: The discretizable distance geometry problem. Optim. Lett. 6(8), 1671–1686 (2012)
Mucherino, A., Omer, J., Hoyet, L., Giordano, P.R., Multon, F.: An application-based characterization of dynamical distance geometry problems. Optim. Lett. (2018, to appear)
Saxe, J.: Embeddability of weighted graphs in k-space is strongly NP-hard. In: Proceedings of 17th Allerton Conference in Communications, Control and Computing, pp. 480–489 (1979)
Sit, A., Wu, Z.: Solving a generalized distance geometry problem for protein structure determination. Bull. Math. Biol. 73, 2809–2836 (2011)
Sulkowska, J.I., Morcos, F., Weigt, M., Hwa, T., Onuchic, J.N.: Genomics-aided structure prediction. Proc. Natl. Acad. Sci. (PNAS) U.S.A. 109(26), 10340–10345 (2012)
Zhang, H., Hager, W.W.: A nonmonotone line search technique and its applications to unconstrained optimization. SIAM J. Optim. 14(4), 1043–1056 (2004)
Acknowledgments
AM and JHL wish to thank the CNRS and MoST for financial support (PRC project “Rapid NMR Protein Structure Determination and Conformational Transition Sampling by a Novel Geometrical Approach”). AM and DSG wish to thank CAPES PRINT for financial support. DSG also thanks CNPq for financial support (Grant n. 421386/2016-9).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Mucherino, A., Lin, JH., Gonçalves, D.S. (2019). A Coarse-Grained Representation for Discretizable Distance Geometry with Interval Data. In: Rojas, I., Valenzuela, O., Rojas, F., Ortuño, F. (eds) Bioinformatics and Biomedical Engineering. IWBBIO 2019. Lecture Notes in Computer Science(), vol 11465. Springer, Cham. https://doi.org/10.1007/978-3-030-17938-0_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-17938-0_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-17937-3
Online ISBN: 978-3-030-17938-0
eBook Packages: Computer ScienceComputer Science (R0)