›› 2013, Vol. 28 ›› Issue (5): 868-889.doi: 10.1007/s11390-013-1384-7

Special Issue: Artificial Intelligence and Pattern Recognition

• Regular Paper • Previous Articles     Next Articles

Comparative Analysis of Different Evaluation Functions for Protein Structure Prediction Under the HP Model

Mario Garza-Fabre, Eduardo Rodriguez-Tello, and Gregorio Toscano-Pulido   

  1. Information Technology Laboratory, CINVESTAV-Tamaulipas, Km. 5.5 Carretera Ciudad Victoria-Soto La Marina 87130, Ciudad Victoria, Tamaulipas, México
  • Received:2013-01-11 Revised:2013-03-27 Online:2013-09-05 Published:2013-09-05
  • Supported by:

    This research was partially supported by the National Council of Science and Technology of Méexico (CONACyT) under Grant Nos. 105060 and 99276.

The HP model for protein structure prediction abstracts the fact that hydrophobicity is a dominant force in the protein folding process. This challenging combinatorial optimization problem has been widely addressed through metaheuristics. The evaluation function is a key component for the success of metaheuristics; the poor discrimination of the conventional evaluation function of the HP model has motivated the proposal of alternative formulations for this component. This comparative analysis inquires into the effectiveness of seven different evaluation functions for the HP model. The degree of discrimination provided by each of the studied functions, their capability to preserve a rank ordering among potential solutions which is consistent with the original objective of the HP model, as well as their effect on the performance of local search methods are analyzed. The obtained results indicate that studying alternative evaluation schemes for the HP model represents a highly valuable direction which merits more attention.

[1] Anfinsen C. Principles that govern the folding of protein chains. Science, 1973, 181(4096): 223-230.

[2] Chandru V, DattaSharma A, Kumar V. The algorithmics of folding proteins on lattices. Discrete Applied Mathematics, 2003, 127(1): 145-161.

[3] Kolinski A, Skolnick J. Reduced models of proteins and their applications. Polymer, 2004, 45(2): 511-524.

[4] Hart W, Newman A. Protein structure prediction with lattice models. In Handbook of Computational Molecular Biology, Chapman & Hall/CRC, 2005.

[5] Clementi C. Coarse-grained models of protein folding: Toy models or predictive tools? Current Opinion in Structural Biology, 2008, 18(1): 10-15.

[6] Pierri C, De Grassi A, Turi A. Lattices for ab initio protein structure prediction. Proteins: Structure, Function, and Bioinformatics, 2008, 73(2): 351-361.

[7] Dill K A. Theory for the folding and stability of globular proteins. Biochemistry, 1985, 24(6): 1501-1509.

[8] Lau K, Dill K A. A lattice statistical mechanics model of the conformational and sequence spaces of proteins. Macromolecules, 1989, 22(10): 3986-3997.

[9] Berger B, Leighton T. Protein folding in the hydrophobichydrophilic (HP) model is NP-complete. In Proc. International Conference on Research in Computational Molecular Biology, March 1998, pp.30-39.

[10] Crescenzi P, Goldman D, Papadimitriou C et al. On the complexity of protein folding. In Proc. the 30th ACM Symposium on Theory of Computing, May 1998, pp.597-603.

[11] Stadler P F. Correlation in landscapes of combinatorial optimization problems. Europhysics Letters, 1992, 20(6): 479482.

[12] Hoos H, StÄutzle T. Stochastic Local Search: Foundations And Applications. Morgan Kaufmann, 2004.

[13] Pitzer E, Affenzeller M. A comprehensive survey on fitness landscape analysis. In Studies in Computational Intelligence 378, Fodor J, Klempous R, Araéujo C (eds.), Springer, 2012, pp.161-191.

[14] Krasnogor N, Hart W, Smith J et al. Protein structure prediction with evolutionary algorithms. In Proc. Conf. Genetic and Evolutionary Computation, July 1999, pp.1569-1601.

[15] Custéodio F, Barbosa H, Dardenne L. Investigation of the three-dimensional lattice HP protein folding model using a genetic algorithm. Genetics and Molecular Biology, 2004, 27(4): 611-615.

[16] Lopes H, Scapin M. An Enhanced genetic algorithm for protein structure prediction using the 2D hydrophobic-polar model. In Proc. the 7th Int. Conf. Artificial Evolution, October 2005, pp.238-246.

[17] Berenboym I, Avigal M. Genetic algorithms with local search optimization for protein structure prediction problem. In Proc. the 10th Conference Genetic and Evolutionary Computation, July 2008, pp.1097-1098.

[18] Cebriéan M, Dotéu I, Van Hentenryck P, Clote P. Protein structure prediction on the face centered cubic lattice by local search. In Proc. the 23rd Conference on Artificial Intelligence, July 2008, Vol.1, pp.241-246.

[19] Islam M, Chetty M. Novel memetic algorithm for protein structure prediction. In Lecture Notes in Computer Science 5866, Nicholson A, Li X (eds.), Springer Berlin/Heidelberg, 2009, pp.412-421.

