[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The discretizable distance geometry problem

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

We introduce the discretizable distance geometry problem in \({\mathbb{R}^3}\) (DDGP3), which consists in a subclass of instances of the Distance Geometry Problem for which an embedding in \({\mathbb{R}^3}\) can be found by means of a discrete search. We show that the DDGP3 is a generalization of the discretizable molecular distance geometry problem (DMDGP), and we discuss the main differences between the two problems. We prove that the DDGP3 is NP-hard and we extend the Branch & Prune (BP) algorithm, previously used for the DMDGP, for solving instances of the DDGP3. Protein graphs may or may not be in DMDGP and/or DDGP3 depending on vertex orders and edge density. We show experimentally that as distance thresholds decrease, PDB protein graphs which fail to be in the DMDGP still belong to DDGP3, which means that they can still be solved using a discrete search.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Anderson, E., Bai, Z., Dongarra, J., Greenbaum, A., McKenney, A., Du Croz, J., Hammerling, S., Demmel, J., Bischof, C., Sorensen, D.: LAPACK: a Portable Linear Algebra Library for High-Performance Computers. In: Supercomputing ’90: Proceedings of the 1990 ACM/IEEE conference on Supercomputing, pp. 2–11. IEEE Computer Society Press, New York (1990)

  2. 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 Acids Res. 28, 235–242 (2000)

    Article  Google Scholar 

  3. Carvalho R.S., Lavor C., Protti F.: Extending the Geometric Buildup Algorithm for the Molecular Distance Geometry Problem. Inf. Process. Lett. 108, 234–237 (2008)

    Article  Google Scholar 

  4. Coope I.D.: Reliable Computation of the Points of Intersection of n Spheres in n-space. ANZIAM J. 42, 461–477 (2000)

    MathSciNet  Google Scholar 

  5. Crippen G.M., Havel T.F.: Distance Geometry and Molecular Conformation. John Wiley & Sons, New York (1988)

    MATH  Google Scholar 

  6. 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)

  7. Havel T.F.: Distance Geometry. In: Grant, D.M., Harris, R.K. (eds) Encyclopedia of Nuclear Magnetic Resonance, pp. 1701–1710. Wiley, New York (1995)

    Google Scholar 

  8. Huang H.-X., Liang Z-A., Pardalos P.M.: Some Properties for the Euclidean Distance Matrix and Positive Semidefinite Matrix Completion Problem. J. Global Optim. 25(1), 3–21 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  9. Krislock, N.: Semidefinite Facial Reduction for Low-Rank Euclidean Distance Matrix Completion, PhD thesis, University of Waterloo, Waterloo (2010)

  10. Lavor, C., Lee, J., Lee-St. John, A., Liberti, L., Mucherino, A., Sviridenko, M.: Discretization orders for distance geometry problems. Optim. Lett. (2011, in press)

  11. Lavor, C., Liberti, L., Maculan, N.: Discretizable molecular distance geometry problem, Tech. Rep. q-bio.BM/0608012, arXiv (2006)

  12. Lavor C., Liberti L., Maculan N.: Molecular distance geometry problem. In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization, pp. 2305–2311. Springer, New York (2009)

    Google Scholar 

  13. Lavor, C., Liberti, L., Maculan, N., Mucherino, A.: The discretizable molecular distance geometry problem. Comput. Optim. Appl. (2011, in press)

  14. Lavor, C., Liberti, L., Maculan, N., Mucherino, A.: Recent advances on the discretizable molecular distance geometry problem. Eur. J. Oper. Res. (2011, in press)

  15. Lavor, C., Mucherino, A., Liberti, L., Maculan, N.: Computing Artificial Backbones of Hydrogen Atoms in order to Discover Protein Backbones. In: IEEE Conference Proceedings, International Multiconference on Computer Science and Information Technology (IMCSIT09), Workshop on Computational Optimization (WCO09), Mragowo, Poland, pp. 751–756 (2009)

  16. Lavor, C., Mucherino, A., Liberti, L., Maculan, N.: An artificial backbone of hydrogens for finding the conformation of protein molecules. In: Proceedings of the Computational Structural Bioinformatics Workshop (CSBW09), Washington D.C., USA, pp. 152–155 (2009)

  17. Lavor C., Mucherino A., Liberti L., Maculan N.: On the computation of protein backbones by using artificial backbones of hydrogens. J. Global Optim. 50(2), 329–344 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  18. Lavor C., Mucherino A., Liberti L., Maculan N.: Discrete approaches for solving molecular distance geometry problems using NMR data. Int. J. Comput. Biosci. 1(1), 88–94 (2010)

    Google Scholar 

  19. Liberti L., Lavor C., Maculan N.: A Branch-and-Prune algorithm for the molecular distance geometry problem. Int. Trans. Oper. Res. 15(1), 1–17 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  20. Liberti, L., Lavor, C., Mucherino, A.: An exponential algorithm for the discretizable molecular distance geometry problem is polynomial on proteins. In: Proceedings of the 7th International Symposium on Bioinformatics Research and Applications (ISBRA11), Changsha, China (2011)

  21. Liberti L., Lavor C., Mucherino A., Maculan N.: Molecular distance geometry methods: from continuous to discrete. Int. Trans. Oper. Res. 18(1), 33–51 (2010)

    Article  MathSciNet  Google Scholar 

  22. Liu X., Pardalos P.M. et al.: A Tabu based pattern search method for the distance geometry problem. In: Giannessi, F. (eds) New Trends in Mathematical Programming, pp. 223–234. Kluwer Academic Publishers, Dordrecht (1998)

    Google Scholar 

  23. Moré J.J., Wu Z.: Global continuation for distance geometry problems. SIAM J. Optim. 7, 814–836 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  24. Moré J.J., Wu Z.: Distance geometry optimization for protein structures. J. Global Optim. 15, 219–223 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  25. Mucherino, A., Lavor, C.: The Branch and Prune algorithm for the molecular distance geometry problem with inexact distances. In: Proceedings of World Academy of Science, Engineering and Technology (WASET), International Conference on Bioinformatics and Biomedicine (ICBB09), Venice, Italy, pp. 349–353 (2009)

  26. Mucherino, A., Liberti, L., Lavor, C., Maculan, N.: Comparisons between an exact and a MetaHeuristic algorithm for the molecular distance geometry problem. In: ACM Conference Proceedings, Genetic and Evolutionary Computation Conference (GECCO09), Montréal, Canada, pp. 333–340 (2009)

  27. Mucherino A., Lavor C., Liberti L., Maculan N.: On the definition of artificial backbones for the discretizable molecular distance geometry problem. Mathematica Balkanica 23(3–4), 289–302 (2009)

    MathSciNet  MATH  Google Scholar 

  28. Mucherino, A., Lavor, C., Liberti, L., Maculan, N.: Strategies for solving distance geometry problems with inexact distances by discrete approaches. In: Proceedings of Toulouse Global Optimization 2010 (TOGO10), Toulouse, France, pp. 93–96 (2010)

  29. Mucherino, A., Lavor, C., Malliavin, T., Liberti, L., Nilges, M., Maculan, M.: Influence of pruning devices on the solution of molecular distance geometry problems. In: Pardalos, P.M., Rebennack, S. (eds.) Proceedings of the 10th International Symposium on Experimental Algorithms (SEA11), Crete, Greece. Lecture Notes in Computer Science, vol. 6630, pp. 206–217 (2011)

  30. Mucherino, A., Liberti, L., Lavor, C.: MD-jeep: an Implementation of a Branch & Prune Algorithm for Distance Geometry Problems. In: Fukuda, K., et al. (eds.) Proceedings of the Third International Congress on Mathematical Software (ICMS10), Kobe, Japan. Lectures Notes in Computer Science, vol. 6327, pp. 186–197 (2010)

  31. Pardalos, P.M., Shalloway, D., Xue, G. (eds.) (1996) Global Minimization of Nonconvex Energy Functions: Molecular Conformation and Protein Folding. AMS, DIMACS

  32. 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, Monticello, IL, pp. 480–489 (1979)

  33. So M.-C., Ye Y.: Theory of semidefinite programming for sensor network localization. Math. Program. 109, 367–384 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  34. Wu D., Wu Z.: An updated geometric build-up algorithm for solving the molecular distance geometry problem with sparse distance Data. J. Global Optim. 37, 661–673 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  35. Wu D., Wu Z., Yuan Y.: Rigid versus unique determination of protein structures with geometric buildup. Optim. Lett. 2, 319–331 (2008)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CERFACS, Toulouse, France

    A. Mucherino

  2. Department of Applied Mathematics (IMECC-UNICAMP), State University of Campinas, Campinas, SP, Brazil

    C. Lavor

  3. LIX, École Polytechnique, Palaiseau, France

    L. Liberti

Authors
  1. A. Mucherino
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. C. Lavor
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. L. Liberti
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A. Mucherino.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mucherino, A., Lavor, C. & Liberti, L. The discretizable distance geometry problem. Optim Lett 6, 1671–1686 (2012). https://doi.org/10.1007/s11590-011-0358-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-011-0358-3

Keywords

Search

Navigation