Improving Kalign via Reconstruction of Phylogenetic Tree and Iteration

The multiple sequence alignment of DNA or protein sequences is one of the fundamental research topics in bioinformatics. Kalign is an widely used multiple sequence alignment method employing the Wu-Manber approximate string matching algorithm, which improves both the accuracy and speed of multiple sequence alignment, and it is especially well suited for the task of aligning large numbers of sequences or divergent sequences. However, the alignment quality is poor because of the inaccurate estimate of the distances between sequences. In this paper, a novel similarity measure based on matching protein subsequences is presented. Then an iterative algorithm, which combines re-estimation of distance and reconstruction of phylogenetic tree, is introduced to refine the alignment created by Kalign. As the result of experiment, we use the BAliBASE 3.0 alignment benchmark set for the assessment of our method. The result shows that our algorithm achieves more accurate alignment than Kalign does.