American Institute of Mathematical Sciences

2011, 1(1): 191-209. doi: 10.3934/naco.2011.1.191

Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction

 1 Dept. of Computer Science, Faculty of Computers and Information, Assiut University, Assiut 71526 2 Department of Mathematics, Faculty of Science, Assiut University, Assiut, 71516, Egypt 3 Department of Information Systems, Faculty of Computers and Information, Assiut University, Assiut, 71526, Egypt

Received  October 2010 Revised  November 2010 Published  February 2011

The search for the global minimum of a potential energy function is very difficult since the number of local minima grows exponentially with the molecule size. The present work proposes the application of genetic algorithm and tabu search methods, which are called GAMCP (Genetic Algorithm with Matrix Coding Partitioning) [7], and TSVP (Tabu Search with Variable Partitioning) [8], respectively, for minimizing the molecular potential energy function. Computational results for problems with up to 200 degrees of freedom are presented and are favorable compared with other four existing methods from the literature. Numerical results show that the proposed two methods are promising and produce high quality solutions with low computational costs.
Citation: Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191
References:
 [1] H. J. C. Barbosa, C. Lavor and F. M. Raupp, A GA-simplex hybrid algorithm for global minimization of molecular potential energy function,, Annals of Operations Research, 138 (2005), 189.  doi: 10.1007/s10479-005-2453-2.  Google Scholar [2] M. Dražić, C. Lavor, N. Maculan and N. Mladenović, A continuous variable neighborhood search heuristic for finding the three-dimensional structure of a molecule,, European Journal of Operational Research, 185 (2008), 1265.  doi: 10.1016/j.ejor.2006.06.052.  Google Scholar [3] C. A. Floudas, J. L. Klepeis and P. M. Pardalos, Global optimization approaches in protein folding and peptide docking, , DIMACS Series in Discrete Metjematics and Theoretical Computer Science, (1999).   Google Scholar [4] S. Garcia, A. Fernandez, J. Luengo and F. Herrera, A study of statistical techniques and performance measures for genetics-based machine learning, accuracy and interpretability,, Soft Computing, 13 (2009), 959.  doi: 10.1007/s00500-008-0392-y.  Google Scholar [5] A. Hedar, B. T. Ong and M. Fukushima, "Genetic algorithms with automatic accelerated termination,", Technical Report 2007-002, (2007), 2007.   Google Scholar [6] A. Hedar, B. T. Ong and M. Fukushima, Genetic algorithms combined with accelerated mutation and automatic termination,, Submitted to Soft Computing., ().   Google Scholar [7] A. Hedar and A. F. Ali, Genetic algorithm with population partitioning and space reduction for high dimensional problems,, International Conference on Computer Engineering $&$ Systems, (2009), 14.   Google Scholar [8] A. Hedar and A. F. Ali, Tabu Search with variable partitioning for high dimensional problems,, The 7th International Conference on Informatics and Systems, (2010), 28.   Google Scholar [9] F. Herrera, M. Lozano and J. L. Verdegay, Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis,, Artificial Intelligence Review, 12 (1998), 265.  doi: 10.1023/A:1006504901164.  Google Scholar [10] V. Kovačević-Vujčić, M. čangalović, M. Dražić and N. Mladenović, VNS-based heuristics for continuous global optimization,, In:L.T. Hoai An, (2004), 215.   Google Scholar [11] C. Lavor and N. Maculan, A function to test methods applied to global minimization of potential energy of molecules,, Numerical Algorithms, 35 (2004), 287.  doi: 10.1023/B:NUMA.0000021763.84725.b9.  Google Scholar [12] N. Mladenović, J. Petrović, V. Kovačević and M. čangalović, Solving spread spectrum radar ployphase code design problem by tabu search and variable nieghbourhood search,, European Journal of Operational Research, 151 (2003), 389.  doi: 10.1016/S0377-2217(02)00833-0.  Google Scholar [13] P. M. Pardalos, D. Shalloway and G. L. Xue, Optimization methods for computing global minima of nonconvex potential energy function,, Journal of Global Optimization, 4 (1994), 117.  doi: 10.1007/BF01096719.  Google Scholar [14] A. Pogorelov, "Geometry, Mir Publishers,", Moscow, (1987).   Google Scholar [15] D. J. Sheskin, "Handbook of Parametric and Nonparametric Statistical Procedures,", CRC Press, (2003).  doi: 10.1201/9781420036268.  Google Scholar [16] D. J. Wales, H. A. Scheraga, Global optimization of clusters, crystals and biomolecules,, Science, 285 (1999), 1368.  doi: 10.1126/science.285.5432.1368.  Google Scholar [17] J. H. Zar, "Biostatistical Analysis,", Prentice Hall, (1999).   Google Scholar

