We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Approximation Algorithms for Local Alignment with Length Constraints.
- Authors
Arslan, Abdullah N.; Egecioglu, Ömer
- Abstract
The local sequence alignment problem is the detection of similar subsequences in two given sequences of lengths n ≥ m. Unfortunately the common notion of local alignment suffers from some well-known anomalies which result from not taking into account the lengths of the aligned subsequences. We introduce the length restricted local alignment problem which includes as a constraint an upper limit T on the length of one of the subsequences to be aligned. Obvious extensions of dynamic programming formulations for the solution of the length restricted local alignment problem result in expensive computations: O(Tnm) time and O(Tm) space. We propose an efficient approximation algorithm using which we can find a solution satisfying the length bound, and whose score is within difference Δ of the optimum score for any given positive integer Δ in time O(nmT/Δ) using O(mT/Δ) space. We also introduce the cyclic local alignment problem and show how our idea can be applied to this case as well. This is a dual approach to the well-known cyclic edit distance problem. These results generalize directly to the case of affine gap penalties. Keywords: Local sequence alignment, edit distance, cyclic edit distance, approximation algorithm.
- Subjects
ALGORITHMS; MATHEMATICAL sequences; DYNAMIC programming
- Publication
International Journal of Foundations of Computer Science, 2002, Vol 13, Issue 5, p751
- ISSN
0129-0541
- Publication type
Article
- DOI
10.1142/S0129054102001436