Editing Needleman–Wunsch algorithm (section)

{{Short description|Method for aligning biological sequences}}
{{Technical|date=September 2013}}
{{Infobox algorithm
|name= <!-- Defaults to article name -->
|class= [[Sequence alignment]]
|image= Needleman-Wunsch pairwise sequence alignment.png
|caption=Figure 1: Needleman-Wunsch pairwise sequence alignment
|data=
|time= <math>O(mn)</math>
|best-time=
|average-time=
|space= <math>O(mn)</math>
}}

The '''Needleman–Wunsch algorithm''' is an [[algorithm]] used in  [[bioinformatics]] to [[sequence alignment|align]] [[protein]] or [[nucleotide]] sequences. It was one of the first applications of [[dynamic programming]] to compare biological sequences. The algorithm was developed by Saul B. Needleman and Christian D. Wunsch and published in 1970.<ref name=Needleman>{{cite journal | journal=Journal of Molecular Biology | volume=48 | issue=3 | pages=443–53 | year=1970  |author1=Needleman, Saul B. |author2=Wunsch, Christian D. |name-list-style=amp | title=A general method applicable to the search for similarities in the amino acid sequence of two proteins  | pmid=5420325 | doi = 10.1016/0022-2836(70)90057-4 }}</ref> The algorithm essentially divides a large problem (e.g. the full sequence) into a series of smaller problems, and it uses the solutions to the smaller problems to find an optimal solution to the larger problem.<ref>{{cite web|title=bioinformatics |url=http://www.britannica.com/EBchecked/topic/1334661/bioinformatics/285871/Goals-of-bioinformatics#ref1115380|access-date=10 September 2014}}</ref> It is also sometimes referred to as the [[optimal matching]] algorithm and the [[Sequence alignment#Global and local alignments|global alignment]] technique. The Needleman–Wunsch algorithm is still widely used for optimal global alignment, particularly when the quality of the global alignment is of the utmost importance. The algorithm assigns a score to every possible alignment, and the purpose of the algorithm is to find all possible alignments having the highest score.