Gotoh-Algorithmus

Der Gotoh-Algorithmus berechnet das Sequenzalignment 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) = gap\_start + l \cdot gap\_extend$ beschreiben lassen. Dabei ist l die Anzahl der Stellen, die das Gap (Bioinformatik) enthält. gap_start sind die Kosten für den Start eines neuen Gap, und gap_extend sind die Kosten für die Erweiterung eines existierenden Gaps um eine Stelle.

Biologisch können affine Gapkosten mehr Sinn ergeben, als rein lineare Gapkosten, da man eine Insertion bzw. Deletion von mehreren Zeichen in bestimmten Zusammenhängen als wahrscheinlicher betrachten möchte als ein Indel (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:

S(0,0) = 0

$V(0,j) = -\inf,\; 0\le j\le n$

$S(i,0) = V(i,0) = g(i),\; 1\le i \le m$

$H(i,0) = -\inf,\; 0\le i\le m$

$S(0,j) = H(0,j) = g(j),\; 1\le j\le n$

Rekursion:

$S(i,j) = \max \begin{Bmatrix} S(i-1, j-1) + w(u[i], v[j]) && \text{Match bzw. Mismatch} \\ H(i, j) && \text{Insertion} \\ V(i, j) && \text{Deletion} \\ \end{Bmatrix},\; 1\le i\le m,\; 1\le j\le n$

$H(i,j) = \max \begin{Bmatrix} S(i, j-1)+gap\_start+gap\_extend && \text{Beginn einer neuen Insertion} \\ H(i, j-1)+gap\_extend && \text{Erweiterung einer Insertion} \\ \end{Bmatrix},\; 1\le i\le m,\; 1\le j\le n$

$V(i,j) = \max \begin{Bmatrix} S(i-1, j)+gap\_start+gap\_extend && \text{Beginn einer neuen Deletion} \\ V(i-1, j)+gap\_extend && \text{Erweiterung einer Deletion} \\ \end{Bmatrix},\; 1\le i\le m,\; 1\le j\le n$

• u,v - Sequenzen über einem Alphabet Σ
• m = length(u), n = length(v)
• w(a, b),$a, b\in\Sigma$ - Similarity-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) = gap_start + l * gap_extend
• S(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
• H(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
• V(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

Die Initialisierung der Hilfsmatrizen V und H wird in mehreren Literaturquellen falsch angegeben mit: H(i,0) = g(i),V(0,j) = g(j) (Stoye, 1997 - Beweis und weitere Literatur). Denn für H(i,0) bzw. V(0,j) enden die Alignments nicht in einem Gap in u bzw. v.

Bei der Berechnung des globalen optimal Alignment ist der Score der optimalen Alignment der Sequenzen u und v in D(m, n) gespeichert.

Effizienz

Die Laufzeit der Algorithmus ist in O(mn) und Speicherplatzbedarf liegt in O(nm), was man einfach mit Hilfe der Matrix-Rekurrenzen erkennen kann. Dies ist eine Verbesserung zum Needleman-Wunsch-Algorithmus, welcher für beliebige Gapkosten eine Laufzeit von O(nm² + n²m)) hat.

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 Aligment mit linearem Platzbedarf berechnet werden kann. Siehe Hirschberg-Algorithmus.

Literatur

• O. Gotoh: An improved algorithm for matching biological sequences. In: J. Mol. Biol.. 162, 1982, S. 705-708 (PDF, 206 KB).
• J. Stoye. Divide-and-Conquer Multiple Sequence Alignment. Dissertation Thesis. Universität Bielefeld, Forschungsbericht der Technischen Fakultät, Abteilung Informationstechnik, Report 97-02, S.26-27, 1997. ISSN 0946-7831
• D. Gusfield. Algorithms on Strings, Trees and Sequences. 11.8:235-244 , 1999, ISBN 0-521-58519-8

Weblinks

• http://bibiserv.techfak.uni-bielefeld.de/cgi-bin/adp_AffineGlobSim CGI-Script zur Berechnung von gloabalen Alignments mit affinen Gapkosten an der Universität Bielefeld