Research On Protein Multiple Sequence Alignment Algorithms And Assessment Of Their Performance

Multiple sequence alignment is an important step in bioinformatics applications. However, traditional sequence alignment is an NP hard problem and most algorithms reach practical speed somehow at the expense of precision. As the existing algorithms cannot perform well on speed and accuracy at the same time, the protein evolution research, which is based on sequence alignment, is difficult to cure the shortcomings of large scale of computations and low accuracy.To assess the performances of various alignment algorithms we proposed the permutation distance method, which can overcome data noises and achieve more objective evaluations for protein multiple sequence alignment algorithms. As the permutation similarity method only concerns the relative order of different protein evolutionary distances, without taking into account the slight difference between the evolutionary distances, it can get more robust evaluations. And the longest common subsequence method selected by us can well define the distances between different permutations.We build the relative entropy model to measure evolutionary distances among proteins. Since the sequence alignment process is not necessary our model can greatly increase the speed, meanwhile maintaining the accuracy. Results show this method is more outstanding than many traditional sequence-alignment-based methods and thus reliable.By using these methods, we compared and assessed Dialign, Tcoffee, CustalW and our own relative entropy method. Results validated the feasibility of relative entropy method and its advantage in time.