A new hybrid genetic algorithm for protein structure prediction on the 2D triangular lattice

The flawless functioning of the protein is essentially related to its three-dimensional structure. Therefore, predicting protein structure from its amino acid sequence is a fundamental problem that draws researchers’ attention in many areas. The protein structure prediction problem (PSP) can be formulated as a combinatorial optimization problem based on simplified lattice models such as the hydrophobic-polar model. In this paper, we propose a new hybrid algorithm that combines three different known heuristic algorithms: the genetic algorithm, the tabu search strategy, and the local search algorithm to solve the PSP problem. Regarding the evaluation of the proposed approach, we present an experimental study, where we consider the quality of the product solution as the main assessment criterion. Furthermore, we compared the proposed algorithm with state-of-the-art algorithms using a selection of well-studied benchmark instances.

PDF

___

1] Valastyan JS, Lindquist S. Mechanisms of protein-folding diseases at a glance. Disease Models & Mechanisms 2014; 7 (1): 9-14. doi: 10.1242/dmm.013474
[2] Hardy JA, Higgins GA. Alzheimer’s disease: the amyloid cascade hypothesis. Science 1992; 256 (5054): 184-185. doi: 10.1126/science.1566067
[3] Chen Y, Ding F, Nie H, Serohijos AW, Sharma S et al. Protein folding: then and now. Archives of Biochemistry and Biophysics 2008; 469 (1): 4-19. doi: 10.1016/j.abb.2007.05.014
[4] Dill KA. Theory for the folding and stability of globular proteins. Biochemistry 1985; 24 (6): 1501-1509. doi: 10.1021/bi00327a032.
[5] Lau KF, Dill KA. A lattice statistical mechanics model of the conformational and sequence spaces of proteins. Macromolecules 1989; 22 (10): 3986-3997.
[6] Lin CJ, Hsieh MH. An eﬀicient hybrid Taguchi-genetic algorithm for protein folding simulation. Expert Systems with Applications 2009; 36 (10): 12446-12453.
[7] Shmygelska A, Hoos HH. An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem. BMC Bioinformatics 2005; 6 (1): 30.
[8] Berger B, Leighton T. Protein folding in the hydrophobic-hydrophilic (HP) is NP-complete. In: Proceedings of the Second Annual International Conference on Computational Molecular Biology; Manhattan, NY, USA; 1998. pp. 30-39.
[9] Crescenzi P, Goldman D, Papadimitriou C, Piccolboni A, Yannakakis M. On the complexity of protein folding. Journal of Computational Biology 1998; 5 (3): 423-465. [10] Unger R, Moult J. Genetic algorithms for protein folding simulations. Journal of Molecular Biology 1993; 231 (1): 75-81.
[11] Dandekar T, Argos P. Folding the main chain of small proteins with the genetic algorithm. Journal of Molecular Biology 1994; 236 (3): 844-861.
[12] Hart WE, Krasnogor N, Pelta DA, Smith J. Protein structure prediction with evolutionary algorithms. Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation 1999; 39: 1596-1601.
[13] König R, Dandekar T. Improving genetic algorithms for protein folding simulations by systematic crossover. BioSystems 1999; 50(1): 17-25.
[14] Shmygelska A, Aguirre-Hernandez R, Hoos HH. An ant colony optimization algorithm for the 2D HP protein folding problem. In: International Workshop on Ant Algorithms; Brussels, Belgium; 2002. pp. 40-52.
[15] Krasnogor N, Blackburne BP, Burke EK, Hirst JD. Multimeme algorithms for protein structure prediction. In: International Conference on Parallel Problem Solving from Nature; Granada, Spain; 2002. pp. 769-778.
16] Pelta DA, Krasnogor N. Multimeme algorithms using fuzzy logic based memes for protein structure prediction. In: Hart WE, Krasnogor N, Smith J (editors). Recent Advances in Memetic Algorithms. Berlin, Germany: Springer, 2005, pp. 49-64.
[17] Bautu A, Luchian H. Protein structure prediction in lattice models with particle swarm optimization. In: Interna- tional Conference on Swarm Intelligence; Brussels, Belgium; 2010. pp. 512-519.
[18] Jiang T, Cui Q, Shi G, Ma S. Protein folding simulations of the hydrophobic–hydrophilic model by combining tabu search with genetic algorithms. The Journal of Chemical Physics 2003; 119 (8): 4592-4596.
[19] Cutello V, Morelli G, Nicosia G, Pavone M. Immune algorithms with aging operators for the string folding problem and the protein folding problem. In: European Conference on Evolutionary Computation in Combinatorial Optimization; Lausanne, Switzerland; 2005. pp. 80-90.
[20] Cutello V, Nicosia G, Pavone M, Timmis J. An immune algorithm for protein structure prediction on lattice models. IEEE Transactions on Evolutionary Computation 2007; 11 (1): 101-117.
[21] Islam MK, Chetty M. Clustered memetic algorithm with local heuristics for ab initio protein structure prediction. IEEE Transactions on Evolutionary Computation 2012; 17 (4): 558-576.
[22] Hoque MT, Chetty M, Dooley LS. A hybrid genetic algorithm for 2D FCC hydrophobic-hydrophilic lattice model to predict protein folding. In: Australasian Joint Conference on Artificial Intelligence; Hobart, Australia; 2006. pp. 867-876.
[23] Böckenhauer HJ, Ullah AZ, Kapsokalivas L, Steinhöfel K. A local move set for protein folding in triangular lattice models. In: International Workshop on Algorithms in Bioinformatics; Karlsruhe, Germany; 2008. pp. 369-381.
[24] Su SC, Lin CJ, Ting CK. An eﬀicient hybrid of hill-climbing and genetic algorithm for 2D triangular protein structure prediction. In: 2010 IEEE International Conference on Bioinformatics and Biomedicine Workshops (BIBMW); Hong Kong, China; 2010. pp. 51-56.
[25] Guo Y, Wu Z, Wang Y, Wang Y. Extended particle swarm optimisation method for folding protein on triangular lattice. IET Systems Biology 2016; 10 (1): 30-33.
[26] Yang CH, Wu KC, Lin YS, Chuang LY, Chang HW. Protein folding prediction in the HP model using ions motion optimization with a greedy algorithm. BioData Mining 2018; 11 (1): 17.
[27] Gillespie J, Mayne M, Jiang M. RNA folding on the 3D triangular lattice. BMC Bioinformatics 2009; 10 (1): 369.
[28] Blum C, Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Com- puting Surveys (CSUR) 2003; 35 (3): 268-308.
[29] Talbi EG. Metaheuristics: From Design to Implementation. Hoboken, NJ, USA: John Wiley & Sons, 2009.
[30] Raidl GR, Puchinger J, Blum C. Metaheuristic hybrids. In: Gendreau M, Potvin JY (editors). Handbook of Metaheuristics. Boston, MA, USA: Springer, 2010, pp. 469-496.
[31] Zhao X. Advances on protein folding simulations based on the lattice HP models with natural computing. Applied Soft Computing 2008; 8 (2): 1029-1040.