###0

The following grammar is a variant of Gotoh's, restricted to canonical alignments. (Canonical alignments avoid redundant re-arrangements of gaps, thereby reducing the search space and making the consideration of near-optimal solutions more meaningful.) Read the full description in Systematic Dynamic Programming in Bioinformatics.