Abstract
The Distance Geometry Problem in three dimensions consists in finding an embedding in \({\mathbb{R}^3}\) of a given nonnegatively weighted simple undirected graph such that edge weights are equal to the corresponding Euclidean distances in the embedding. This is a continuous search problem that can be discretized under some assumptions on the minimum degree of the vertices. In this paper we discuss the case where we consider the full-atom representation of the protein backbone and some of the edge weights are subject to uncertainty within a given nonnegative interval. We show that a discretization is still possible and propose the iBP algorithm to solve the problem. The approach is validated by some computational experiments on a set of artificially generated instances.
Similar content being viewed by others
References
Berman H.M., Westbrook J., Feng Z., Gilliland G., Bhat T.N., Weissig H., Shindyalov I.N., Bourne P.E.: The protein data bank. Nucleic Acid Res. 28, 235–242 (2000)
Carvalho R.S., Lavor C., Protti F.: Extending the geometric build-up algorithm for the molecular distance geometry problem. Inf. Process. Lett. 108, 234–237 (2008)
Coope I.D.: Reliable computation of the points of intersection of n spheres in \({\mathbb{R}^n}\) . Australian N. Z. Ind. Appl. Math. J. 42, C461–C477 (2000)
Eren, T., Goldenberg, D.K., Whiteley, W., Yang, Y.R., Morse, A.S., Anderson, B.D.O., Belhumeur, P.N.: Rigidity, computation, and randomization in network localization. In: IEEE Infocom Proceedings, pp. 2673–2684 (2004)
Henneberg L.: Die graphische Statik der starren Systeme. B.G. Teubner, Leipzig (1911)
Kirkpatrick S., Jr. Gelatt C.D., Vecchi M.P.: Optimization by simulated annealing. Science 220, 671–680 (1983)
Krislock, N.: Semidefinite facial reduction for low-rank Euclidean distance matrix completion. Ph.D. thesis, University of Waterloo (2010)
Lavor, C., Lee, J., Lee-St. John, A., Liberti, L., Mucherino, A., Sviridenko, M.: Discretization orders for distance geometry problems. Optim. Lett. (to appear)
Lavor, C., Liberti, L., Maculan, N.: The discretizable molecular distance geometry problem. Technical report q-bio/0608012, arXiv (2006)
Lavor C., Liberti L., Maculan N.: Molecular distance geometry problem. In: Floudas, C., Pardalos , P. (eds) Encyclopedia of Optimization. 2nd edn, pp. 2305–2311. Springer, New York (2009)
Lavor, C., Liberti, L., Maculan, N., Mucherino, A.: The discretizable molecular distance geometry problem. Comput. Optim. Appl. (2011, to appear)
Lavor, C., Liberti, L., Mucherino, A.: On the solution of molecular distance geometry problems with interval data. In: International Conference on Bioinformatics and Biomedicine, IEEE Conference Proceedings, Hong Kong (2010)
Lavor C., Mucherino A., Liberti L., Maculan N.: Discrete approaches for solving molecular distance geometry problems using nmr data. Int. J. Comput. Biosci. 1, 88–94 (2011)
Lavor C., Mucherino A., Liberti L., Maculan N.: On the computation of protein backbones by using artificial backbones of hydrogens. J. Glob. Optim. 50, 329–344 (2011)
Lee-St. John, A.: Geometric constraint systems with applications in CAD and biology. Ph.D. thesis, University of Massachusetts at Amherst (2008)
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., Mucherino A., Maculan N.: Molecular distance geometry methods: from continuous to discrete. Int. Trans. Oper. Res. 18, 33–51 (2011)
Liu, X., Pardalos, P.M.: A tabu based pattern search method for the distance geometry problem. In: Giannessi, F. et al. (eds.) New Trends in Mathematical Programming, pp. 223–234. Kluwer Academic Publishers, The Netherlands (1998)
Mucherino, A., Lavor, C.: The branch and prune algorithm for the molecular distance geometry problem with inexact distances. In: Proceedings of the International Conference on Computational Biology, vol. 58. World Academy of Science, Engineering and Technology, 349–353 (2009)
Mucherino, A., Lavor, C., Liberti, L.: The discretizable distance geometry problem. Optim. Lett. (to appear)
Mucherino A., Lavor C., Liberti L., Maculan N.: On the definition of artificial backbones for the discretizable molecular distance geometry problem. Mathematica Balkanica 23, 289–302 (2009)
Mucherino, A., Liberti, L., Lavor, C., Maculan, N.: Comparisons between an exact and a metaheuristic algorithm for the molecular distance geometry problem. In: Rothlauf, F. (ed.) Proceedings of the Genetic and Evolutionary Computation Conference, pp. 333–340. Montreal, ACM (2009)
Nilges M., Gronenborn A.M., Brunger A.T., Clore G.M.: Determination of three-dimensional structures of proteins by simulated annealing with interproton distance restraints. application to crambin, potato carboxypeptidase inhibitor and barley serine proteinase inhibitor 2. Protein Eng. 2, 27–38 (1988)
Nilges M., Macias M.J., O’Donoghue S.I., Oschkinat H.: Automated noesy interpretation with ambiguous distance restraints: The refined nmr solution structure of the pleckstrin homology domain from β-spectrin. J. Mol. Biol. 269, 408–422 (1997)
Pardalos, P.M., Shalloway, D., Xu, G. (eds.): Global Minimization of Nonconvex Energy Functions: Molecular Conformation and Protein Folding. DIMACS. AMS (1996)
Saxe, J.B.: 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)
Schlick T.: Molecular modelling and simulation: an interdisciplinary guide. Springer, New York (2002)
So M.-C., Ye Y.: Theory of semidefinite programming for sensor network localization. Math. Programm. 109, 367–384 (2007)
Wu D., Wu Z., Yuan Y.: Rigid versus unique determination of protein structures with geometric buildup. Optim. Lett. 2, 319–331 (2008)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lavor, C., Liberti, L. & Mucherino, A. The interval Branch-and-Prune algorithm for the discretizable molecular distance geometry problem with inexact distances. J Glob Optim 56, 855–871 (2013). https://doi.org/10.1007/s10898-011-9799-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-011-9799-6