Research On Multiple Sequence Alignment Algorithm Of Bioinformatics

Sequence alignment is the most important manipulation and the fundamental information processing method in bioinformatics. Aligning a number of sequences is significant for discovering functional, structural, and evolutionary information in biological sequences. Pair-wise alignment algorithms are very successful at present, and the existing multiple sequence alignment algorithms are mostly based on a mathematical model or biological model, which can not guarantee the results of alignment is optimal, but rather a approximation. Therefore, it is still a hot and difficult to study both efficient and accurate on multiple sequence alignment algorithm. A multiple sequence alignment based on particle swarm optimization (PSO) of evolution and the hidden Markov models(HMM) is proposed because of the highly effective performance of the intellectualized algorithm in processing the multiple sequence alignment.The basis of sequence alignment and analysis of the sequence alignment in the gap penalty and effects of scoring matrix,the definition of multiple sequence alignment and the SP model which evaluate the result of the alignment are introduced. Then classical Clustalw——a famous progressive method, is analyzed in detail as an example of progressive alignment algorithms. On this basis, the intelligent algorithm of hidden Markov model and the three basic problems for HMM and the solution are described. The hidden Markov models for multiple sequence alignment is established and the algorithmic process is given to solve the multiple sequence alignment.After that the shortcomings of the hidden Markov Model to solve multiple sequence alignment are studied. As the Baum-Welch algorithm may converge to a large iteration stride undesirable local minimum, the particle swarm optimization algorithm to optimize the training of the model is introduced. Particle Swarm Optimization is a collaborative group-based random search algorithm by simulated flock foraging behavior. Then the shortcomings of particle swarm optimization in solving the training of the hidden Markov model are conducted and a "premature" phenomenon in particle swarm optimization is described. In the search process, particle swarm may fall into local optimum but not the global optimum. To solve this problem, the particle swarm optimization algorithm based on the theory of evolution is proposed. If we find a particle fall into a local optimum in the search process, we move it and fill a particle with more capability to search, then we continue the global search to ensure the global optimization. It's efficient to overcome the "premature" phenomenon. Finally, the algorithmic process to solve multiple sequence alignment based on the evolutionary ideas of particle swarm optimization and hidden Markov models is described. By the simulation experiment which use the test data in BAliBASE2.0 reference library, proves that the improved algorithm, which is effective in solving the multiple sequence alignment, is better than the Baum-Welch algorithm.