Pairwise alignment with scoring on tuples

Abstract

Pairwise alignment of two sequences a, b usually assumes a and b being sequences over the same alphabet A and a scoring function s: A×A→ℝ operating on symbol pairs. The framework presented here extends this to a scoring function s: A ^p ×B ^q →ℝ operating on p-tuples and q-tuples of symbols, where the scoring tuples can have an arbitrary (but not complete) overlap. We show that, if the alphabets A and B are finite and p and q are constant, the resulting algorithms have the same asymptotic time and space complexity as their single symbol counterparts. This framework has been applied successfully to the codon-wise alignment of prokaryotic and eukaryotic genes.