Warum ist dieses Wissen wichtig? Hidden-Markov-Modelle werden häufig zur Modellierung in bioinformatischen Fragestellungen verwendet; beispielsweise zur Charakterisierung von Proteinfamilien oder zur Vorhersage der Lage von Genen. Um Möglichkeiten und Grenzen dieses Ansatzes abschätzen zu können, ist es wichtig, sich mit den wichtigsten Algorithmen vertraut zu machen.
Bezug Die theoretischen Grundlagen finden Sie in den Kapiteln 15 "Hidden-Markov-Modelle" und 16 "Profil-HMMs zur Modellierung von Proteinfamilien".
Lernziel
Nach dem Bearbeiten der Übung sollten Sie
  • eine der wichtigsten Datenbanken für Proteinfamilien kennen,
  • die Arbeitsweise der Algorithmen, 
  • den Einfluss der Übergangs- und Emissionswahrscheinlichkeiten auf das Ergebnis der Algorithmen verstanden haben.
   
Übung HMM_1, Hidden-Markov-Modelle
   
  Mit dieser Übung soll das Konzept der Hidden-Markov-Ketten (HMMs) verdeutlicht werden. Wir stellen uns ein experimentelles Szenario vor, das durch das folgende Zustandsdiagramm beschrieben wird:
   
 

Zustandsdiagramm für Münzwurfmodell
   
  In einem Experiment werden zwei Münzen (hier Fair und Unfair genannt) verwendet, die bei jedem Wurf Kopf (K) oder Zahl (Z) als "Emission" liefern. In obiger Abbildung sind die Wahrscheinlichkeiten für das Auftreten dieser Emissionen angegeben. Beim Wurf der unfairen Münze tritt z. B. mit einer Wahrscheinlichkeit von 75% die Emission "Kopf" auf, d. h., es gilt eU(K) = 0.75.

Neben den Emissionswahrscheinlichkeiten sind auch die Übergangswahrscheinlichkeiten durch obige Angaben determiniert. p(F,F) ist z. B. die Wahrscheinlichkeit dafür, dass in einem Experiment nach der fairen Münze wiederum die faire Münze verwendet wird.

Zu Beginn wird jeweils mit den angegebenen Wahrscheinlichkeiten eine der beiden Münzen ausgewählt.

Stellen wir uns nun folgendes Experiment vor:

Es seien zwei Münzen geworfen worden und es sei jeweils die Emission "Kopf" beobachtet worden.

Beantworten Sie nun folgende Frage:
   
Aufgabe Welche Münze wurde mit höchster Wahrscheinlichkeit bei welchem Wurf verwendet?
   
Hinweis Für diesen einfachen Fall können wir noch alle Kombinationen durchrechnen.

Bestimmen Sie hierzu die Wahrscheinlichkeiten für alle möglichen Kombinationen und wählen Sie diejenige mit der höchsten Gesamtwahrscheinlichkeit aus. Es ist sinnvoll, eine Tabelle anzulegen und zunächst die Einzelwahrscheinlichkeiten einzutragen, ehe Sie die Gesamtwahrscheinlichkeit berechnen. Wir haben es aufgrund der Situation im Experiment mit einer Folge ∏1 , ∏2 von zwei Zuständen zu tun. In der folgenden Tabelle ist mit ∏i jeweils ein Zustand gemeint. Jeder Zustand kann entweder vom Typ Fair oder Unfair sein. Zu ermitteln ist, welche der vier möglichen Kombinationen (FF, FU, UF, UU) die wahrscheinlichste ist unter Berücksichtigung der Beobachtung (Emission) Kopf, Kopf.

 
 
p(Start,∏1) e∏1(K) a∏1∏2 e∏2(K) p(Gesamt)  
          ∏1 = F, ∏2 = F
          ∏1 = F, ∏2 = U
          ∏1 = U, ∏2 = F
          ∏1 = U, ∏2 = U

 
  Durch Auswahl der wahrscheinlichsten Kombination haben Sie den Viterbi-Pfad berechnet. Es ist leicht einzusehen, dass die Anzahl der Kombinationen extrem ansteigt, sobald in einem Experiment mehr Zustände und Emissionen vorkommen. Daher ist ein Verfahren, das sämtliche Kombinationen durchrechnet, für größere Probleme NICHT geeignet. Wir haben aber bereits Algorithmen kennengelernt, die in solchen Situationen weiterhelfen. Welche waren dies?
  Hier finden Sie die Lösung zur Aufgabe.
   
Übung HMM_2, Parametrisieren eines Profil-HMMs
   
 

