Needleman–Wunsch algorithm – Wikipedia
Friday, November 11th, 2016https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm
relates to
https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm
https://en.wikipedia.org/wiki/Michael_J._Fischer
QT:{{"
Historical notes and algorithm development[edit]
The original purpose of the algorithm described by Needleman and Wunsch was to find similarities in the amino acid sequences of two proteins.[1]
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[3] by David Sankoff in 1972. Similar quadratic-time algorithms were discovered independently by T. K. Vintsyuk[4] in 1968 for speech processing ("time warping"), and by Robert A. Wagner and Michael J. Fischer[5] in 1974 for string matching.
"}}