Research On Algorithms Of Protein Structure Prediction

The prediction of a protein's structure from its amino-acid sequence is one of the most important problems in modern computational biology. Main problem in computational methods is the huge computational task. There are two kinds of efforts having been done to solve the problem: one is using novel searching methods, such as Genetic algorithm, Simulated Annealing Algorithm etc; the other is to make reasonable simplification of protein structure, such as simplification model.This paper applies two typical swarm intelligence algorithms, Ant Colony Optimization (ACO) Algorithm and Particle Swarm Optimization (PSO) Algorithm, to the protein structure prediction in two kinds of simple exact model. We present an improved ACO to solve lattice model, and introduce PSO for off-lattice model.The paper consists of four chapters. As the basic part, Charter 1 and Charter 2 introduce the importance of the research, the current works, the basic knowledge for this research, including the amino acid classification, protein molecular structure, the lattice model and off-lattice model. Chapter 3 and Chapter 4 is our primary work, and it includes two parts: In part one, an improved ACO is proposed for lattice model, we modified the local search mechanism by using pull moves. It can quicken the convergence rate, and the experiments show that our algorithm can observably decrease computing time with the same result of previous ACO algorithm. In part two, we introduce PSO for off-lattice model and demonstrate its ability to solve artificial data and real protein data. To our best knowledge, this is the first application of PSO to the highly relevant problem from bioinformatics. The results indicate PSO is really a good searching method and off-lattice model can simulate real protein to some extent, but it still need further improvement.