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

  1. Keine Lücke beim Alignment in der letzten Position, d.h. $x_m$ und $y_n$ werden mit $\alpha_{x,y}$ bestraft (oder $x_m=y_n$) und Unterproblem Alignment von $X'$ und $Y'$.
  2. $x_m$ trifft auf eine Lücke in $Y$, d.h. Strafterm $\alpha_{gap}$ und Unterproblem Alignment von $X'$ und $Y$.
  3. $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

Rekonstruktionsalgorithmus analog zu den bisherigen Beispielen.

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$

image.png

Abbildung aus [Man]

Literatur