Abstract
Algorithms for Local Alignments with Length Constraints
by: Abdullah N. Arslan and Omer Egecioglu
Abstract:
The local sequence alignment problem is the detection of similarsubsequences in two given sequences of lengths n >= m. Unfortunately thecommon notion of local alignment suffers from some well-known anomalies whichresult from not taking into account the lengths of the aligned subsequences.We introduce the length restricted local alignment problem which includes as aconstraint an upper limit T on the length of one of the subsequences to bealigned. However, obvious extensions of dynamic programming formulations forthe solution of the length restricted local alignment problem result inexpensive computations: O(Tnm) time and O(Tm) space. We propose an efficientapproximation algorithm, which finds a solution satisfying the length bound,and whose score is within difference D of the optimum score for any givenpositive integer D. The algorithm runs in time O(nmT/D) using O(mT/D) space.We also introduce the cyclic local alignment problem and show how our idea canbe applied to this case.
Keywords:
Local sequence alignment, edit distance, cyclic edit distance, approximation algorithm
Date:
October 2001
Document: 2001-17
