Near Optimal Multiple Alignment Within a Band In Polynomial Time
Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Title of host publication | STOC '00 |
| Subtitle of host publication | Proceedings of the thirty-second annual ACM symposium on Theory of computing |
| Publisher | Association for Computing Machinery |
| Pages | 425-434 |
| ISBN (print) | 1581131844, 978-1-58113-184-0 |
| Publication status | Published - May 2000 |
Publication series
| Name | |
|---|---|
| ISSN (Print) | 0737-8017 |
Conference
| Title | 32nd Annual ACM Symposium on Theory of Computing (STOC '00) |
|---|---|
| Place | United States |
| City | Portland |
| Period | 21 - 23 May 2000 |
Link(s)
Abstract
Multiple sequence alignment is one of the most important problems in computational biology. Because of its notorious difficulties, aligning sequences within a constant band is a popular practice in bioinformatics with good results [17; 13; 14; 15; 1; 3; 6; 20; 18]. However, the problem is still NP-hard for multiple sequences. In this paper, we present polynomial time approximation schemes (PTAS) for multiple sequence alignment within a constant band, under standard models of SP alignment and consensus (star) alignment. The algorithms work for very general score schemes.
In order to prove our main results, we also present a PTAS for SP alignment and a PTAS for consensus alignment, allowing only constant number of insertion and deletion gaps (of arbitrary length) per sequence on the average.
In order to prove our main results, we also present a PTAS for SP alignment and a PTAS for consensus alignment, allowing only constant number of insertion and deletion gaps (of arbitrary length) per sequence on the average.
Citation Format(s)
Near Optimal Multiple Alignment Within a Band In Polynomial Time. / Li, Ming; Ma, Bin; Wang, Lusheng.
STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing. Association for Computing Machinery, 2000. p. 425-434.
STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing. Association for Computing Machinery, 2000. p. 425-434.
Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review
