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.