###0

Gotoh's algorithm generalizes Waterman's by introducing affine gap scores. It retains runtime O(n^2), but uses two additional tables. Read the full description in Systematic Dynamic Programming in Bioinformatics.