"An Improved Algorithm for Matching Biological Sequences", Gotoh (1982):
The algorithm of Waterman et al. (1976) for malchirlg biological seyuences was modified under some limitations to be accomplished in essentially MN steps, instead of the M2N steps necessary in the original algorithm.
http://www.genome.ist.i.kyoto-u.ac.jp/~aln_user/archive/JMB82.pdf