Approximation algorithms for multiple sequence alignment

We consider the problem of aligning of k sequences of length n. The cost function is sum of pairs, and satisfies triangle inequality. Earlier results on finding approximation algorithms for this problem are due to Gusfield, 1991, who achieved an approximation ratio of 2 − 2/k, and Pevzner, 1992, who improved it to 2 − 3/k. We generalize this approach to assemble an alignment of k sequences from optimally aligned subsets of lrandomized algorithms yielding performance guarantees of 2−l/k. For fixed l, the running times of these algorithms are polynomial in n and k.