๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Approximation algorithms for multiple sequence alignment

โœ Scribed by Vineet Bafna; Eugene L. Lawler; Pavel A. Pevzner

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
793 KB
Volume
182
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 1 < k sequences to obtain an improved performance guarantee. For arbitrary 1 < k, we devise deterministic and randomized algorithms yielding performance guarantees of 2 -Z/k. For fixed I, the running times of these algorithms are polynomial in n and k.

๐Ÿ“œ SIMILAR VOLUMES

Non-approximability of weighted multiple
Non-approximability of weighted multiple sequence alignment
โœ Bodo Manthey ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 167 KB

We consider a weighted generalization of multiple sequence alignment (MSA) with sum-of-pair score. MSA without weights is known to be NP-complete and can be approximated within a constant factor, but it is unknown whether it has a polynomial time approximation scheme. Weighted multiple sequence alig

Improved Approximation Algorithms for Tr
Improved Approximation Algorithms for Tree Alignment
โœ Lusheng Wang; Dan Gusfield ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 251 KB

Multiple sequence alignment is a task at the heart of much of current computaw x tional biology 4 . Several different objective functions have been proposed to formalize the task of multiple sequence alignment, but efficient algorithms are lacking in each case. Thus multiple sequence alignment is on

Parametric and ensemble sequence alignme
Parametric and ensemble sequence alignment algorithms
โœ Michael S. Waterman ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Springer ๐ŸŒ English โš– 1020 KB

## Proceedings of the Third Annual ACM-SIAM Discrete Algorithms) find optimal scores for all penalty parameters, both for global and local sequence alignment. This paper reviews those techniques Then in the main part of this paper dynamic programming methods are used to compute ensemble alignment,