Heuristic Algorithms For Predicting Three-dimensional Folding Structures Of Proteins

The protein structure prediction problem, i.e., the protein folding problem, is concerned with how proteins fold into biologically-active three-dimensional (3D) structures from their linear amino acid sequences. As one of the core research areas in bioinformatics, the protein folding problem has high theoretical value and practical significance.The protein structure prediction problem is known to be an NP-hard problem. During the past few years, researchers have put forward a number of simplified models. This thesis mainly studies the3D protein structure prediction problems based on two types of specific models:the hydrophobic-hydrophilic (HP) lattice model and the hydrophobic-hydrophilic-neutral (BLN) off-lattice model, by proposing global optimization algorithms. By making full use of the information of the models themselves to construct some effective heuristic strategies, some heuristic algorithms for solving the corresponding problems are proposed by combining these heuristic strategies with some global optimization algorithms. And we use the experiments to validate the effectiveness of these heuristic algorithms. The main research contents and results are as follows:(1) By using the HP lattice model, we put forward the improved genetic algorithm to predict the3D protein spatial folding structure from its linear amino acid sequence. In the process of solving the problem, we use the greedy algorithm to produce the initial population, and perform the mutation operation after the operations of selection and crossover by using the backtracking method, thus we can obtain the chromosomes which have a strong ability to survive. Finally we get a new generation of population by using conformation updating mechanism based on the pull-move set. We simulate the algorithm on some representative instances. The numerical computational results show that the proposed improved genetic algorithm is an effective algorithm for solving the protein structure prediction on the3D HP lattice model.(2) We use the hybrid algorithm to predict the protein spatial folding structure based on the BLN off-lattice model. First, we establish an equivalent energy model by using the idea of quasi-physical method. Then we convert the problem into an unconstrained optimization problem by introducing the penalty function. By putting forward a new updating mechanism of the histogram function in the energy landscape paving (ELP) method and incorporating heuristic conformation update strategies into the ELP method, we obtain an improved ELP (IELP) method. Subsequently, by combining the IELP method with the local search (LS) based on the gradient descent method, we propose a hybrid algorithm, denoted by IELP-LS, for the conformational search of the off-lattice BLN model. Simulation results on three real protein sequences from the PDB show that the proposed method is an effective tool for global optimization in the BLN off-lattice protein model.