page_title: Needleman–Wunsch algorithm
hierarchical_section_title: Needleman–Wunsch algorithm
caption_attribution_description: English: The score matrix for an alignment between GATTACA and GCATGCU.
context_page_description: The Needleman–Wunsch algorithm is an algorithm used in bioinformatics to 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. The algorithm essentially divides a large problem into a series of smaller problems, and it uses the solutions to the smaller problems to find an optimal solution to the larger problem. It is also sometimes referred to as the optimal matching algorithm and the 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.
context_section_description: The Needleman–Wunsch algorithm is an algorithm used in  bioinformatics to 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. 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. It is also sometimes referred to as the optimal matching algorithm and the 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.
caption: Figure 1: Needleman-Wunsch pairwise sequence alignment  Results:
  
  Sequences    Best alignments
  ---------    ----------------------
  GCATGCU      GCATG-CU      GCA-TGCU      GCAT-GCU
  GATTACA      G-ATTACA      G-ATTACA      G-ATTACA
  
  Interpretation of the initialization step:
  
  One can interpret the leftmost column in the above figure like this (putting a "handle" before each sequence, annotated as + here):
  
  Alignment:  +GCATGCU
              +GATTACA
  Score:      0  // Handle matches handle, doesn't win any score
  
  Alignment:  +GCATGCU
             +GATTACA
  Score:      0  // 1 gap,  score −1
  
  Alignment:  +GCATGCU
            +GATTACA
  Score:      0  // 2 gaps, score −2
  
  Alignment:  +GCATGCU
           +GATTACA
  Score:      0  // 3 gaps, score −3
  
  Alignment:  +GCATGCU
          +GATTACA
  Score:      0  // 4 gaps, score −4
  
  ...
  
  The same thing can be done for the uppermost row.
exif: {}