Um alle Funktionen dieser Seite zu nutzen, aktivieren Sie bitte die Cookies in Ihrem Browser.
my.bionity.com
Mit einem my.bionity.com-Account haben Sie immer alles im Überblick - und können sich Ihre eigene Website und Ihren individuellen Newsletter konfigurieren.
- Meine Merkliste
- Meine gespeicherte Suche
- Meine gespeicherten Themen
- Meine Newsletter
Gotoh-AlgorithmusDer Gotoh-Algorithmus berechnet das Sequenzalignment von zwei Sequenzen bei affinen Gapkosten. Er verwendet die Programmiermethode der dynamischen Programmierung. Weiteres empfehlenswertes Fachwissen
Affine GapkostenMit affinen Gapkosten bezeichnet man Kosten für Gaps in Alignments, welche sich durch eine lineare Funktion beschreiben lassen. Dabei ist l die Anzahl der Stellen, die das Gap (Bioinformatik) enthält. gap_start + gap_extend 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 von einem einzigen Zeichen, z.B. beim Alignieren von cDNA gegen Genom-DNA (Gusfield, 1999). Matrix-RekurrenzenSpezifikation des Algorithmus durch Matrix-Rekurrenzen: Initialisierung: S(0,0) = 0
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. EffizienzDie 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(nm2 + n2m)) hat. Wenn nur der Score des optimalen Alignments berechnet werden soll, können alle Matrizen auch spalten- bzw. zeilenweise berechnet, da jeder Eintrag nur von der vorherigen Spalte bzw. Zeile abhaengt. 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 in linearer Zeit berechnet werden kann. Siehe Hirschberg-Algorithmus. Literatur
|
|
Dieser Artikel basiert auf dem Artikel Gotoh-Algorithmus aus der freien Enzyklopädie Wikipedia und steht unter der GNU-Lizenz für freie Dokumentation. In der Wikipedia ist eine Liste der Autoren verfügbar. |