Skip to main content
SpringerLink
Log in

A Custom Bio-Inspired Algorithm for the Molecular Distance Geometry Problem

  • Conference paper
  • First Online:
Intelligent Systems (BRACIS 2023)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 14195))

Included in the following conference series:

  • 211 Accesses

Abstract

Protein structure allows for an understanding of its function and enables the evaluation of possible interactions with other proteins. The molecular distance geometry problem (MDGP) regards determining a molecule’s three-dimensional (3D) structure based on the known distances between some pairs of atoms. An important application consists in finding 3D protein arrangements through data obtained by nuclear magnetic resonance (NMR). This work presents a study concerning the discretized version of the MDGP and the viability of employing genetic algorithms (GAs) to look for optimal solutions. We present computational results for input instances whose sizes varied from 10 to \(10^3\) atoms. The results obtained show that approaches to solving the discrete version of the MDGP based on GAs are promising.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    Instance set is publicly available in: https://bit.ly/3d0ezzo.

  2. 2.

    The set of instances is available in https://www.rcsb.org/.

References

  1. Berman, H.M., et al.: The protein data bank. Nucleic Acids Res. 28(1), 235–242 (2000)

    Article  Google Scholar 

  2. Biswas, P., Toh, K.C., Ye, Y.: A distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation. SIAM J. Sci. Comput. 30(3), 1251–1277 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  3. Carneiro, S., Souza, M., Filho, N., Tarrataca, L., Rosa, J., Assis, L.: Algoritmo genético aplicado ao problema da geometria de distâncias moleculares. In: Anais do LII Simpósio Brasileiro de Pesquisa Operacional (2020)

    Google Scholar 

  4. Creighton, T.E.: Proteins: Structures and Molecular Properties. Macmillan (1993)

    Google Scholar 

  5. Cucuringu, M., Singer, A., Cowburn, D.: Eigenvector synchronization, graph rigidity and the molecule problem. Inf. Infer. J. IMA 1(1), 21–67 (2012)

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  7. Goldberg, D.E.: Genetic Algorithms in Search. Optimization, and Machine Learning (1989)

    Google Scholar 

  8. Goncalves, D.S., Lavor, C., Liberti, L., Souza, M.: A new algorithm for the \(^k\)dmdgp subclass of distance geometry problems (2020)

    Google Scholar 

  9. Gong, Y.J., et al.: Distributed evolutionary algorithms and their models: a survey of the state-of-the-art. Appl. Soft Comput. 34, 286–300 (2015)

    Article  Google Scholar 

  10. Hendrickson, B.: The molecule problem: exploiting structure in global optimization. SIAM J. Optim. 5(4), 835–857 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  11. Lavor, C., Liberti, L., Maculan, N., Mucherino, A.: The discretizable molecular distance geometry problem. Comput. Optim. Appl. 52(1), 115–146 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  12. Leung, N.H.Z., Toh, K.C.: An SDP-based divide-and-conquer algorithm for large-scale noisy anchor-free graph realization. SIAM J. Sci. Comput. 31(6), 4351–4372 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  13. Liberti, L., Lavor, C., Maculan, N., Marinelli, F.: Double variable neighbourhood search with smoothing for the molecular distance geometry problem. J. Global Optim. 43(2–3), 207–218 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  14. 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, pp. 47–60. Springer, New York (2013). https://doi.org/10.1007/978-1-4614-5128-0_3

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

    Article  MathSciNet  MATH  Google Scholar 

  16. Maculan Filho, N., Lavor, C.C., de Souza, M.F., Alves, R.: Álgebra e Geometria no Cálculo de Estrutura Molecular. Colóquio Brasileiro de Matemática, IMPA (2017)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  19. Mucherino, A., Lavor, C., Liberti, L.: The discretizable distance geometry problem. Optim. Lett. 6(8), 1671–1686 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  20. Mucherino, A., Lavor, C., Liberti, L.: Exploiting symmetry properties of the discretizable molecular distance geometry problem. J. Bioinform. Comput. Biol. 10(03), 1242009 (2012)

    Article  MATH  Google Scholar 

  21. Mucherino, A., Liberti, L., Lavor, C.: MD-jeep: an implementation of a branch and prune algorithm for distance geometry problems. In: Fukuda, K., Hoeven, J., Joswig, M., Takayama, N. (eds.) ICMS 2010. LNCS, vol. 6327, pp. 186–197. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15582-6_34

    Chapter  Google Scholar 

  22. Mulati, M.H., Constantino, A.A., da Silva, A.F.: Otimização por colônia de formigas. In: Lopes, H.S., de Abreu Rodrigues, L.C., Steiner, M.T.A. (eds.) Meta-Heurísticas em Pesquisa Operacional, 1 edn., Chap. 4, pp. 53–68. Omnipax, Curitiba, PR (2013)

    Google Scholar 

  23. Nobile, M.S., Citrolo, A.G., Cazzaniga, P., Besozzi, D., Mauri, G.: A memetic hybrid method for the molecular distance geometry problem with incomplete information. In: 2014 IEEE Congress on Evolutionary Computation (CEC), pp. 1014–1021. IEEE (2014)

    Google Scholar 

  24. Schlick, T.: Molecular Modeling and Simulation: An Interdisciplinary Guide: An Interdisciplinary Guide, vol. 21. Springer, New York (2010). https://doi.org/10.1007/978-1-4419-6351-2

  25. Sit, A., Wu, Z.: Solving a generalized distance geometry problem for protein structure determination. Bull. Math. Biol. 73(12), 2809–2836 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  26. Souza, M., Gonçalves, D.S., Carvalho, L.M., Lavor, C., Liberti, L.: A new algorithm for a class of distance geometry problems. In: 18th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (2020)

    Google Scholar 

  27. Yang, X.S.: Engineering Optimization: An Introduction with Metaheuristic Applications. Wiley (2010)

    Google Scholar 

