Hybrid Algorithms For Protein Structure Prediction Problems Of AB Off-lattice Model

Protein acts an important role in life activity, its biological function is determined by the spatial structure. The study found that many human diseases are caused by structural changes of protein. So, to understand the spatial structure of protein has important practical significance. However, more and more studies show that protein structure prediction problem is NP hard problem. For such problem, there is no existence of generally applicable solutions yet. This article proposes a novel scheme for constructing a hybrid algorithm.Because the spatial structure of real protein is very complex, the theory put forward many simplified models when studying the problem, among which AB off-lattice model is one of the most classic models. In this model, amino acids are divided into two categories:hydrophobic and hydrophilic, denoted by A and B respectively. AB model is usually divided into AB Model I and AB Model II according to the difference of potential energy function. It is a continuous polymer model, which is more in line with the folding properties of real protein than HP lattice model. So, we choose AB model as the simplified model of protein structure prediction and study the problem based on both of AB Model I and II. The research results of this article are as follows:(1) For the protein structure prediction problem of AB model I, a quasi-physical strategy is first adopted to establish the mathematical model of the problem, and the tabu search algorithm is then applied to search for the low-energy conformations of protein. For this problem, we make a new definition of neighborhood structure and tabu object in tabu search algorithm, and improve the acceptance criteria of current conformation. We use the improved tabu search algorithm for global search, meanwhile, the gradient method is incorporated for local search. In the search process, inspired by the structural features of real protein, we propose a heuristic mechanism of generating promising initial conformation and a heuristic conformation updating mechanism, then a heuristic-based tabu search algorithm (HTS) is obtained. The experimental results show that whether it is two-dimensional AB model I or three-dimensional one or not, HTS algorithm can obtain better results.(2) For the protein structure prediction problem of AB model II, a annealing genetic algorithm based on local search (LS-AGA) is presented for dealing with the problem in this thesis. In this algorithm, crossover operator and mutation operator in genetic algorithm are applied to update conformation. Considering that AB model is a continuous model, we use non-uniform arithmetic crossover for crossover operator and spherical update mechanism for mutation operator. For a new generated conformation, the Metropolis rule in simulated annealing algorithm is used to determine whether to accept it or not. Then, the conjugate gradient method based on an adapted step is used to search near the conformation generated by annealing genetic algorithm, so as to avoid missing global optimal conformation. The experimental results show that LS-AGA algorithm is an effective algorithm for solving the protein structure prediction problem of AB model Ⅱ.