Gotoh-Algorithmus
# Gotoh-Algorithmus

Der Gotoh-Algorithmus berechnet das Alignment von zwei Sequenzen bei affinen Gapkosten. Er verwendet das Programmierparadigma der dynamischen Programmierung.

## Affine Gapkosten

Mit affinen Gapkosten bezeichnet man Kosten für Gaps in Alignments, welche sich durch eine lineare Funktion $g(l)={\text{gap}}\_{\text{start}}+(l-1)\times {\text{gap}}\_{\text{extend}}$ beschreiben lassen. Dabei ist $l$ die Länge des Gaps. ${\text{gap}}\_{\text{start}}$ sind die Kosten für den Start eines neuen Gap, und ${\text{gap}}\_{\text{extend}}$ sind die Kosten für die Erweiterung eines existierenden Gaps um eine Stelle.
Biologisch können affine Gapkosten mehr Sinn als rein lineare Gapkosten ergeben, da man eine Insertion bzw. Deletion von mehreren Zeichen in bestimmten Zusammenhängen als wahrscheinlicher betrachten möchte als eine Insertion oder Deletion von einem einzigen Zeichen, z. B. beim Alignieren von cDNA gegen Genom-DNA (Gusfield, 1999).

## Matrix-Rekurrenzen

Spezifikation des Algorithmus durch Matrix-Rekurrenzen:
Initialisierung:
A[0, 0] = 0
B[0, 0] = 0
C[0, 0] = 0
A[i, 0] = C[i, 0] = -inf, 1 <= i <= m
A[0, j] = B[0, j] = -inf, 1 <= j <= n
B[i, 0] = g(i), 1 <= i <= m
C[0, j] = g(j), 1 <= i <= n
Rekursion:
$A(i,j)=\max {\begin{Bmatrix}A(i-1,j-1)+w(u[i-1],v[j-1])\\B(i-1,j-1)+w(u[i-1],v[j-1])\\C(i-1,j-1)+w(u[i-1],v[j-1]\\\end{Bmatrix}},\;1\leq i\leq m,\;1\leq j\leq n$
$B(i,j)=\max {\begin{Bmatrix}A(i-1,j)+{\text{gap}}\_{\text{start}}\\B(i-1,j)+{\text{gap}}\_{\text{extend}}\\C(i-1,j)+{\text{gap}}\_{\text{start}}\\\end{Bmatrix}},\;1\leq i\leq m,\;1\leq j\leq n$
$C(i,j)=\max {\begin{Bmatrix}A(i,j-1)+{\text{gap}}\_{\text{start}}\\B(i,j-1)+{\text{gap}}\_{\text{start}}\\C(i,j-1)+{\text{gap}}\_{\text{extend}}\\\end{Bmatrix}},\;1\leq i\leq m,\;1\leq j\leq n$
* u,v – Sequenzen über einem Alphabet $\Sigma$
* m = Länge(u), n = Länge(v)
* w(a, b),$a,b\in \Sigma$ - Ähnlichkeits-Funktion
* gap_start – Kosten für den Beginn eines Gaps
* gap_extend – Kosten für die Erweiterung eines Gaps
* g(l) - affine Gap-Kosten Funktion $g(l)={\text{gap}}\_{\text{start}}+(l-1)\times {\text{gap}}\_{\text{extend}}$
* -inf = $-\infty$
* A(i,j) – der optimale Similarity Score des optimalen Alignment des Präfixes u[1..i] von u und des Präfixes v[1..j] von v unter affinen Gapkosten
* B(i,j) – der optimale Similarity Score des optimalen Alignment des Präfixes u[1..i] von u und des Präfixes v[1..j] von v, welches mit einem Gap in u endet
* C(i,j) – der optimale Similarity Score des optimalen Alignment des Präfixes u[1..i] von u und des Präfixes v[1..j] von v, welches mit einem Gap in v endet
Der optimale Score des Alignments ist das Maximum von: A[m, n], B[m, n], C[m, n].
Implementation in Pseudo-Code:
Implementation in C# (ohne Fehlerbehandlung):

## Effizienz

Die Laufzeit und der Speicherplatzbedarf des Algorithmus liegen in O(nm). Dies ist eine Verbesserung zum Needleman-Wunsch-Algorithmus, welcher für beliebige Gapkosten eine Laufzeit von $O(nm^{2}+n^{2}m)$ hat. Im schlimmsten Fall ist die Matrix quadratisch ($n=m$), was beim Needleman-Wunsch-Algorithmus zu einer kubischen Laufzeit von $O(n^{3})$ führt. Durch den Gotoh-Algorithmus mit seinen linearen Gap-Kosten verringert sich die Komplexität auf $O(n^{2})$.
Wenn nur der Score des optimalen Alignments berechnet werden soll, können alle Matrizen auch spalten- bzw. zeilenweise berechnet werden, da jeder Eintrag nur von der vorherigen Spalte bzw. Zeile abhängt. Also sinkt der Speicherplatzbedarf auf $O(m+n)$.
Der Gotoh-Algorithmus kann auch mit der Divide-and-Conquer-Methode implementiert werden, so dass das optimale Alignment mit linearem Platzbedarf berechnet werden kann. Siehe Hirschberg-Algorithmus.