Global and local sequence alignment with a bounded number of gaps

Pairwise sequence alignment techniques have gained renewed interest in recent years, primarily due to their applications in re-sequencing—the assembly of a genome directed by a reference sequence.

In this article, we show that adding the flexibility of bounding the number of gaps inserted in an alignment strengthens the classical sequence alignment scheme of scoring matrices and affine gap penalty scores. We present GapsMis, an algorithm for pairwise global sequence alignment with a variable, but bounded, number of gaps. It is based on computing a variant of the traditional dynamic programming matrix for global sequence alignment. We also present GapsMis-L, the analogous algorithm for pairwise local sequence alignment with a variable, but bounded, number of gaps.

Website: http://www.arjonline.org/engineering/american-research-journal-of-computer-science-and-information-technology/