Smith-Waterman-Algorithmus

Der Smith-Waterman-Algorithmus ist ein Algorithmus, der den optimalen lokalen Alignment-Score (similarity score) bzw. das optimale lokale Alignment zwischen zwei Sequenzen berechnet. Ein Sequenzalignment ist eine Folge von Edit-Operationen (wie z. B. Zeichenersetzung, Einfügung, Löschung), die die eine Sequenz in die andere überführt. Die einzelnen Operationen haben einen Score und der Alignment-Score ist als die Summe der Edit-Operations-Scores definiert. Ein lokales Alignment ist eine Folge von Edit-Operationen um eine Teilsequenz der ersten Sequenz in eine Teilsequenz der anderen Sequenz zu überführen, d. h. bei der Optimierung kann eine Folge von Einfüge- und Lösch-Operationen am Anfang und Ende ignoriert werden, wenn dies den Alignment-Score verbessert. Diese ignorierten Operationen sind nicht Teil des lokalen Alignments.

Die Eingabe-Sequenzen können Zeichenketten über verschiedenen Alphabeten sein, z. B. in der Bioinformatik wird der Smith-Waterman-Algorithmus auf DNA-Sequenzen oder Aminosäuresequenzen angewendet. Ein Anwendungsfall ist z. B. die Suche nach Genen (in neu-sequenzierten Genomen), deren Sequenz einer bekannten Gen-Sequenz in einem andern Organismus ähnelt, wobei das Edit-Operations-Modell biologische Veränderungen während der Evolution approximiert.

Der Algorithmus verwendet die Methode der Dynamischen Programmierung und seine Laufzeit ist quadratisch. Er wurde 1981 von Temple Smith und Michael S. Waterman entwickelt und ist eine Variante des Needleman-Wunsch-Algorithmus, der das globale Alignment berechnet.

Lokales Alignment-Problem

Der Smith-Waterman-Algorithmus löst das lokale Alignment-Problem:

Gegeben seien zwei Sequenzen $a$ und $b$, sowie eine Alignmentbewertung $w$. Gesucht sind alle optimalen lokalen Alignierungen, das sind globale Alignierungen von Teilsequenzen $a'$ und $b'$, die die Bewertungsfunktion $w$ optimieren, mit $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

Die Berechnung des optimalen lokalen Alignment hat eine andere Anwendung als die Berechnung des optimalen globalen Alignment.

Die Betrachtung von globalen Alignments ist sinnvoll, wenn man davon ausgehen kann, dass die zu vergleichenden Sequenzen relativ ähnlich sind, z. B. Sequenzen gleicher Länge aus einer Proteinfamilie.

Wenn man allerdings nach lokalen Übereinstimmungen (=Similarities) in Sequenzen, die in anderen Bereichen sehr unterschiedlich sein können, suchen möchte, so ist die Betrachtung von lokalen Alignments sinnvoller. Denn ein optimales globales Alignment könnte in diesem Fall diese lokalen Übereinstimmungen verdecken, da es seinen Score in Hinblick auf die gesamte Sequenz maximieren muss, z. B. einzelne Motive in verschiedenen Proteinsequenzen.

Abgrenzung zum Needleman-Wunsch-Algorithmus

Der Needleman-Wunsch-Algorithmus berechnet das globale Alignment von zwei Sequenzen. Um das lokale Alignment-Problem zu lösen, sind an dem Needleman-Wunsch-Algorithmus zwei Modifikationen notwendig:

1. Initialisierung der ersten Spalte und der ersten Zeile mit 0
2. Maximierung über einen vierten Fall, nämlich 0

Der lokale Alignment-Score steht nicht in der rechten unteren Ecke der Score-Matrix, sondern irgendwo in der Matrix. Es ist der Eintrag mit dem größten Wert in der Matrix.

Das optimale lokale Alignment erhält man durch Backtracking von dem Matrix-Eintrag mit dem größten Wert bis zu einem 0-Eintrag in der Matrix.

Wie bei der Berechnung des globalen Alignment können auch mehrere optimale lokale Alignments von zwei Sequenzen existieren. Also können mehrere maximale Werte in der Score-Matrix existieren, und für jeden optimalen Wert sind auch mehrere unterschiedliche Backtraces möglich.

Matrix-Rekurrenzen

Spezifikation des Algorithmus durch Matrix-Rekurrenzen:

Input

• $a,b$ … Zeichenketten über einem Alphabet $\Sigma$ mit
  • $m={\text{length}}(a)$
  • $n={\text{length}}(b)$
• $w(c,d)$ … Alignment-Score-Funktion mit
  • $c,d\in \Sigma \cup \{-\}$
  • $-$ … Gap-Charakter

Rekurrenzen

• $H(i,j)$ gibt den maximalen Alignment-Score zwischen einem Suffix von den ersten $i$ Zeichen von $a$ und einem Suffix von den ersten $j$ Zeichen von $b$ an
• $H(i,0)=0,\;0\leq i\leq m$
• $H(0,j)=0,\;0\leq j\leq n$
• $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$

Effizienz

Die Laufzeitkomplexität des Smith-Waterman-Algorithmus ist in $O(nm)$ und der Speicherbedarf in $O(nm)$. Dies kann man einfach aus den Matrix-Rekurrenzen ableiten.

Weil man die Score-Matrix zeilen- bzw. spaltenweise berechnen kann, braucht man jeweils nur die aktuelle und die letzte Zeile bzw. Spalte zu speichern, wenn man nur den Score und nicht das Alignment berechnen möchte. In dem Fall liegt der Speicherbedarf in $O(n)$ bzw. $O(m)$.

In linearem Speicherbedarf kann man auch das lokale Alignment mit Hilfe der Programmiermethode Divide-and-Conquer berechnen. Siehe Hirschberg-Algorithmus.

Beispiel

Input

• Sequenz a = TCCG
• Sequenz b = ACGA
• $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}}$

$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}}$

Für das optimale lokale Alignment wird bei der Zahl $4$ begonnen und diagonal zurückgewandert, was als Ergebnis des Alignments CG (aus Sequenz $a$) mit CG (aus Sequenz $b$) liefert. Dies scheint bei diesem einfachen Beispiel trivial, bei längeren Sequenzen jedoch ist das Ergebnis nicht mehr auf einen Blick aus der Angabe abzulesen.

Literatur

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

Weblinks

• https://bibiserv.cebitec.uni-bielefeld.de/cgi-bin/adp_LocSim CGI-Script zur Berechnung von lokalen Alignments bzw. dem lokalen Alignment-Score an der Universität Bielefeld
• https://jaligner.sourceforge.net/ Java-Implementierung des Smith-Waterman-Algorithmus
• https://melodic-sequence-alignment.firebaseapp.com/ JavaScript-GUI zum Alignment von Melodien auf Grundlage des Smith-Waterman-Algorithmus