Parametric Sequence Alignment

This lecture describes parametric sequence alignment as presented in Section 13.1 of Dan Gusfield’s book Algorithms on Strings, Trees, and Sequences.

Given two sequences, can you determine how many choices of values of the standard sequence alignment objective function’s parameters give distinct optimal alignments. In other words, how many alignments are optimal for some setting of the objective function’s parameters. This lecture discusses how to approach and answer this question.