APPROXIMATION ALGORITHMS FOR MULTIPLE SEQUENCE ALIGNMENT

We consider the problem of aligning of k sequences of length n. The co st function is sum of pairs, and satisfies triangle inequality. Earlie r results on finding approximation algorithms for this problem are due to Gusfield (1991) who achieved an approximation ratio of 2 - 2/k, an d Pevzner (1992) who improved it to 2 - 3/k. We generalize this approa ch to assemble an alignment of k sequences from optimally aligned subs ets of l < k sequences to obtain an improved performance guarantee. Fo r arbitrary I < k, we devise deterministic and randomized algorithms y ielding performance guarantees of 2 - l/k. For fixed I, the running ti mes of these algorithms are polynomial in n and k.