[20] Garza-Fabre M, Rodriguez-Tello E, Toscano-Pulido G. Comparing alternative energy functions for the HP model of protein structure prediction. In Proc. IEEE Congress on Evolutionary Computation, June 2011, pp.2307-2314.

[21] Khimasia M, Coveney P. Protein structure prediction as a hard optimization problem: The genetic algorithm approach. Molecular Simulation, 1997, 19(4): 205-226.

[22] Cotta C. Protein structure prediction using evolutionary algorithms hybridized with backtracking. In Lecture Notes in Computer Science 2687, Mira J, Alvarez J (eds.), Springer Berlin/Heidelberg, 2003, pp.321-328.

[23] Bui T, Sundarraj G. An effcient genetic algorithm for predicting protein tertiary structures in the 2D HP model. In Proc. Conf. Genetic and Evolutionary Computation, June 2005, pp.385-392.

[24] Hoque M, Chetty M, Lewis A, Sattar A. Twin removal in genetic algorithms for protein structure prediction using lowresolution model. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2011, 8(1): 234-245.

[25] Krasnogor N, Blackburne B, Burke E, Hirst J. Multimeme algorithms for protein structure prediction. In Proc. the 7th International Conference on Parallel Problem Solving from Nature, September 2002, pp.769-778.

[26] Islam M, Chetty M. Clustered memetic algorithm for protein structure prediction. In Proc. IEEE Congress on Evolutionary Computation, July 2010, pp.1-8.

[27] Zhang X, Wang T, Luo H, Yang J, Deng Y, Tang J, Yang M. 3D protein structure prediction with genetic tabu search algorithm. BMC Systems Biology, 2010, 4(Suppl. 1): S6.

[28] Chira C. A hybrid evolutionary approach to protein structure prediction with lattice models. In Proc. IEEE Congress on Evolutionary Computation, June 2011, pp.2300-2306.

[29] Chira C, Horvath D, Dumitrescu D. Hill-climbing search and diversification within an evolutionary approach to protein structure prediction. BioData Mining, 2011, 4: Article No.8.

[30] Blazewicz J, Lukasiak P, Milostan M. Application of tabu search strategy for finding low energy structure of protein. Artificial Intelligence in Medicine, 2005, 35(1/2): 135-145.

[31] Pardalos P, Liu X, Xue G. Protein conformation of a lattice model using tabu search. Journal of Global Optimization, 1997, 11(1): 55-68.

[32] Shmygelska A, Hoos H. An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem. BMC Bioinformatics, 2005, 6: Article No.30.

[33] Chu D, Till M, Zomaya A. Parallel ant colony optimization for 3D protein structure prediction using the HP lattice model. In Proc. the 19th IEEE International Parallel and Distributed Processing Symposium, April 2005, Vol.7, p.193b.

[34] Hu X M, Zhang J, Li Y. Flexible protein folding by ant colony optimization. In Studies in Computational Intelligence 151, Smolinski T G, Milanova M G, Hassgnien A (eds.), Springer, 2008, pp.317-336.

[35] Guo H, Lv Q, Wu J, Huang X, Qian P. Solving 2D HP protein folding problem by parallel ant colonies. In Proc. the 2nd International Conference on Biomedical Engineering and Informatics, October 2009, pp.1-5.

[36] De Almeida C, Gon籧alves R, Delgado M. A hybrid immunebased system for the protein folding problem. In Proc. the 7th Evolutionary Computation in Combinatorial Optimization, April 2007, pp.13-24.

[37] Cutello V, Morelli G, Nicosia G, Pavone M. Immune algorithms with aging operators for the string folding problem and the protein folding problem. In Proc. the 5th European Conf. Evolutionary Computation in Combinatorial Optimization, April 2005, pp.80-90.

[38] Cutello V, Nicosia G, Pavone M et al. An immune algorithm for protein structure prediction on lattice models. IEEE Trans. Evolutionary Computation, 2007, 11(1): 101-117.

[39] Cutello V, Morelli G, Nicosia G, Pavone M, Scollo G. On discrete models and immunological algorithms for protein structure prediction. Natural Computing, 2011, 10(1): 91-102.

[40] Kanj F, Mansour N, Khachfe H, Abu-Khzam F. Protein structure prediction in the 3D HP model. In Proc. IEEE/ACS International Conference on Computer Systems and Applications, May 2009, pp.732-736.

[41] B?utu A, Luchian H. Protein structure prediction in lattice models with particle swarm optimization. In Proc. the 7th Int. Conf. Swarm Intelligence, Sept. 2010, pp.512-519.

[42] Bitello R, Lopes H. A differential evolution approach for protein folding. In Proc. IEEE Symp. Computational Intelligence, Bioinformatics and Computational Biology, Sept. 2006, pp.1-5.

[43] Lopes H, Bitello R. A differential evolution approach for protein folding using a lattice model. Journal of Computer Science and Technology, 2007, 22(6): 904-908.

[44] Santos J, Diéeguez M. Differential evolution for protein structure prediction using the HP model. In Lecture Notes in Computer Science 6686, Ferréandez J M, Séanchez J R éA, Paz F (eds.), 2011, pp.323-333.

