Multiple Sequence Alignment Algorithm Research And Implementation

Sequence alignment of bioinformatics is an important fundamental subject in bioinformatics research.One of its most basic task is to multiple sequence alignments. Sequence alignment is used to research of the domain protein identification, secondary structure prediction, gene identification, and molecular phylogenetic analysis.Muttiple sequence alignment is NP-hard problem, still there is not an optimal algorithm of multiple sequence alignments.This paper proseses a method, which use quantum-behaved particle swarm optimization algorithm and the Hidden Markov Model to solve the problems of multiple sequence alignments.Firstly, the effect on sequence alignment caused by the gap penalty, substitution matrix and objective function are analyzed, and the SP objective function and COFFEE objective function are introduced. For the classic multiple sequence alignment algorithm, study the SAGA algorithm and Clustal programming and HMM algorithm.Make comparison and assessment for the performance on several algorithms.Later through the study on current situation of the multiple sequence alignments algorithm and the analysis to the principle and characteristic of the particle swarm optimization algotithm,present the multiple sequence alignments algorithem based on binary particle swarm optimization algorithm MSA_BPSO,and then through the study and the analysis on the quantum-behaved particle swarm optimization algorithm and the Hidden Markov Model,present multiple sequence alignment based on Hidden Markov Model and quantum-behaved particle swarm optimization algorithm (MSA_HMM_QPSO).Base on the algorithm of this paper bringing forward, design and implement the software for multiple sequence alignments based on Windows operation system by Microsoft Visual Studio.Net C#2005. Also, The algorithms were used to test benchmark multiple sequence alignments database BAliBASE, and make comparative analysis with classical protein sequence alignment method.The results show that the proposed MSA_HMM_QPSO algorithm are feasible to solve the problem of sequence alignments.Finally, the future work of MSA_HMM_QPSO algorithm in sequence analysis was discussed in this paper.