Abstract
Given a strong match between regions of two sequences, how far can the match be meaningfully extended if gaps are allowed in the resulting alignment? The aim is to avoid searching beyond the point that a useful extension of the alignment is likely to be found. Without loss of generality, we can restrict attention to the suffixes of the sequences that follow the strong match, which leads to the following formal problem. Given two sequences and a fixed X>0, align initial portions of the sequences subject to the constraint that no section of the alignment scores below -X. Our results indicate that computing an optimal alignment under this constraint is very expensive. However, less rigorous conditions on the alignment can be guaranteed by quite efficient algorithms. One of these variants has been implemented in a new release of the Blast suite of database search programs.
Original language | English (US) |
---|---|
Pages | 294-301 |
Number of pages | 8 |
DOIs | |
State | Published - 1998 |
Event | Proceedings of the 1998 2nd Annual International Conference on Computational Molecular Biology - New York, NY, USA Duration: Mar 22 1998 → Mar 25 1998 |
Other
Other | Proceedings of the 1998 2nd Annual International Conference on Computational Molecular Biology |
---|---|
City | New York, NY, USA |
Period | 3/22/98 → 3/25/98 |
All Science Journal Classification (ASJC) codes
- General Computer Science
- General Biochemistry, Genetics and Molecular Biology