Constrained sequence alignment
Journal
Bulletin of Mathematical Biology
Journal Volume
55
Journal Issue
3
Pages
503-524
Date Issued
1993
Author(s)
Abstract
This paper presents a dynamic programming algorithm for aligning two sequences when the alignment is constrained to lie between two arbitrary boundary lines in the dynamic programming matrix. For affine gap penalties, the algorithm requires only O(F) computations time and O(M+N) space, when F is the area of the feasible region and M and N are the sequence lengths. The result extends to concave gap penalities, with somewhat increased time and space bounds.
Type
journal article