Algorithms Based On Face-centered-cubic Lattice Model For Protein Structure Prediction

Protein is the material base of life. The research of the theory of protein folding and the prediction of protein spatial structure not only play a key guiding role in experimental biology, but also have great potential value in pharmacology and gene therapy. With the advances of protein engineering technology, the determination speed of amino acid sequence has far exceeded with the determination speed of its protein structure by using experimental methods. Therefore, to predict the spatial structure of protein theoretically has great practical significance.The structure of the real protein is too complex to predict. For this reason, most scholars use the simplified model to simulate the structure of the real protein. The face-centered-cubic (FCC) lattice model doesn’t have the parity problem which exists in both two-dimensional (2D) square and three-dimensional (3D) cube lattice models, and the structure of the protein simulated based on this model is closer to the structure of the real protein than that simulated based on the square and cube models, so it is chosen as the model for this thesis. However, even if the sequence of this model only contains hydrophobic and hydrophilic amino acids, the protein structure prediction problem based on this model is NP-hard.In this paper, two intelligent optimization algorithms------energy landscape paving method (ELP) and Wang-Landau sampling algorithm are introduced to solve the protein spatial structure prediction problem based on the FCC lattice model. Experimental results indicate that they are two impactful algorithms for protein spatial structure prediction problem on both2D and3D FCC lattice models. Detailed description and the relevant simulated results for these two intelligent algorithms are as follows.(1) By putting forward a new update mechanism of the frequency histogram in ELP and incorporating the greedy strategy for generating initial conformation and the neighborhood search strategy based on pull-moves into ELP, an improved energy landscape paving (ELP+) method is proposed. Twelve general benchmark instances are first tested on both2D and3D FCC hydrophobic-hydrophilic (HP) lattice models. The lowest energies by ELP+are as good as or better than those of other methods in the literature for all instances. Then5sets of benchmarks consisting of21instances are tested on3D FCC lattice model. The ELP+algorithm improves the best results of12instances obtained by other algorithms.(2) Wang-Landau sampling algorithm is a novel Monte Carlo (MC) algorithm. Unlike conventional MC methods which can only form a canonical distribution at a fixed temperature, this algorithm estimates the density of states for the range of all possible energies via a random walk which produces a flat histogram in energy space. In this paper, Wang-Landau sampling algorithm is firstly introduced to solve the protein spatial structure prediction problem based on the FCC lattice model. Combining this randomized algorithm with the pull-moves strategy which has a fine search capabilitity, a new intelligent randomized optimization algorithm is introduced. We test the method on the above33instances. For each instance, the lowest energy by this algorithm is as good as or better than those of the above ELP+algorithm and all methods in the literature, indicating that this algorithm is also an efficient algorithm for solving the protein spatial structure prediction problem.