01805nas a2200217   4500008004100000245006100041210005900102260008600161300001200247490000700259520106200266653002801328653002601356653002201382653003201404653001401436100001301450700001301463700001601476856009501492       2000                        eng d00aA more efficient approximation scheme for tree alignment0 amore efficient approximation scheme for tree alignment  a3600 UNIV CITY SCIENCE CENTER, PHILADELPHIA, PA 19104-2688 USAbSIAM PUBLICATIONS  a283-2990 v303 aWe present a new polynomial time approximation scheme (PTAS) for tree alignment, which is an important variant of multiple sequence alignment. As in the 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 algorithm uses a clever partitioning strategy and achieves a better efficiency for the same performance ratio. For example, to achieve approximation ratios 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 are the depth and number of leaves of the tree, while the new PTAS only has to 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 determines 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.10aapproximation algorithm10acomputational biology10aevolutionary tree10amultiple sequence alignment10aphylogeny1 aWang, LS1 aJiang, T1 aGusfield, D  uhttps://nematoda.myspecies.info/content/more-efficient-approximation-scheme-tree-alignment