Sequenzalignment - Levenshtein Abstand¶
Motivation - Anwendungen¶
- Sequenzalignment (Sequence Alignment)
- Berechnung der Genome-Ähnlichkeit (Proxy für Phylogenetic Trees) in der Biologie / Bioinformatik
- Edit-Abstand oder Levenshtein Abstand zweier Zeichenketten
- Rechtschreibprüfung in der Such- und Sprachtechnologie
Problem Definition: Sequenzalignment¶
Eingabe: Zwei Zeichenketten $X$ und $Y$ aus einem Alphabet $\Sigma$, z.B. $\Sigma = \{A,C, G, T\}$. Eine Bestrafung/Kosten $\alpha_{x,y}$ für jedes Symbol-Paar $x,y \in \Sigma$ und ein nicht-negativer Strafterm $\alpha_{gap}>0$ für eine Lücke (gap).
Ausgabe: Ein Alignment von $X$ und $Y$ mit minimalen Gesamtkosten.
Die Gesamtkosten (total penalty) heißen in der Bioinformatik auch Needleman-Wunsch Score (NW Score).
Problem Definition: Edit-Abstand¶
Eingabe: Zwei Zeichenketten $X$ und $Y$ aus einem Alphabet $\Sigma$. Die Zeichenfolge $X$ soll durch Edit-Operationen in eine Zeichenfolge $Y$ überführt werden. Dabei gibt es Bestrafung/Kosten für
- die Editoperation Ersetzen (Symbolaustausch): $\alpha_{x,y}$ für jedes Symbol-Paar $x,y \in \Sigma$ (z.B. $\alpha_{x,y}=1$ für $x \neq y$ unabhängig von $x,y$ und $\alpha_{x,y}=0$ für $x=y$) und
- die Editoperation Löschen/Einfügen: nicht-negativer Strafterm $\alpha_{gap}>0$ (z.B. $\alpha_{gap}=1$) für das Löschen eines Symbols aus $X$ bzw. für ein Einfügen eines Symbols zu $X$.
Ausgabe: Der Edit-Abstand von $X$ zu $Y$, d.h. die minimalen möglichen Gesamtkosten, die durch Editieren von $X$ zu $Y$ (und umgekehrt) entstehen.
Hinweis:
- Die beiden Probleme (Berechnung des Needleman-Wunsch Score bzw. des Edit-Abstandes) sind identisch.
Optimale Unterstruktur¶
Nicht-leere Zeichenketten:
- $X=x_1,x_2,\dots, x_m$
- $Y=y_1,y_2,\dots, y_n$
und die um ein Symbol verkürzten Zeichenketten:
- $X'=x_1,x_2,\dots, x_{m-1}$
- $Y'=y_1,y_2,\dots, y_{n-1}$
Drei Fälle¶
- Keine Lücke beim Alignment in der letzten Position, d.h. $x_m$ und $y_n$ werden mit $\alpha_{x,y}$ bestraft (oder $x=y$) und Unterproblem Alignment von $X'$ und $Y'$.
- $x_m$ trifft auf eine Lücke in $Y$, d.h. Strafterm $\alpha_{gap}$ und Unterproblem Alignment von $X'$ und $Y$.
- $y_n$ trifft auf eine Lücke in $X$, d.h. Strafterm $\alpha_{gap}$ und Unterproblem Alignment von $X$ und $Y'$.
Rekurrenz¶
$P_{i,j}$ sei die Gesamtstrafe (total penalty) des Alignments von $X_i$ und $Y_j$ mit
- $X_i=x_1,x_2,\dots x_i$ (ersten $i$-Symbole von $X$)
- $Y_j=y_1,y_2,\dots y_j$ (ersten $j$-Symbole von $Y$)
dann gilt folgende Rekurrenz für $i\in\{1,2,\dots,m\}$ und $j\in\{1,2,\dots,n\}$:
$$ P_{i,j} = \min\left\{ P_{i-1,j-1} + \alpha_{x_i, y_j}, P_{i-1,j} + \alpha_{gap}, P_{i,j-1} + \alpha_{gap}\right\} $$Hinweis:
- Die drei Möglichkeiten in $\min$ entsprechen den drei Fällen.
- Das Problem mit $i=m$ und $j=n$ entspricht dem Gesamtproblem.
Algorithmus¶
NW / EditDistance¶
Input: : Strings $X$ and $Y$. Penalties $\alpha_{xy}$ and $\alpha_{gap}>0$
Output: The NW score / Edit distance of $X$ and $Y$
// subproblem solutions (indexed from 0)
$A:= (m+1)\times(n+1)$ two dimensional array
// base case #1
for $i:=0$ to $m$ do
$A[i][0]=i\cdot \alpha_{gap}$
// base case #2
for $j:=0$ to $n$ do
$A[0][j]=j\cdot \alpha_{gap}$
// systematically solve all subproblems
for $i:=1$ to $m$ do
for $j:=1$ to $n$ do
$A[i][j] := \min\left\{ A[i-1][j-1] + \alpha_{x_i, y_j}, A[i-1][j] + \alpha_{gap}, A[i][j-1] + \alpha_{gap}\right\}$
return $A[m][n]$// solution to largest subproblem
Laufzeit¶
Die Laufzeit ist $O(mn)$ (Auffüllen des 2d-Arrays)
Beispiel: Edit-Abstand mit $\alpha_{x,y}=1$ für $x\neq y$ und $\alpha_{gap}=1$
Abbildung aus [Man]
Literatur¶
- T. Roughgarden, Algorithms Illuminated, Part 3: Greedy Algorithms and Dynamic Programming
- [Man] Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information Retrieval, Chapter 3: Dictionaries and tolerant retrieval / Spelling correction / Edit distance, Cambridge University Press. 2008