Hill-Climbing search and diversification within an evolutionary approach to protein structure prediction

Proteins are complex, irregular structures playing key roles in many cellular functions [1,2]. A protein molecule is a chain of amino acids linked together by peptide bonds (the primary structure), which tend to locally adopt some few characteristic conformations or form flexible loops (the secondary level structure). The function of a protein mainly depends on the tertiary structure which represents the relative arrangement of its secondary structure elements. An open protein chain normally folds into a three-dimensional configuration (called native state) to perform its function. The knowledge generated by a correct prediction of protein tertiary structures is of huge importance for many applications fields including drug design and disease prediction [3].Protein structure prediction refers to the problem of predicting the tertiary structure of a protein based on its primary structure information. This is a computationally challenging problem of significant importance in biochemistry, molecular biology and biophysics. Starting from an unfolded chain of amino acids, protein folding simulations aim to find a final protein structure having minimum energy. Detecting such a structure represents an NP-hard problem [1,4] even in simplified lattice models which abstract away many of the details of protein folding.Lattice protein models are simplified instances of the generic class of cooperative chain folding processes, which include the actual folding of biological macromolecules. Although these models cannot make actual predictions about real biological macromolecules, their fitness landscape and process dynamics share common traits with real-life processes and therefore may serve to characterize generic features of protein folding.The hydrophobic-polar (HP) model [5] is a simplified model which has become a major tool for investigating general properties of protein folding. The HP model emphasizes hydrophobicity as the most important difference between amino acids cons