Algorithms for Local Alignments with Length Constraints

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.