Global and local sequence alignment with a bounded number of gaps (Q2342666)

The authors present an algorithm for pairwise global sequence alignment with at most a given number of gaps. Their algorithm computes a three-dimensional variant of the traditional two-dimensional dynamic-programming matrix for global sequence alignment. This takes \(\Theta (m k \ell)\) time and \(\Theta (m k)\) space, where \(m\) is the length of the shorter sequence, \(k\) is the maximum allowed edit distance and \(\ell\) is the maximum number of gaps allowed in the alignment. The authors also present an analogous algorithm for pairwise local sequence alignment with at most a given number of gaps. (This summary is slightly paraphrasing the first paragraph of the article's conclusion.)