A Simulated Annealing Approach To Multiple Sequence Alignment

Multiple sequence alignment is a basic information processing method in bioinformatics. The research of fast and sensitive biology sequence alignment algorithm is a current hot topic of bioinformatics, some researches are made in this dissertation.In this paper, we describe existing alignment algorithms, such as pairwise alignment algorithms: Needleman-Wunsch, Smith-Waterman, FASTA , BLAST and multiple alignment algorithms: CLUSTALW, T-Coffee, DiAlign, MultAlin, Prrp, Muscle, POA, ABA and expose the potential strengths and weaknesses of the most widely used alignment algorithms.Simulated annealing method provides a useful tool for obtaining the best heuristic solution for several hard problems in combinatorial optimization. In this paper we demonstrate that existing multiple alignment algorithms using simulated annealing algorithm are low biology sensitivity and inefficiency, which is proved by the theoretical analysis and experiment of the SA-MSA. For research sensitive biology sequence alignment algorithm, refer to the characteristic of simulated annealing and center star alignment, a new multiple alignment algorithm MSA_CONSENSUS_STAR is developed, which divide the complicated problem of multiple alignment into the problem of seek for consensus sequence and simple aligning. In order to test the accuracy of the algorithm, MSA_CONSENSUS_STAR is tested by using the BAliBASE database of multiple sequence alignment. The results of testing indicate that the proposed algorithm is feasible. The accuracy of MSA_CONSENSUS_STAR alignment has a great improvement compared with SA-MSA and HMMT alignment. For data sets in including"orphan"sequences and comprising N/ C terminal extensions, MSA_CONSENSUS_STAR generates better alignment as compared with ClustalW, SAGA and MultAlin .