APPROXIMATION ALGORITHMS FOR TREE ALIGNMENT WITH A GIVEN PHYLOGENY

We study the following fundamental problem in computational molecular biology: Given a set of DNA sequences representing some species and a phylogenetic tree depicting the ancestral relationship among these spe cies, compute an optimal alignment of the sequences by the means of co nstructing a minimum-cost evolutionary tree. The problem is an importa nt variant of multiple sequence alignment, and is widely known as tree alignment. We design an efficient approximation algorithm with perfor mance ratio 2 for tree alignment, The algorithm is then extended to a polynomial-time approximation scheme. The construction actually works for Steiner trees in any metric space, and thus implies a polynomial-t ime approximation scheme for planar Steiner trees under a given topolo gy (with any constant degree). To our knowledge, this is the first pol ynomial-time approximation scheme in the fields of computational biolo gy and Steiner trees. The approximation algorithms may be useful in ev olutionary genetics practice as they can provide a good initial alignm ent for the iterative method in [23].