show all references

References:
 [1] H. J. C. Barbosa, C. Lavor and F. M. Raupp, A GA-simplex hybrid algorithm for global minimization of molecular potential energy function,, Annals of Operations Research, 138 (2005), 189.  doi: 10.1007/s10479-005-2453-2.  Google Scholar [2] M. Dražić, C. Lavor, N. Maculan and N. Mladenović, A continuous variable neighborhood search heuristic for finding the three-dimensional structure of a molecule,, European Journal of Operational Research, 185 (2008), 1265.  doi: 10.1016/j.ejor.2006.06.052.  Google Scholar [3] C. A. Floudas, J. L. Klepeis and P. M. Pardalos, Global optimization approaches in protein folding and peptide docking, , DIMACS Series in Discrete Metjematics and Theoretical Computer Science, (1999).   Google Scholar [4] S. Garcia, A. Fernandez, J. Luengo and F. Herrera, A study of statistical techniques and performance measures for genetics-based machine learning, accuracy and interpretability,, Soft Computing, 13 (2009), 959.  doi: 10.1007/s00500-008-0392-y.  Google Scholar [5] A. Hedar, B. T. Ong and M. Fukushima, "Genetic algorithms with automatic accelerated termination,", Technical Report 2007-002, (2007), 2007.   Google Scholar [6] A. Hedar, B. T. Ong and M. Fukushima, Genetic algorithms combined with accelerated mutation and automatic termination,, Submitted to Soft Computing., ().   Google Scholar [7] A. Hedar and A. F. Ali, Genetic algorithm with population partitioning and space reduction for high dimensional problems,, International Conference on Computer Engineering $&$ Systems, (2009), 14.   Google Scholar [8] A. Hedar and A. F. Ali, Tabu Search with variable partitioning for high dimensional problems,, The 7th International Conference on Informatics and Systems, (2010), 28.   Google Scholar [9] F. Herrera, M. Lozano and J. L. Verdegay, Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis,, Artificial Intelligence Review, 12 (1998), 265.  doi: 10.1023/A:1006504901164.  Google Scholar [10] V. Kovačević-Vujčić, M. čangalović, M. Dražić and N. Mladenović, VNS-based heuristics for continuous global optimization,, In:L.T. Hoai An, (2004), 215.   Google Scholar [11] C. Lavor and N. Maculan, A function to test methods applied to global minimization of potential energy of molecules,, Numerical Algorithms, 35 (2004), 287.  doi: 10.1023/B:NUMA.0000021763.84725.b9.  Google Scholar [12] N. Mladenović, J. Petrović, V. Kovačević and M. čangalović, Solving spread spectrum radar ployphase code design problem by tabu search and variable nieghbourhood search,, European Journal of Operational Research, 151 (2003), 389.  doi: 10.1016/S0377-2217(02)00833-0.  Google Scholar [13] P. M. Pardalos, D. Shalloway and G. L. Xue, Optimization methods for computing global minima of nonconvex potential energy function,, Journal of Global Optimization, 4 (1994), 117.  doi: 10.1007/BF01096719.  Google Scholar [14] A. Pogorelov, "Geometry, Mir Publishers,", Moscow, (1987).   Google Scholar [15] D. J. Sheskin, "Handbook of Parametric and Nonparametric Statistical Procedures,", CRC Press, (2003).  doi: 10.1201/9781420036268.  Google Scholar [16] D. J. Wales, H. A. Scheraga, Global optimization of clusters, crystals and biomolecules,, Science, 285 (1999), 1368.  doi: 10.1126/science.285.5432.1368.  Google Scholar [17] J. H. Zar, "Biostatistical Analysis,", Prentice Hall, (1999).   Google Scholar
 [1] Bo Chen, Youde Wang. Global weak solutions for Landau-Lifshitz flows and heat flows associated to micromagnetic energy functional. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020268 [2] Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115 [3] Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169 [4] Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $(n, m)$-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117 [5] Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031 [6] Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076 [7] Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082 [8] Jianhua Huang, Yanbin Tang, Ming Wang. Singular support of the global attractor for a damped BBM equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020345 [9] Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020158 [10] Cheng He, Changzheng Qu. Global weak solutions for the two-component Novikov equation. Electronic Research Archive, 2020, 28 (4) : 1545-1562. doi: 10.3934/era.2020081 [11] Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243 [12] Mengni Li. Global regularity for a class of Monge-Ampère type equations with nonzero boundary conditions. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020267

Impact Factor: