3D Protein Folding Structure Prediction With Genetic Tabu Search Algorithm

While protein folds into its specific spatial structure, it performs a wide variety of bioactivities, thus the study of protein folding structure is a key issue in bioinformatics. Based on the thermodynamic hypothesis that the native conformation of protein is the one at lowest free energy state, researchers are using the ab inito prediction method to predict stereo structure from its amino acid sequence directly, and encounter two major difficulties. One is how to obtain a potential energy function that distinguishes the native conformation from non-native structures, and the other is how to develop an effective global optimization method to search the minimum free energy.The three-dimensional AB off-lattice model which remains faithful to protein characteristics is adopted as simplified model in this thesis, and a novel hybrid approach genetic tabu search algorithm (GATS) that combines genetic algorithm and tabu search algorithm is presented for dealing with the 3D protein folding structure prediction. In order to enhance the global optimization ability and local search intensity, five improved strategies are developed for the proposed method, which are chromosome encoding, variable population size, ranking selection, tabu search mutation (TSM) and tabu search recombination (TSR).The proposed genetic tabu search algorithm is applied to two types of data for folding structure prediction in three dimensions, which are the widely-used four Fibonacci sequences and the nine real protein sequences from Protein Data Bank (PDB), and can search the minimum free energies and the lowest-energy landscapes quickly with the higher accuracy. Experimental results show that the lowest energies obtained by our algorithm are better than those searched by other methods, and the optimal solutions are improved even more with the sequence length increases. In addition, the lowest-energy conformations of this thesis all form compact hydrophobic cores, surrounded by hydrophilic residues as observed in real protein. All of these demonstrate that the proposed GATS provides an effective and high-performance global search method for protein folding structure prediction.