Download references

Acknowledgements

Douglas O. Cardoso acknowledges the financial support by the Foundation for Science and Technology (Fundação para a Ciência e a Tecnologia, FCT) through grant UIDB/05567/2020, and by the European Social Fund and programs Centro 2020 and Portugal 2020 through project CENTRO-04-3559-FSE-000158.

Author information

Authors and Affiliations

  1. Celso Suckow da Fonseca Federal Center of Technological Education, Rio de Janeiro, RJ, Brazil

    Sarah Ribeiro Lisboa Carneiro, Luís Tarrataca & Laura S. Assis

  2. Department of Statistics and Applied Mathematics, Federal University of Ceará, Fortaleza, Ceará, Brazil

    Michael Ferreira de Souza

  3. Smart Cities Research Center, Polytechnic Institute of Tomar, Tomar, Portugal

    Douglas O. Cardoso

Authors
  1. Sarah Ribeiro Lisboa Carneiro
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael Ferreira de Souza
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Douglas O. Cardoso
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Luís Tarrataca
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Laura S. Assis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Laura S. Assis .

Editor information

Editors and Affiliations

  1. Federal University of São Carlos, São Carlos, Brazil

    Murilo C. Naldi

  2. Centro Universitario da FEI, São Bernardo do Campo, Brazil

    Reinaldo A. C. Bianchi

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Carneiro, S.R.L., de Souza, M.F., Cardoso, D.O., Tarrataca, L., Assis, L.S. (2023). A Custom Bio-Inspired Algorithm for the Molecular Distance Geometry Problem. In: Naldi, M.C., Bianchi, R.A.C. (eds) Intelligent Systems. BRACIS 2023. Lecture Notes in Computer Science(), vol 14195. Springer, Cham. https://doi.org/10.1007/978-3-031-45368-7_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-45368-7_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-45367-0

  • Online ISBN: 978-3-031-45368-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation