Smith-Waterman algorithm

The Smith-Waterman algorithm is an algorithm that calculates the optimal local alignment score ( similarity score ) or the optimal local alignment between two sequences . A sequence alignment is a sequence of edit operations (such as character replacement, insertion, deletion) that convert one sequence into the other. The individual operations have a score and the alignment score is defined as the sum of the edit operations scores. A local alignment is a sequence of edit operations to convert a partial sequence of the first sequence into a partial sequence of the other sequence, i.e. H. a sequence of insert and delete operations at the beginning and end can be ignored during optimization if this improves the alignment score. These ignored operations are not part of the local alignment.

The input sequences can be character strings over different alphabets , e.g. B. in bioinformatics , the Smith-Waterman algorithm is applied to DNA sequences or amino acid sequences . One use case is e.g. B. the search for genes (in newly sequenced genomes ) whose sequence is similar to a known gene sequence in another organism, the edit-operations model approximating biological changes during evolution .

The algorithm uses the dynamic programming method and its running time is quadratic. It was developed in 1981 by Temple Smith and Michael S. Waterman and is a variant of the Needleman-Wunsch algorithm that calculates the global alignment .

Local alignment problem

The Smith-Waterman algorithm solves the local alignment problem:

Given are two sequences and , as well as an alignment assessment . We are looking for all optimal local alignments, that is, global alignments of partial sequences and that optimize the evaluation function . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle w}$ ${\displaystyle a'}$ ${\displaystyle b'}$ ${\displaystyle w}$ ${\displaystyle a'=a_{x}\ldots a_{x'},b'=b_{y}\ldots b_{y'},0\leq x\leq x'<|a|,0\leq y\leq y'<|b|}$

motivation

The computation of the optimal local alignment has a different application than the computation of the optimal global alignment.

The consideration of global alignments is useful if one can assume that the sequences to be compared are relatively similar, e.g. B. Sequences of the same length from a protein family.

However, if you want to look for local similarities in sequences that can be very different in other areas, then it makes more sense to consider local alignments. Because an optimal global alignment could in this case hide these local matches, since it has to maximize its score with regard to the entire sequence, e.g. B. individual motifs in different protein sequences.

Differentiation from the Needleman Wunsch algorithm

The Needleman Wunsch algorithm calculates the global alignment of two sequences. To solve the local alignment problem, two modifications are necessary to the Needleman Wunsch algorithm:

1. Initialization of the first column and the first row with 0
2. Maximization over a fourth case, namely 0

The local alignment score is not in the lower right corner of the score matrix, but somewhere in the matrix. It is the entry with the greatest value in the matrix.

The optimal local alignment is obtained by backtracking from the matrix entry with the largest value to a 0 entry in the matrix.

As with the calculation of the global alignment, there can also be several optimal local alignments of two sequences. So several maximum values ​​can exist in the score matrix, and several different backtraces are possible for each optimal value.

Matrix recurrences

The algorithm specification matrix - recurrences :

Input

• ${\displaystyle a,b}$... strings over an alphabet with ${\displaystyle \Sigma }$
  • ${\displaystyle m={\text{length}}(a)}$
  • ${\displaystyle n={\text{length}}(b)}$
• ${\displaystyle w(c,d)}$ … Alignment score function with
  • ${\displaystyle c,d\in \Sigma \cup \{-\}}$
  • ${\displaystyle -}$... gap character

Recurrences

• ${\displaystyle H(i,j)}$indicates the maximum alignment score between a suffix of the first characters of and a suffix of the first character of at ${\displaystyle i}$ ${\displaystyle a}$ ${\displaystyle j}$ ${\displaystyle b}$
• ${\displaystyle H(i,0)=0,\;0\leq i\leq m}$
• ${\displaystyle H(0,j)=0,\;0\leq j\leq n}$
• ${\displaystyle H(i,j)=\max {\begin{Bmatrix}0&{\text{das leere Suffix}}\\H(i-1,j-1)+\ w(a_{i},b_{j})&{\text{Match bzw. Mismatch}}\\H(i-1,j)+\ w(a_{i},-)&{\text{Deletion}}\\H(i,j-1)+\ w(-,b_{j})&{\text{Insertion}}\end{Bmatrix}},\;1\leq i\leq m,1\leq j\leq n}$

Efficiency

The runtime complexity of the Smith-Waterman algorithm is in and the memory requirements in . This can easily be derived from the matrix recurrences. ${\displaystyle O(nm)}$ ${\displaystyle O(nm)}$

Because you can calculate the score matrix line by line or column by column, you only need to save the current and the last line or column if you only want to calculate the score and not the alignment. In this case, the memory requirement is in or . ${\displaystyle O(n)}$ ${\displaystyle O(m)}$

If the memory requirement is linear, the local alignment can also be calculated using the Divide-and-Conquer programming method. See Hirschberg's algorithm .

example

Input

• Sequence a = TCCG
• Sequence b = ACGA
• ${\displaystyle w(x,y)={\begin{cases}+2&{\text{wenn }}x=y{\text{ (match)}}\\-1&{\text{wenn }}x=-{\text{ oder }}y=-{\text{ oder }}x\neq y{\text{ (mismatch)}}\end{cases}}}$

${\displaystyle H={\begin{pmatrix}&-&A&C&G&A\\-&0&0&0&0&0\\T&0&0&0&0&0\\C&0&0&2&1&0\\C&0&0&2&1&0\\G&0&0&1&\mathbf {4} &3\\\end{pmatrix}}}$

For the optimal local alignment, one starts with the number and moves back diagonally, which delivers as the result of the alignment (from sequence ) with (from sequence ). This seems trivial in this simple example, but with longer sequences, the result can no longer be read off the information at a glance. ${\displaystyle 4}$CG ${\displaystyle a}$CG ${\displaystyle b}$

literature

• Temple F. Smith, Michael S. Waterman: Identification of Common Molecular Subsequences. In: Journal of Molecular Biology . Volume 147, 1981, pp. 195-197. DOI: 10.1016 / 0022-2836 (81) 90087-5 . (on-line)
• D. Gusfield: Algorithms on Strings, Trees and Sequences. 1999, ISBN 0-521-58519-8 , pp. 232-235, chap. 11.7.

Web links

• http://bibiserv.techfak.uni-bielefeld.de/cgi-bin/adp_LocSim CGI script for calculating local alignments or the local alignment score at Bielefeld University
• http://jaligner.sourceforge.net/ Java implementation of the Smith-Waterman algorithm
• https://melodic-sequence-alignment.firebaseapp.com/ JavaScript GUI for aligning melodies based on the Smith-Waterman algorithm