imported>Saehrimnir: BKL Fix

2025-06-30T08:08:38Z

BKL Fix

Neue Seite

Der '''Smith-Waterman-Algorithmus''' ist ein [[Algorithmus]], der den [[Optimierungsalgorithmus|optimalen]] lokalen Alignment-Score (''similarity score'') bzw. das optimale [[Sequenzalignment#Lokales Alignment|lokale Alignment]] zwischen zwei [[Folge (Mathematik)|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 [[Zeichenkette|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 [[Zeichenkette]]n über verschiedenen [[Alphabet]]en sein, z. B. in der [[Bioinformatik]] wird der Smith-Waterman-Algorithmus auf [[Nukleotidsequenz|DNA-Sequenzen]] oder [[Aminosäuresequenz]]en angewendet. Ein Anwendungsfall ist z. B. die Suche nach [[Gen]]en (in neu-sequenzierten [[Genom]]en), 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 [[Dynamische Programmierung|Dynamischen Programmierung]] und seine [[Laufzeitkomplexität|Laufzeit]] ist quadratisch. Er wurde 1981 von [[Temple Smith]] und
[[Michael S. Waterman]] entwickelt und ist eine Variante des [[Needleman-Wunsch-Algorithmus]], der das [[Sequenzalignment#Globales Alignment|globale Alignment]] berechnet.

== Lokales Alignment-Problem ==
Der Smith-Waterman-Algorithmus löst das lokale Alignment-Problem:
:Gegeben seien zwei Sequenzen <math>a</math> und <math>b</math>, sowie eine Alignmentbewertung <math>w</math>. Gesucht sind alle optimalen lokalen Alignierungen, das sind globale Alignierungen von Teilsequenzen <math>a'</math> und <math>b'</math>, die die Bewertungsfunktion <math>w</math> optimieren, mit <math>a' = a_x\ldots a_{x'}, b' = b_y\ldots b_{y'}, 0\leq x\leq x'<|a|, 0\leq y\leq y'<|b|</math>.

== 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 [[Sequenzmotiv|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:
# Initialisierung der ersten Spalte und der ersten Zeile mit 0
# 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 (Mathematik)|Matrix]]-[[Differenzengleichung|Rekurrenzen]]:

'''Input'''
* <math>a, b</math> … Zeichenketten über einem [[Alphabet]] <math>\Sigma</math> mit
** <math>m = \text{length}(a)</math>
** <math>n = \text{length}(b)</math>
* <math>w(c,d)</math> … Alignment-Score-Funktion mit
** <math>c, d\in\Sigma\cup\{-\}</math>
** <math>-</math> … [[Gap (Bioinformatik)|Gap-Charakter]]

'''Rekurrenzen'''
* <math>H(i,j)</math> gibt den maximalen Alignment-Score zwischen einem [[Suffix]] von den ersten <math>i</math> Zeichen von <math>a</math> und einem Suffix von den ersten <math>j</math> Zeichen von <math>b</math> an
* <math>H(i,0) = 0,\; 0\le i\le m</math>
* <math>H(0,j) = 0,\; 0\le j\le n</math>
* <math>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\le i\le m, 1\le j\le n
</math>

== Effizienz ==
Die Laufzeitkomplexität des Smith-Waterman-Algorithmus ist in <math>O(nm)</math> und der Speicherbedarf in <math>O(nm)</math>. 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 <math>O(n)</math> bzw. <math>O(m)</math>.

In linearem Speicherbedarf kann man auch das lokale Alignment mit Hilfe der Programmiermethode [[Teile und herrsche (Informatik)|Divide-and-Conquer]] berechnen. Siehe [[Hirschberg-Algorithmus]].

== Beispiel ==
'''Input'''
* Sequenz a = <code>TCCG</code>
* Sequenz b = <code>ACGA</code>
* <math>w(x,y)=\begin{cases}
+2&\text{wenn }x=y\text{ (match)}\\
-1&\text{wenn }x=-\text{ oder }y=-\text{ oder }x\ne y\text{ (mismatch)}
\end{cases}</math>

<math>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}
</math>

Für das optimale lokale Alignment wird bei der Zahl <math>4</math> begonnen und diagonal zurückgewandert, was als Ergebnis des Alignments <code>CG</code> (aus Sequenz <math>a</math>) mit <code>CG</code> (aus Sequenz <math>b</math>) 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]]. [https://dornsife.usc.edu/assets/sites/516/docs/papers/msw_papers/msw-042.pdf (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

[[Kategorie:Bioinformatik]]
[[Kategorie:Optimierungsalgorithmus]]
[[Kategorie:Dynamische Programmierung]]

Smith-Waterman-Algorithmus - Versionsgeschichte

imported>Saehrimnir: BKL Fix