Historical notes and algorithm development
The original purpose of the algorithm described by Needleman and Wunsch was to find similarities in the amino acid sequences of two proteins.
Needleman and Wunsch describe their algorithm explicitly for the case when the alignment is penalized solely by the matches and mismatches, and gaps have no penalty (d=0). The original publication from 1970 suggests the recursion …
A better dynamic programming algorithm with quadratic running time for the same problem (no gap penalty) was first introduced by David Sankoff in 1972. Similar quadratic-time algorithms were discovered independently by T. K. Vintsyuk in 1968 for speech processing ("time warping"), and by Robert A. Wagner and Michael J. Fischer in 1974 for string matching.