> next') ;?> up') ;?> previous'); ?>
Next: Analyse von Proteinsequenzen für Up: Bioinformatik Previous: Bioinformatik

Ein neues Verfahren zum Lernen von Hidden-Markov-Modellen

Hidden-Markov-Modelle (HMM) sind eine Klasse von stochastischen Modellen, die schon für eine Vielzahl von Anwendungsgebieten, von der Spracherkennung bis zur Simulation biochemischer Prozesse in Zellmembranen, erfolgreich eingesetzt wurden. Am ZAIK werden z.B. HMM auch für die Analyse und Simulation ökonomischer Zeitreihen, genauer von Bausparverträgen, benutzt.

HMM bestehen aus einer Markov-Kette, also einer ,,gedächtnislosen`` Folge von Zufallsvariablen, den sogenannten Zuständen, die aber nicht direkt zu beobachten sind. Weiterhin gibt es für jeden dieser Zustände eine diskrete oder kontinuierliche Verteilung, anhand derer dann die beobachtbaren Ausgaben erzeugt werden. Ein HMM impliziert eine Wahrscheinlichkeitsverteilung auf der Menge aller möglichen Sequenzen von Ausgaben.

Für DNA-Sequenzen, also Abfolgen der Buchstaben A, C, G und T, kann in einem einfachen Beispiel ein Zustand des HMM jeweils einer funktional ausgezeichneten Region des DNA-Moleküls entsprechen (coding vs. non-coding). Diese unsichtbaren Zustände zeichnen sich z.B. durch unterschiedliche Sequenzkompositionen, also Unterschiede in der beobachteten relativen Häufigkeit der einzelnen Buchstaben A, C, G und T zwischen den verschiedenen Regionen aus. Ein mit entsprechendem Datenmaterial trainiertes HMM, kann dann z.B. für die Erkennung von kodierenden Regionen benutzt werden.

Abbildung: Ein HMM mit drei Zuständen als gerichteter Graph mit diskreten Ausgabeverteilungen. Die Kantengewichte sind als Übergangswahrscheinlichkeiten zwischen Zuständen zu interpretieren.
\begin{figure}\centerline{\epsfig{file=bioinfo/hmm.eps, width = 8cm} }\end{figure}

Weitere Anwendungsfelder von HMM in der Bioinformatik sind das Finden von Genen, Strukturvorhersagen, Verfahren zur Motivsuche, Finden entfernt homologer Proteinsequenzen, Multiple Alignments, Klassifizierung von DNA/Proteinsequenzen (Transkriptionseinheiten) und Modellierung von Proteinfamilien.

In der Literatur zu HMM, insbesonders in dem bekannten Tutorial-Artikel von Rabiner, werden drei Probleme in Bezug auf HMM erwähnt:

  1. Wie kann man die Wahrscheinlichkeit ausrechnen, dass ein bestimmtes Modell eine gegebene Ausgabensequenz ausgerechnet hat?
  2. Gegeben ein Modell und eine Ausgabensequenz, wie kann man die ,,dazugehörende`` Sequenz an ,,versteckten`` Zuständen rekonstruieren?
  3. Wie kann man die Parameter eines HMM so trainieren, dass die Wahrscheinlichkeit, eine bestimmte Ausgabensequenz zu erzeugen, maximiert wird?

Da die von Rabiner betrachteten Anwendungen in der Spracherkennung auf natürliche Art und Weise ein geeignetes HMM nahelegten, ist es verständlich, dass eine viel grundlegendere Frage nicht gestellt wurde. Wie wählt man die Struktur oder Topologie eines HMM, also die Anzahl der Zustände und der zwischen ihnen erlaubten bzw. verbotenen Übergänge?

Die Frage ist aus zweierlei Gründen von Bedeutung. Zum einem ist die Anzahl der zu trainierenden Parameter, vereinfacht gesprochen, quadratisch in der Anzahl der Zustände. Bei einer fest vorgegebenen, beschränkten Datenmenge, wie es in der Praxis fast immer der Fall ist, ergeben sich damit Trainingsfehler für die Parameter, die mit der Modellgröße zunehmen. Des weiteren läuft man mit einer zu großen Anzahl an Parametern Gefahr, das Modell ,,überzutrainieren``, also Generalisierungsfähigkeit zu verlieren. Zum anderen geht die Anzahl der Zustände auch quadratisch in die Laufzeit der Algorithmen ein, die z.B. für die Datenbanksuche nach verwandten Proteinen benutzt werden.

Sofern das Anwendungsproblem nicht klare Vorgaben lieferte, wurden bisher weitgehend adhoc Verfahren, z.B. die sogenannte Model-Surgery, zur Auswahl einer geeigneten Topologie verwendet. Im Rahmen einer Promotion wurde am ZAIK ein Bayes'scher Ansatz entwickelt, der nach Vorgabe einer Prior-Distribution, die als erwartete Fehlerverteilung der Daten zu interpretieren ist, auf der Basis eines Clusterverfahrens Topologie und Modellparameter lernt.

Abbildung: Sequenzen werden in einen sog. Prefix-Baum eingefügt. Kanten sind mit Ausgabesymbolen gekennzeichnet. Die Knotengewichte entsprechen den Häufigkeiten von Prefixen. Z.B. bedeutet das Knotengewicht 22 des Knotens $ a$, das der Prefix 00 22-mal in den Eingabesequenzen vorkam. In diesem Baum werden die Knoten geclustert, wobei die Cluster dann Zuständen des HMM entsprechen. Die für das Clusterverfahren benutzten Abstände ergeben sich durch Betrachtung der implizit durch die Knotengewichte gegebenen relativen Häufigkeiten (vgl. Wurzel und Blätter der beiden ausgezeichneten Teilbäume).
\begin{figure}\centerline{\epsfig{file=bioinfo/prefix-tree-cluster.fh.eps, width = 8cm} }\end{figure}

Mit diesem Verfahren können, ohne Bias für bestehende Problemstellungen, Modelle mit einer geringeren Anzahl an Zuständen und einer größeren Generalisierungsfähigkeit gelernt werden, die darüberhinaus für die typischen Bioinformatik-Anwendungen einen klaren Laufzeitvorteil bieten.


next') ;?> up') ;?> previous'); ?>