A more efficient approximation scheme for tree alignment

We present a new polynomial time approximation scheme (PTAS) for tree align ment, which is an important variant of multiple sequence alignment. As in t he existing PTASs in the literature, the basic approach of our algorithm is to partition the given tree into overlapping components of a constant size and then apply local optimization on each such component. But the new algo rithm uses a clever partitioning strategy and achieves a better efficiency for the same performance ratio. For example, to achieve approximation ratio s 1.6 and 1.5, the best existing PTAS has to spend time O(kdn(5)) and O(kdn (9)), respectively, where n is the length of each leaf sequence and d, k ar e the depth and number of leaves of the tree, while the new PTAS only has t o spend time O(kdn(4)) and O(kdn(5)). Moreover, the performance of the PTAS is more sensitive to the size of the components, which basically determine s the running time, and we obtain an improved approximation ratio for each size. Some experiments of the algorithm on simulated and real data are also given.