A New Approach for Tree Alignment Based on Local Re-Optimization

Multiple sequence alignment is the most fundamental task in bioinformatics and computational biology. In this paper, we present a new algorithm to conduct multiple sequences alignment based on phylogenetic trees. It is widely accepted that a good phylogenetic tree can help produce high quality alignment, but the direct dynamic programming solution grows exponentially [13]. To overcome this problem, we first devise a procedure that can produce optimal alignment for three sequences and infer their common ancestor. We then extend the above procedure to compute the alignment of a given tree with more sequences by itera- tively relabeling the internal nodes. We have implemented our algorithm as a C program package, which can handle both DNA and protein data and can take simple cost model as well as complex substitution matrices, such as PAM or BLOSUM series. We test our new method with biological and simulated datasets, and compare its performance with those of other popular multiple sequence alignment tools, including the widely used programs such as ClustalW and T-Coffee.