The Research And Optimization Of CLUSTAL Algorithm In Multiple Sequence Alignment

Multiple sequence alignment is one of the most important fundamental subjects inmodern bioinformatics. In order to align multiple sequences in multiple sufficientlysimilar organisms, there is an urgent need for software tools which can align more thantwo sequences. However, most of the current research focuses on pair-wise genomealignment, and only a few available applications can efficiently align multiple genomes,and the most classics application is CLUSTAL.This paper researches the algorithm of CLUSTAL in detail. CLUSTAL algorithmincludes three steps: pair-wise alignment, build guide tree and progressive alignment,and this paper propose an effective optimization algorithm for its first and second steps.In the first step, this paper uses Ukk-FA algorithm to calculate distance matrix, insecond step, this paper makes use of Fast-NJ algorithm to build guide tree, in its finalstep, this paper uses original algorithm.The experimental results of sequence alignment on the multiunit multiple realDNA sequence has shown that compared with original algorithm the optimizationalgorithm which proposed in this paper is good in accuracy and high in efficiency. Inthe step of building guide tree, the experimental results show that as the increase ofsequence number, the time performance has improved observably.