An Evolutionary Model Based on Hill-Climbing Search Operators for Protein Structure Prediction

摘要

The prediction of a minimum-energy protein structure from its amino-acid sequence represents one of the most important and challenging problems in computational biology. A new evolutionary model based on hill-climbing genetic operators is proposed to address the hy-drophobic - polar model of the protein folding problem. The introduced model ensures an efficient exploration of the search space by implementing a problem-specific crossover operator and enforcing an explicit diversification stage during the evolution. The mutation operator engaged in the proposed model refers to the pull-move operation by which a single residue is moved diagonally causing the potential transition of connecting residues in the same direction in order to maintain a valid protein configuration. Both crossover and mutation are applied using a steepest-ascent hill-climbing approach. The resulting evolutionary algorithm with hill-climbing operators is successfully applied to the protein structure prediction problem for a set of difficult bidimensional instances from lattice models.