Double variable neighbourhood search with smoothing for the molecular distance geometry problem | Journal of Global Optimization Skip to main content
Springer Nature Link
Log in

Double variable neighbourhood search with smoothing for the molecular distance geometry problem

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

We discuss the geometrical interpretation of a well-known smoothing operator applied to the Molecular Distance Geometry Problem (MDGP), and we then describe a heuristic approach based on Variable Neighbourhood Search on the smoothed and original problem. This algorithm often manages to find solutions having higher accuracy than other methods. This is important as small differences in the objective function value may point to completely different 3D molecular structures.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Crippen G.M. and Havel T.F. (1988). Distance Geometry and Molecular Conformation. Wiley, New York

    Google Scholar 

  2. Cruz I.F. and Twarog J.P.  (1996). 3D graph drawing with simulated annealing. In: Brandenburg, F.-J. (eds) 3D Graph Drawing – GD95 Proceedings, LNCS, vol. 1027, pp 162–165. Springer, Berlin

    Google Scholar 

  3. Dong Q. and Wu Z. (2002). A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances. J. Global Optim. 22: 365–375

    Article  Google Scholar 

  4. Dražić, M., Lavor, C., Maculan, N., Mladenović, N.: A continuous variable neighbourhood search heuristic for finding the tridimensional structure of a molecule. Eur. J. Oper. Res. (to appear)

  5. 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. IEEE Infocom Proc. pp. 2673–2684 (2004)

  6. Gill, P.E.: User’s Guide for SNOPT 5.3. Systems Optimization Laboratory, Department of EESOR, Stanford University, California, February 1999

  7. Klepeis J.L., Floudas C.A., Morikis D. and Lambris J.D. (1999). Predicting peptide structures using NMR data and deterministic global optimization. J. Comput. Chem. 20(13): 1354–1370

    Article  Google Scholar 

  8. Lavor, C.: On generating instances for the molecular distance geometry problem. In Liberti, and Maculan [13], pp. 405–414

  9. Lavor C., Liberti L. and Maculan N. (2006). Computational experience with the molecular distance geometry problem. In: Pintér, J. (eds) Global Optimization: Scientific and Engineering Case Studies., pp 213–225. Springer, Berlin

    Google Scholar 

  10. Lavor, C., Liberti, L., Maculan, N.: An overview of distinct approaches for the molecular distance geometry problem. In: Floudas, C.A., Pardalos, P. (eds.), Encyclopedia of Optimization, 2nd edn, Springer (to appear)

  11. Liberti L. and Dražic M. (2005). Variable neighbourhood search for the global optimization of constrained NLPs. In Proceedings of GO Workshop, Almeria, Spain

    Google Scholar 

  12. Liberti, L., Lavor, C., Maculan, N.: The discretizable molecular distance geometry problem. arXiv: q-bio/0608012, 2006.

  13. (2006). Global Optimization: From Theory to Implementation. Springer, Berlin

    Google Scholar 

  14. Liberti L., Tsiakis P., Keeping B. and Pantelides C.C. (2001). \(oo{\mathcal OPS}\). Centre for Process Systems Engineering Chemical Engineering Department, Imperial College, London, UK

    Google Scholar 

  15. Moré J.J. and Wu Z. (1997). Global continuation for distance geometry problems. Siam J. Optim. 7(3): 814–846

    Article  Google Scholar 

  16. Moré J.J. and Wu Z. (1999). Distance geometry optimization for protein structures. J. Global Optim. 15: 219–234

    Article  Google Scholar 

  17. Neumaier A. (1997). Molecular modeling of proteins and mathematical prediction of protein structure. SIAM Rev. 39: 407–460

    Article  Google Scholar 

  18. Phillips A.T., Rosen J.B., Walke V.H.: Molecular structure determination by convex underestimation of local energy minima. In: Pardalos P.M., Shalloway D., Xue G. (eds) Global Minimization of Nonconvex Energy Functions: Molecular Conformation and Protein Folding, vol 23, pp. 181–198 American Mathematical Society, Providence (1996)

  19. Saxe, J.B.: Embeddability of weighted graphs in k-space is strongly NP-hard. Proceedings of 17th Allerton Conference in Communications, Control and Computing, vol. 23; pp. 480–489 (1979)

  20. Yoon J.-M., Gad Y. and Wu Z. (2000). Mathematical modeling of protein structure using distance geometry. Technical Report TR00-24, Dept. Comput. Applied Maths, Rice University, Houston

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. École Polytechnique, LIX, Palaiseau, 91128, France

    Leo Liberti & Fabrizio Marinelli

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

    Carlile Lavor

  3. COPPE – Systems Engineering, Federal University of Rio de Janeiro, P.O. Box 68511, Rio de Janeiro-RJ, 21941-972, Brazil

    Nelson Maculan

Authors
  1. Leo Liberti
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Carlile Lavor
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Nelson Maculan
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Fabrizio Marinelli
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Leo Liberti.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liberti, L., Lavor, C., Maculan, N. et al. Double variable neighbourhood search with smoothing for the molecular distance geometry problem. J Glob Optim 43, 207–218 (2009). https://doi.org/10.1007/s10898-007-9218-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-007-9218-1

Keywords