Approximation algorithms for multiple sequence alignment

AbstractWe 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 − 2k, and Pevzner (1992) who improved it to 2 − 3k. We generalize this approach to assemble an alignment of k sequences from optimally aligned subsets of l < k sequences to obtain an improved performance guarantee. For arbitrary l < k, we devise deterministic and randomized algorithms yielding performance guarantees of 2 − lk. For fixed l, the running times of these algorithms are polynomial in n and k