Research Of Multiple Sequence Alignment Based On The Lempel-Ziv

In this paper,a novel progressive multiple sequence alignment algorithm LZ_MSA is developed.The time complexity of pairwise sequence alignment is O(N log N) and the guide tree is adjusted in LZ_MSA.Its features are:pairwise alignment speed,can avoid the partial solutions.The 5gruops'proteins in BAliBASE test the validation of the algorithm.Test result shows that LZ_MSA shorten the alignment time without sacrificing the accuracy.This paper studies the multiple sequence alignment algorithms in bioinformatics. The main contents are as follows listed:Firstly,we describe the basic content about sequence alignment:substitution matrix,scoring system and sequence alignment testing data collection and evaluation standard.Secondly,we mainly study and describe the algorithm ClustalW which is based on the progressive alignment strategy.Then through the analysis of this algorithm,its advantages and disadvantages are proposed.Thirdly,for the pairwise alignment in large amount of calculation and easy to fail into local solutions in ClustalW,a novel progressive multiple sequence alignment algorithm LZ_MSA based on LZ algorithm is developed.Design and implement a soft of LZ_MSA based on Windows operation system by Microsoft VisualC++.Finally,Using a group of BAliBASA' biological protein sequences for testing LZ_MSA,comparative analysis with ClustalW,MAFFT.The results show that the time of LZ_MSA is drastically reduced as compared with ClustalW,MAFFT with comparable accuracy.These algorithms are also testified feasible and efficient in biology sensitivity and computing efficiency.