8 - Bounds for Optimal Sequence Alignment

Summary

One of the most frequently used techniques in determining the similarity between biological sequences is optimal sequence alignment. In the standard instance of the sequence alignment problem, we are given two sequences (usually DNA or protein sequences) that have evolved from a common ancestor via a series of mutations, insertions and deletions. The goal is to find the best alignment between the two sequences. The definition of “best” here depends on the choice of scoring scheme, and there is often disagreement about the correct choice. In parametric sequence alignment, this problem is circumvented by instead computing the optimal alignment as a function of variable scores. In this chapter, we address one such scheme, in which all matches are equally rewarded, all mismatches are equally penalized and all spaces are equally penalized. An efficient parametric sequence alignment algorithm is described in Chapter 7. Here we will address the structure of the set of different alignments, and in particular the number of different alignments of two given sequences which can be optimal. For a detailed treatment on the subject of sequence alignment, we refer the reader to [Gusfield, 1997].

Alignments and optimality

We first review some notation from Section 2.2. In this chapter, all alignments will be global alignments between two sequences σ¹ and σ² of the same length, denoted by n.