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
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
Instance set is publicly available in: https://bit.ly/3d0ezzo.
- 2.
The set of instances is available in https://www.rcsb.org/.
References
Berman, H.M., et al.: The protein data bank. Nucleic Acids Res. 28(1), 235–242 (2000)
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)
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)
Creighton, T.E.: Proteins: Structures and Molecular Properties. Macmillan (1993)
Cucuringu, M., Singer, A., Cowburn, D.: Eigenvector synchronization, graph rigidity and the molecule problem. Inf. Infer. J. IMA 1(1), 21–67 (2012)
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)
Goldberg, D.E.: Genetic Algorithms in Search. Optimization, and Machine Learning (1989)
Goncalves, D.S., Lavor, C., Liberti, L., Souza, M.: A new algorithm for the \(^k\)dmdgp subclass of distance geometry problems (2020)
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)
Hendrickson, B.: The molecule problem: exploiting structure in global optimization. SIAM J. Optim. 5(4), 835–857 (1995)
Lavor, C., Liberti, L., Maculan, N., Mucherino, A.: The discretizable molecular distance geometry problem. Comput. Optim. Appl. 52(1), 115–146 (2012)
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)
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)
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
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)
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)
Moré, J.J., Wu, Z.: Global continuation for distance geometry problems. SIAM J. Optim. 7(3), 814–836 (1997)
Moré, J.J., Wu, Z.: Distance geometry optimization for protein structures. J. Global Optim. 15(3), 219–234 (1999)
Mucherino, A., Lavor, C., Liberti, L.: The discretizable distance geometry problem. Optim. Lett. 6(8), 1671–1686 (2012)
Mucherino, A., Lavor, C., Liberti, L.: Exploiting symmetry properties of the discretizable molecular distance geometry problem. J. Bioinform. Comput. Biol. 10(03), 1242009 (2012)
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
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)
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)
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
Sit, A., Wu, Z.: Solving a generalized distance geometry problem for protein structure determination. Bull. Math. Biol. 73(12), 2809–2836 (2011)
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)
Yang, X.S.: Engineering Optimization: An Introduction with Metaheuristic Applications. Wiley (2010)
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
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
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)