Gegeben sei das folgende multiple Sequenzalignment.

  
0 ACYLVMVNC
1 ACYII-V-C
2 GC-IV-INC
3 GC-LV-V-C
4 ACYLLMIAC
5 GCYL--IAC

MSA
   
  Entwickeln Sie hierfür ein Profil-HMM nach der in Abschnitt 16.3 des Buches skizzierten, einfachen Methode.
   
Hinweise Bestimmen Sie zunächst die Architektur des HMMs. Wie viele Matchzustände sollen eingeführt werden?
Schätzen Sie die Übergangswahrscheinlichkeiten für alle, aus M2 und M5 herausführenden Übergänge sowie die Emissionswahrscheinlichkeiten für die Zustände M2 , I2 sowie M5 und I5.
Verwenden Sie zur Berechnung der Wahrscheinlichkeiten die Laplacesche Regel: Initialisieren Sie sämtliche Variablen zum Zählen von Übergängen und Emissionen jeweils mit dem Wert 1.

Hier finden Sie eine Lösung.
   
Übung PFAM_1
   
  Mit Hilfe von HMMs werden Proteinfamilien modelliert. Eine der anerkannt besten Sammlungen ist PFAM, die Sie mittels HMMER abfragen können. Mit der folgenden Übung erlernen Sie den Umgang mit dieser Datenbank.
 

Gegeben sei die folgende Sequenz:

>Unbekannt
TDIAQLLGKDADNLLQHRCMTIPSDQLYLPGHDYVDRVMIDNNRPPAVLRNMQTLYNTGR
LAGTGYLSILPVDQGVEHSAGASFAANPLYFDPKNIVELAIEAGCNCVASTYGVLASVSR
RYAHRIPFLVKLNHNETLSYPNTYDQTLYASVEQAFNMGAVAVGATIYFGSEESRRQIEE
ISAAFERAHELGMVTVLWAYLRNSAFKKDGVDYHVSADLTGQANHLAATIGADIVKQKMA
ENNGGYKAINYGYTDDRVYSKLTSENPIDLVRYQLANCYMGRAGLINSGGAAGGETDLSD
AVRTAVINKRAGGMGLILGRKAFKKSMADGVKLINAVQDVYLDSKITIA

Unbekanntes Protein
 
  Charakterisieren Sie das Protein mit Hilfe der PFAM-Datenbank.
   
Hinweis Geben Sie die Sequenz per copy&paste ein und wählen Sie als HMM Database Pfam.
Klicken Sie anschließend bitte auf Submit.
  Zu welcher PFAM-Familie gehört das Protein?
Wie gross ist der E-Value bzw. der Score für diese Suche?
Ab welchem Score kann man bei dieser Familie mit hoher Sicherheit auf Zugehörigkeit schliessen?
   
  Um diese Fragen beantworten zu können, müssen Sie die Einträge zur Proteinfamilie studieren, die Sie durch Anklicken des Namens öffnen können. Beachten Sie insbesondere die Angaben die Sie per Menü Curation & model/HMM information erreichen.
   
  Die PFAM-Familie gehört zu einem "Clan", von Proteinfamilien. Wie wird dieser beschrieben?
Um funktionsrelevante Residuen zu identifizieren, empfiehlt es sich, die Sequenzvariabilität genauer zu untersuchen.
   
  Welche Positionen sind in diesem Protein am stärksten konserviert?
   
Hinweis Studieren Sie zur Beantwortung dieser Frage jeweils das aus dem Seed abgeleiteten multiple Sequenzalignment und das HMM Logo. Verwenden Sie die Nummerierung des HMM-Logos für die Angabe der Positionen.
   
Übung PFAM_2
   
  In dieser Übung wollen wir die Parameter eines PFAM-HMMs genauer betrachten. Diese Datei beschreibt das HMM für eine Proteinfamilie komplett.

  Erläutern Sie den Aufbau und bestimmen Sie die Wahrscheinlichkeit für das Auftreten (Emissionswahrscheinlichkeit) eines L an Position 4.
Gibt es Positionen, an denen Insertionen wahrscheinlicher sind als sonst?
   
Hinweise Die Angaben in diesen beiden Dateien sollten weiterhelfen: 1, 2
 

Was Sie jetzt verstanden haben sollten

 HMMs sind ein mächtiges stochastisches Werkzeug, das in der Bioinformatik für viele Anwendungen geeignet ist. Eine Anwendung ist der sehr empfindliche Sequenzvergleich. Die Parameter für ein HMM werden im Falle des Sequenzvergleichs aus speziell zusammengestellten MSAs errechnet.