page_title: Smith–Waterman algorithm
section_title: Example
hierarchical_section_title: Smith–Waterman algorithm / Example
caption_attribution_description: English: Scoring matrix and scoring process
context_page_description: The Smith–Waterman algorithm performs local sequence alignment; that is, for determining similar regions between two strings of nucleic acid sequences or protein sequences. Instead of looking at the entire sequence, the Smith–Waterman algorithm compares segments of all possible lengths and optimizes the similarity measure.
  The algorithm was first proposed by Temple F. Smith and Michael S. Waterman in 1981. Like the Needleman–Wunsch algorithm, of which it is a variation, Smith–Waterman is a dynamic programming algorithm. As such, it has the desirable property that it is guaranteed to find the optimal local alignment with respect to the scoring system being used. The main difference to the Needleman–Wunsch algorithm is that negative scoring matrix cells are set to zero, which renders the local alignments visible. Traceback procedure starts at the highest scoring matrix cell and proceeds until a cell with score zero is encountered, yielding the highest scoring local alignment.
context_section_description: Take the alignment of DNA sequences TGTTACGG and GGTTGACTA as an example. Use the following scheme:
  Substitution matrix: 
  Gap penalty:  (a linear gap penalty of )
  Initialize and fill the scoring matrix, shown as below. This figure shows the scoring process of the first three elements. The yellow color indicates the bases that are being considered. The red color indicates the highest possible score for the cell being scored.
  The finished scoring matrix is shown below on the left. The blue color shows the highest score. An element can receive score from more than one element, each will form a different path if this element is traced back. In case of multiple highest scores, traceback should be done starting with each highest score. The traceback process is shown below on the right. The best local alignment is generated in the reverse direction.
  The alignment result is:
  G T T - A C| | |   | |G T T G A C
caption: Initialization of the scoring matrix (left 1) and the scoring process of the first three elements (left 2-4)
exif: {}