An effective evolutionary algorithm for protein folding on 3D FCC HP model by lattice rotation and generalized move sets

Proteome Science

Research

Jyh-Jong Tsay¹  Shih-Chieh Su¹ 

[1] Department of Computer Science and Information Engineering, National Chung Cheng University, 168 University Road, Minhsiung Township, 62102, Chiayi County, Taiwan;

关键词: Local Search;    Tabu Search;    Constraint Programming;    Protein Structure Prediction;    Local Search Method;   

DOI  :  10.1186/1477-5956-11-S1-S19

来源: Springer

【 摘 要 】

BackgroundProteins are essential biological molecules which play vital roles in nearly all biological processes. It is the tertiary structure of a protein that determines its functions. Therefore the prediction of a protein's tertiary structure based on its primary amino acid sequence has long been the most important and challenging subject in biochemistry, molecular biology and biophysics. In the past, the HP lattice model was one of the ab initio methods that many researchers used to forecast the protein structure. Although these kinds of simplified methods could not achieve high resolution, they provided a macrocosm-optimized protein structure. The model has been employed to investigate general principles of protein folding, and plays an important role in the prediction of protein structures.MethodsIn this paper, we present an improved evolutionary algorithm for the protein folding problem. We study the problem on the 3D FCC lattice HP model which has been widely used in previous research. Our focus is to develop evolutionary algorithms (EA) which are robust, easy to implement and can handle various energy functions. We propose to combine three different local search methods, including lattice rotation for crossover, K-site move for mutation, and generalized pull move; these form our key components to improve previous EA-based approaches.ResultsWe have carried out experiments over several data sets which were used in previous research. The results of the experiments show that our approach is able to find optimal conformations which were not found by previous EA-based approaches.ConclusionsWe have investigated the geometric properties of the 3D FCC lattice and developed several local search techniques to improve traditional EA-based approaches to the protein folding problem. It is known that EA-based approaches are robust and can handle arbitrary energy functions. Our results further show that by extensive development of local searches, EA can also be very effective for finding optimal conformations on the 3D FCC HP model. Furthermore, the local searches developed in this paper can be integrated with other approaches such as the Monte Carlo and Tabu searches to improve their performance.

【 授权许可】

CC BY   
© Tsay and Su; licensee BioMed Central Ltd. 2013