3 ZUSTANDSMODELLE
Die Idee, die Vorhersagen zu einer vollständigen Genstruktur zu kombinieren, besteht darin, dass die „grammatikalischen“ Beschränkungen einige falsche Exon-Zusammensetzungen ausschließen können. Die grammatikalische Struktur des Problems wurde von David Searls (Searls, 1992; Dong und Searls, 1994) hervorgehoben, der auch vorschlug, die Methoden der formalen Grammatiken aus der Informatik und der Linguistik zu verwenden. Die dynamische Programmierung lässt sich häufig durch eine Art endlichen Zustandsautomaten beschreiben (Searls und Murphy, 1995; Durbin et al., 1998). Ein Modell könnte einen Zustand für den Übersetzungsbeginn (S), einen für Donorstellen (D), einen für Akzeptorstellen (A) und einen für die Beendigung der Übersetzung (T) haben. Jedes Mal, wenn ein Übergang von einem Zustand in einen anderen erfolgt, wird ein Punktwert (oder eine Strafe) hinzugefügt. Für den Übergang vom Donor-Zustand zum Akzeptor-Zustand wird die Intron-Punktzahl zur Gesamtpunktzahl hinzugezählt, usw. In Abbildung 11.2 ist das Zustandsdiagramm für den obigen einfachen dynamischen Programmieralgorithmus dargestellt. Für jede Variable im Algorithmus gibt es einen entsprechenden Zustand mit demselben Namen, und auch ein Anfangs- und Endzustand wird benötigt.
Abbildung 11.2. Ein endlicher Zustandsautomat, der dem einfachen DP-Algorithmus entspricht.
Der Vorteil einer solchen Formulierung besteht darin, dass die dynamische Programmierung zur Ermittlung der maximalen Punktzahl (oder der minimalen Strafe) allgemeiner Art ist und daher das Hinzufügen neuer Zustände oder neuer Übergänge einfach ist. Zum Beispiel ist das Zeichnen des Zustandsdiagramms für einen allgemeineren dynamischen Programmierungsalgorithmus, der eine beliebige Anzahl von Genen und auch Teilgenen zulässt, einfach (Abbildung 11.3), während es schwierig ist, es aufzuschreiben. Ähnlich ist das Zustandsdiagramm für den oben skizzierten frame-aware Algorithmus in Abbildung 11.4 dargestellt.
Abbildung 11.3. Das Modell aus Abbildung 11.2 mit zusätzlichen Übergängen, die die Vorhersage einer beliebigen Anzahl von Genen und Teilgenen ermöglichen, bei denen die Sequenz in der Mitte eines Exons oder Introns beginnt oder endet.
Abbildung 11.4. Ein Modell, das die Konsistenz des Rahmens in einem Gen gewährleistet. Wie in den beiden vorangegangenen Abbildungen entsprechen die gepunkteten Linien den intergenischen Regionen, die gestrichelten den Introns und die durchgezogenen Linien den kodierenden Regionen (Exons).
Wenn die verwendeten Scores log-Wahrscheinlichkeiten oder log-Quoten sind, dann ist ein endlicher Zustandsautomat im Wesentlichen ein verstecktes Markov-Modell (HMM), und diese wurden kürzlich von mehreren Gruppen in die Genfindung eingeführt. Der einzige grundlegende Unterschied zu den oben diskutierten dynamischen Programmierungsschemata besteht darin, dass diese Modelle vollständig probabilistisch sind, was gewisse Vorteile hat. Einer der Vorteile ist, dass das Gewichtungsproblem einfacher ist.
VEIL (Henderson et al., 1997) ist eine Anwendung eines HMM auf das Problem der Gensuche. In diesem Modell sind alle Sensoren HMMs. Das Exon-Modul ist im Wesentlichen eine inhomogene Markov-Kette erster Ordnung, die oben beschrieben wurde. Dies ist die natürliche Reihenfolge für die Implementierung in ein HMM, weil dann jede der bedingten Wahrscheinlichkeiten der inhomogenen Markov-Kette der Wahrscheinlichkeit eines Übergangs von einem Zustand zum nächsten im HMM entspricht. Es ist nicht möglich, Stoppcodons im Leseraster zu vermeiden, wenn ein Modell erster Ordnung verwendet wird, aber in VEIL werden auf geschickte Weise einige weitere Zustände hinzugefügt, wodurch die Wahrscheinlichkeit eines Stoppcodons gleich Null ist. Sensoren für Spleißstellen werden auf ähnliche Weise erstellt. Die einzelnen Module werden dann im Wesentlichen wie in Abbildung 11.2 kombiniert (d. h. die Rahmenkonsistenz wird nicht erzwungen). Das kombinierte Modell ist ein großes HMM, und alle Übergänge haben zugehörige Wahrscheinlichkeiten. Diese Wahrscheinlichkeiten können aus einem Satz von Trainingsdaten durch eine Maximum-Likelihood-Methode geschätzt werden. Bei der Kombination der Modelle läuft dies im Wesentlichen darauf hinaus, das Auftreten der verschiedenen Arten von Übergängen im Datensatz zu zählen. Daher ist die implizite Gewichtung der einzelnen Sensoren nicht wirklich ein Problem.
Obwohl die Art und Weise, wie die optimale Genstruktur gefunden wird, im Geiste der oben beschriebenen dynamischen Programmierung ähnelt, sieht sie in der Praxis ganz anders aus. Das liegt daran, dass die dynamische Programmierung auf der Ebene der einzelnen Zustände in allen Teilmodellen durchgeführt wird; es gibt mehr als 200 solcher Zustände in VEIL. Da das Modell vollständig probabilistisch ist, kann man für eine gegebene DNA-Sequenz die Wahrscheinlichkeit einer beliebigen Abfolge von Zuständen berechnen. Diese Zustandsfolge (ein so genannter Pfad) bestimmt die Zuordnung von Exons und Introns. Verläuft der Pfad durch das Exon-Modell, wird dieser Teil der Sequenz als Exon bezeichnet; verläuft er durch das Intron-Modell, wird er als Intron bezeichnet, und so weiter. Der Algorithmus der dynamischen Programmierung, der so genannte Viterbi-Algorithmus, findet für eine gegebene Sequenz den wahrscheinlichsten Pfad durch das Modell, und daraus wird die vorhergesagte Genstruktur abgeleitet (siehe Rabiner (1989) für eine allgemeine Einführung in HMMs).
Dieses probabilistische Modell hat den Vorteil, dass das Problem der Gewichtung der einzelnen Sensoren gelöst wird. Die Maximum-Likelihood-Schätzung der Parameter ist nachweislich optimal, wenn genügend Trainingsdaten vorhanden sind und die statistische Natur der Gene durch ein solches Modell beschrieben werden kann. Eine Schwachstelle von VEIL ist das Exon-Modell erster Ordnung, das wahrscheinlich nicht in der Lage ist, die Statistik der kodierenden Regionen zu erfassen, und die meisten anderen Methoden verwenden Modelle vierter oder fünfter Ordnung.
Ein HMM-basierter Genfinder namens HMMgene wird derzeit entwickelt. Die grundlegende Methode ist die gleiche wie VEIL, aber sie enthält mehrere Erweiterungen der Standard-HMM-Methodik, die von Krogh (1997) beschrieben werden. Eine der wichtigsten ist, dass die kodierenden Regionen durch eine inhomogene Markov-Kette vierter Ordnung anstelle einer Kette erster Ordnung modelliert werden. Dies geschieht durch eine fast triviale Erweiterung des Standard-HMM-Formalismus, die eine Markov-Kette beliebiger Ordnung in einem Zustand des Modells zulässt, während das Standard-HMM eine einfache unbedingte Wahrscheinlichkeitsverteilung über die vier Basen hat (entsprechend 0. Ordnung). Das Modell ist rahmensensitiv und kann eine beliebige Anzahl von Genen und Teilgenen vorhersagen, so dass die Gesamtstruktur des Modells wie in Abbildung 11.4 aussieht, wobei Übergänge hinzugefügt wurden, um den Beginn und das Ende von Introns zu berücksichtigen, wie in Abbildung 11.3.
Wie bereits erwähnt, funktioniert die Methode der Maximum-Likelihood-Schätzung gut, wenn die Modellstruktur die wahre Statistik der Gene beschreiben kann. Dies ist eine sehr idealisierte Annahme, und deshalb verwendet HMMgene eine andere Methode zur Schätzung der Parameter, die als bedingte maximale Wahrscheinlichkeit bezeichnet wird (Juang und Rabiner, 1991; Krogh, 1994). Grob gesagt, maximiert die maximale Wahrscheinlichkeit die Wahrscheinlichkeit der DNA-Sequenzen im Trainingssatz, während die bedingte maximale Wahrscheinlichkeit die Wahrscheinlichkeit der Genstrukturen dieser Sequenzen maximiert, was uns ja interessiert. Diese Art der Optimierung ist konzeptionell ähnlich wie bei GeneParser, wo die Vorhersagegenauigkeit ebenfalls optimiert wird. HMMgene verwendet auch einen dynamischen Programmieralgorithmus, der sich vom Viterbi-Algorithmus zur Vorhersage der Genstruktur unterscheidet. Alle diese Methoden haben zu einer hohen Leistung von HMMgene beigetragen.
Genie ist ein weiteres Beispiel für ein probabilistisches Zustandsmodell, das als verallgemeinertes HMM bezeichnet wird (Kulp et al., 1996; Reese et al., 1997). Abbildung 11.4 ist in der Tat die Zustandsstruktur von Genie, und sowohl diese Abbildung als auch Abbildung 11.2 sind im Wesentlichen von Kulp et al. (1996) übernommen. In Genie sind die Signalsensoren (Spleißstellen) und die Inhaltssensoren (Kodierungspotential) neuronale Netze, deren Output als Wahrscheinlichkeiten interpretiert wird. Diese Interpretation erfordert die Schätzung zusätzlicher Wahrscheinlichkeitsparameter, die wie Gewichte auf den Sensoren wirken. Obwohl es also als probabilistisches Modell formuliert ist, tritt das Gewichtungsproblem immer noch verschleiert auf. Der Algorithmus für die Vorhersage ist fast identisch mit dem Algorithmus der dynamischen Programmierung aus dem letzten Abschnitt. Eine Version von Genie beinhaltet auch Datenbankähnlichkeiten als Teil des Exon-Sensors (Kulp et al., 1997).
Es gibt zwei Hauptvorteile verallgemeinerter HMMs im Vergleich zu Standard-HMMs. Erstens können die einzelnen Sensoren von beliebigem Typ sein, wie z.B. neuronale Netze, während sie bei einem Standard-HMM durch den HMM-Rahmen eingeschränkt sind. Zweitens kann die Längenverteilung (z. B. von Kodierungsbereichen) explizit berücksichtigt werden, während die natürliche Längenverteilung für ein HMM eine geometrische Verteilung ist, die exponentiell mit der Länge abnimmt. Es ist jedoch möglich, eine ziemlich fortschrittliche Längenmodellierung in einem HMM zu haben, wenn mehrere Zustände verwendet werden (Durbin et al., 1998). Der Vorteil eines Systems wie HMMgene ist hingegen, dass es sich um ein einziges integriertes Modell handelt, das für eine maximale Vorhersagegenauigkeit auf einmal optimiert werden kann.
Ein weiterer Genfinder, der auf einem verallgemeinerten HMM basiert, ist GENSCAN (Burge und Karlin, 1997). Der Hauptunterschied zwischen der Zustandsstruktur von GENSCAN und der von Genie oder HMMgene besteht darin, dass GENSCAN die Sequenz in beiden Richtungen gleichzeitig modelliert. Bei vielen Genfindern, wie den oben beschriebenen, werden Gene zuerst auf einem Strang vorhergesagt und dann auf dem anderen. Die gleichzeitige Modellierung beider Stränge wurde sehr erfolgreich in GeneMark durchgeführt, und eine ähnliche Methode ist in GENSCAN implementiert. Ein Vorteil (und vielleicht der wichtigste) ist, dass diese Konstruktion die Vorhersage von sich überschneidenden Genen auf den beiden Strängen vermeidet, die im menschlichen Genom vermutlich sehr selten sind. GENSCAN modelliert eine beliebige Anzahl von Genen und Teilgenen wie HMMgene. Die Sensoren in GENSCAN sind ähnlich wie die in HMMgene verwendeten. So ist beispielsweise der Kodierungssensor eine inhomogene Markov-Kette fünfter Ordnung. Bei den Signalsensoren handelt es sich im Wesentlichen um positionsabhängige Gewichtsmatrizen, die denen von HMMgene ebenfalls sehr ähnlich sind, aber bei den Spleißstellenmodellen gibt es erweiterte Funktionen. GENSCAN modelliert auch Promotoren und die 5′ und 3′ UTRs.