Needleman-Wunsch Algorithm

The Needleman-Wunsch algorithm is an algorithm used in bioinformatics to align protein or nucleotide sequences, and was one of the first applications of dynamic programming to compare biological sequences. It was developed by Saul B. Needleman and Christian D. Wunsch and published in 1970. The algorithm divides a large problem, such as a full sequence, into a series of smaller problems and uses the solutions to the smaller problems to find an optimal solution to the larger one; it is also sometimes called the optimal matching algorithm or the global alignment technique, and assigns a score to every possible alignment in order to find the alignments with the highest score. It remains widely used for optimal global alignment, particularly when the quality of the global alignment matters most.