[45] Jana N, Sil J. Protein structure prediction in 2D HP lattice model using differential evolutionary algorithm. In Proc. the Int. Conf. Information Systems Design and Intelligent Applications, January 2012, pp.281-290.

[46] Santana R, Larranaga P, Lozano J A. Protein folding in simplified models with estimation of distribution algorithms. IEEE Trans. Evolutionary Computation, 2008, 12(4): 418438.

[47] Chen B, Li L, Hu J. A novel EDAs based method for hp model protein folding. In Proc. IEEE Congress on Evolutionary Computation, May 2009, pp.309-315.

[48] Unger R, Moult J. Genetic algorithms for protein folding simulations. Journal of Molecular Biology, 1993, 231(1): 75-81.

[49] Patton A, Punch III W, Goodman E. A standard GA approach to native protein conformation prediction. In Proc. the 6th Int. Conf. Genetic Algorithms, July 1995, pp.574581.

[50] Lopes H, Scapin M. A hybrid genetic algorithm for the protein folding problem using the 2D-HP lattice model. In Studies in Computational Intelligence 92, Yang A, Shan Y, Bui L (eds.), Springer, 2008, pp.121-140.

[51] Dotéu I, Cebriéan M, Van Hentenryck P, Clote P. On lattice protein structure prediction revisited. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2011, 8(6): 1620-1632.

[52] Islam M, Chetty M, Murshed M. Novel local improvement techniques in clustered memetic algorithm for protein structure prediction. In Proc. IEEE Congress on Evolutionary Computation, June 2011, pp.1003-1011.

[53] Zhang J, Kou S C, Liu J S. Biopolymer structure simulation and optimization via fragment regrowth Monte Carlo. The Journal of Chemical Physics, 2007, 126(22): 225101.

[54] Thachuk C, Shmygelska A, Hoos H. A replica exchange Monte Carlo algorithm for protein folding in the HP model. BMC Bioinformatics, 2007, 8: 342.

[55] WÄust T, Li Y W, Landau D P. Unraveling the beautiful complexity of simple lattice model polymers and proteins using Wang-Landau sampling. Journal of Statistical Physics, 2011, 144(3): 638-651.

[56] Corne D, Knowles J. Techniques for highly multiobjective optimisation: Some nondominated points are better than others. In Proc. the 9th Conf. Genetic and Evolutionary Computation, Volume 1, July 2007, pp.773-780.

[57] Blum C, Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 2003, 35(3): 268-308.

[58] Talbi E. Metaheuristics: From Design to Implementation. Wiley Publishing, 2009.

[59] Martin O, Otto S, Felten E. Large-step Markov chains for the traveling salesman problem. Complex Systems, 1991, 5(3): 299-326.

[60] Lourenço H, Martin O, StÄutzle T. Iterated local search. In International Series in Operations Research & Management Science 57, Glover F, Kochenberger G (eds.), Kluwer Academic Publishers, 2002, pp.321-353.

[61] Lourenço H, Martin O, StÄutzle T. Iterated local search: Framework and applications. In International Series in Operations Research & Management Science 146, Gendreau M, Potvin J Y (eds.), Springer, 2010, pp.363-397.

[62] Vanneschi L, Tomassini M, Collard P, Véerel S, Pirola Y, Mauri G. A comprehensive view of fitness landscapes with neutrality and fitness clouds. In Proc. the 10th European Conf. Genetic Programming, April 2007, pp.241-250.

[63] Collard P, Clergue M, Defoin-Platel M. Synthetic neutrality for artificial evolution. In Proc. the 4th European Conf. Artificial Evolution, November 1999, pp.254-265.

[64] Yu T, Miller J. Finding needles in haystacks is not hard with neutrality. In Proc. the 5th European Conf. Genetic Programming, April 2002, pp.13-25.

[65] Véerel S, Collard P, Clergue M. Scuba search: When selection meets innovation. In Proc. IEEE Congress on Evolutionary Computation, June 2004, pp.924-931.

[66] Marmion M, Dhaenens C, Jourdan L, Liefooghe A, Véerel S. On the neutrality of flowshop scheduling fitness landscapes. In Lecture Notes in Computer Science 6683, Coello C A C (ed.), Springer, 2011, pp.238-252.

[67] Marmion M, Dhaenens C, Jourdan L, Liefooghe A, Véerel S. NILS: A neutrality-based iterated local search and its application to flowshop scheduling. In Proc. Evolutionary Computation in Combinatorial Optimization, April 2011, pp.191-202.

[68] Marmion M, Dhaenens C, Jourdan L, Liefooghe A, Véerel S. The road to VEGAS: Guiding the search over neutral networks. In Proc. Genetic and Evolutionary Computation Conference, July 2011, pp.1979-1986.

[69] Watson J. An introduction to fitness landscape analysis and cost models for local search. In International Series in Operations Research & Management Science 146, Gendreau M, Potvin J Y (eds.), Springer, 2010, pp.599-623.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved