Warum ist dieses Wissen wichtig? Hidden-Markov-Modelle werden häufig zur Modellierung in bioinformatischen Fragestellungen verwendet; beispielsweise zur Charakterisierung von Proteinfamilien. 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 kennen,
  • die Arbeitsweise der Algorithmen, 
  • den Einfluss (Übergangs- und Emissionswahrscheinlichkeiten)
    auf das Ergebnis der Algorithmen

besser verstanden haben.

   
Übung HMM_1, Hidden-Markov-Modelle
   
  Mit dieser Übung sollen das Konzept der Hidden-Markov-Ketten (HMMs) verdeutlicht werden. Wir stellen uns folgendes Szenario vor:
 

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.

Ebenso sind 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 vorstellbar, dass die Anzahl der Kombinationen extrem ansteigt, sobald 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?
  Hier finden Sie die Lösung zur Aufgabe.
   
Übung PFAM_1
   
  Mit Hilfe von HMMs werden Proteinfamilien modelliert. Eine der anerkannt besten Sammlungen ist PFAM. 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!

Zu welcher PFAM-Familie gehört es?
Hinweis Benutzen Sie die Sequenz zum Suchen.
  Wie gross ist der E-Value bzw. der Score für Ihre Suche? Ab welchem Score kann man bei dieser Familie mit hoher Sicherheit auf Zugehörigkeit schliessen?
Hinweis Beachten Sie hierzu die Angaben unter der Rubrik HMM information, die Sie per Menü Curation & models erreichen.
  Die PFAM-Familie gehört zu einem "Clan", von Proteinfamilien. Wie wird dieser beschrieben?
 
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
   
  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
   
Übung HMM_2 CpG-Inseln
   
  M. Stahnke hat ein Applet geschrieben, mit dem HMMs studiert werden können.
Aktivieren Sie das Applet in einem separaten Fenster. 
  
cggggtcgtggccgggcagaggggctcctcacttcccagtaggggcggccgggcagaagc
gcccctcacctcccggatggggcggctggccgggcgggggctgaccccccaccaccctcc
cggacggggcagctggccaggcagagcggctcctcacttcccagtaggggcggccgggca
gaggcgcccctcacctcctggatagggcggctggccgggcggggggctgtcccccccacc
tccctcccggatggggcggctggctgggcagaggggtcctcacttcccagtaggggcggc
cgggcagaggcgcccctcacctcccggacggggcggccggccggaaggggggctgacccc
cccacctccctcccggacggggcggctggccgggcagaggggctcctcactttccaataa
gggcggccgggcagaggcgcccctcacctcccggacggggtggctggccaggcggggggc
tgatccccccacctccctcccggacggggcggctggccgggtggggggctgagccccccg
ctcgctccgggactgggcgggtgggccggcgggggggctgacccccccccctccccccgg
cccggggcggccggccggaaagggtgcgacccccccacccccctcccggacagggcggct
ggccgacgccccccccgcctccctcccggacggggcggctggccgggcagaggagctcct
cactttccagtaggggcggccaggcagaggcgcccctcacctcccggacggggcggctgg
ctgggcggggggctgaccccccctcccccttcccggacagggcggctggccgggcggggg
ctgacccccccacctccctcccgggcggggcggctggccgggcagaggggctcctcactt
cccagtaggggcggccgggcagaggcgcccctcacctcccggacggggcggctggccaga
tggggggctgatccccccacctccctcccggacggggcggctggccgggcggggggctga
ccccccacctccctcccagactgggcggctggctgggcggggggctgacccccccacctc
cctcccggacggggcggctggccgggcagaggggtcctcacttcccagtaggggcggccg
ggcagaggcgcccctcacctcccggacggggcggctggccgggcggggggctgacccccc
ctcccccctcccggatggggcggctggccaggcggggggctgtcccccccacctccctcc
cggacggggcggctggccgggcagaggggtcctcacttcccagtaggggcggccgggcag
aggcgcccctcacctcccggaaggggcggccggccggaaggagggctgacccccccacct
ccctcccggacggggcggctggccgaccccccccccgcctccctcccggacggggcggct
ggccgggcagaggggctcctcactttccagtaggggcggccgggcagaggcgcccctcac
ctcccggacggggcggctggccaggcggggggctgatccccccacctccctcccggacgg
ggcggctggccgggcagaggggtcctcacttcccagtaggggaggccgggcagaggcgcc
cctcacctcccggacggggcggccagccgggcggggggctgacccccccacctccctccc
ggacggggtggctgccgggcggagacgctcctcacttcccagacggggtggttgccggac
ggaggggctcctcacttctcagacggggcggttgccaggcagagggtttcctcacttctc
agacggagcggccgggcagagacgctcctcacctcccagacagggttgcggcccagcaga
ggcgctcctcacatcccagacagggcggtggggcagaggtgctccccacatctcagacga
tgggcggccgggcagagacgctcctcacttcctagatgggatggcggcggggaagaggtg
ctcctcgcttcctagatgggatggcggccgggcagagacgctcctcactttccagactgg
gcagccaggcagaggggctcctcatatcccagacgatgggcggccaggcagagacgctcc
tcacttcccagacggggtggcggccgggcagaggctgcaatctcggctctttgggaggcc
aaggcaggcggctgggaggtgtaggttgtagtgagctgagatcacgccactgcactccag
cctgggcaccattgagcactgagtgaacgagactccatctgcaatcccggcacctcggga
ggccgaggctggcggatcactcgcggttaggagctggagaccagcccggccaacacagcg
aaaccccgtctccaccaaaaaaaaacgaaaaccagtcaggcgtggcggcgcgcgcctgca
atcgcaggcactcg

CpG Insel aus Homo sapiens

Gegeben sei die oben angegeben CpG-Insel aus Homo sapiens. 

Stellen Sie zunächst den Modus im Applet auf CpG Inseln.

Übernehmen Sie die Sequenz per copy and paste in das Eingabefenster des Applets und lassen Sie den Viterbi-Pfad berechnen. Übernehmen Sie aus dem Ausgabefenster das Ergebnis und speichern Sie es ab.

Ändern Sie anschließend die beiden Wahrscheinlichkeiten q+ und q- auf jeweils 0.5. Sie müssen jede Eingabe mit <return> abschließen. 

Die Angabe zur Länge ist nur für das Generieren von Emissionen, also künstlichen Sequenzen, relevant.  

Übernehmen Sie wiederum die Sequenz per copy and paste in das Eingabefenster des Applets und lassen Sie den Viterbi-Pfad berechnen.

Sichern Sie wiederum die Ausgabe.
Interpretieren Sie die Ausgabe: Wie viele Inseln werden gefunden, welche Länge haben Sie? Vergleichen Sie die Ergebnisse und erklären Sie die Unterschiede.

Hier finden Sie einen Server, der einen fensterbasierten Algorithmus zur Vorhersage von CpG-Inseln anbietet. 

Wieviele Inseln werden mit der Standardeinstellung gefunden?
    
Übung HMM_3 Baum-Welch
Stellen Sie den Modus des Applets auf Unehrliches Kasino und die Anzahl der Zustände auf 1. Übernehmen Sie die oben angegebene Sequenz der CpG-Insel in das Eingabefenster und stoßen Sie durch Drücke der Taste Baum-Welch die Schätzung der Parameter mehrmals an. 
Vergleichen und interpretieren Sie die berechneten Emissionswahrscheinlichkeiten. 

Welche Bedeutung haben sie?

Vergleichen Sie Ihre Vermutung mit Angaben in der Annotation der Sequenz.
 
Übung HMM_4 Allgemeines Hidden-Markov-Modell
64246566651623316266626633666666653656236146156666
11626661664461335662464664266362666664626666611246
66661635636665662265142241662231161666664266631144
63335515366166316561664356214666616166516136612662
56362566663616663336266566626666665234363126666666
63624646236226644463666622451266166666614663236226

 Ausgewürfelte Sequenz

Die oben angegebene Sequenz wurde mit einem "unehrlichen Würfel" mit den Emissionswahrscheinlichkeiten aus Abb. 15.8 generiert. 
Wie kann diese unter Verwendung des Applets erzeugt werden? 
Tipp: Verwende die Einstellung Allgemeines Hidden-Markov-Modell.

Stellen Sie den Modus auf Unehrliches Kasino, übertragen Sie mit copy and paste die Sequenz in das Eingabefenster und berechnen Sie durch Betätigen der entsprechenden Taste den Viterbi Pfad.
Speichern Sie für den folgenden Vergleich die Ergebnisse dieser Berechnung zwischen.   (I)
Weshalb gibt es Teilpfade, die dem fairen Würfel zugeordnet werden? 

Tipp: Sehen Sie sich die Übergangswahrscheinlichkeiten vom unfairen zum fairen Würfel an. In welchem Verhältnis steht diese Wahrscheinlichkeit zur erwarteten Länge einer unfairen Sequenz?  

Stellen den Modus um auf Allgemeines Hidden-Markov-Modell.

Kopieren Sie die folgenden Parameter in das Eingabefenster und drücken Sie die Taste lese Modellparameter...
 
# Neuer Parametersatz
# Die Namen der Zustände: 
F L

# Die Startwahrscheinlichkeiten:
0.5 0.5
# Die Übergangsmatrix:
0.95 0.05
0.003 0.997

# Das Emissionsalphabet:
123456

# Die EmissionsWkeiten:
0.166666 0.166666 0.166666 0.166666 0.166666 0.166666
0.1 0.1 0.1 0.1 0.1 0.5

Parametersatz für Allgemeines HMM.
Übergeben Sie nochmals die oben angegebene, ausgewürfelte Sequenz und lassen Sie den Viterbi-Pfad berechnen. Vergleichen Sie die gewonnenen Ergebnisse mit der Ausgabe unter (I).
  Begründen Sie, weshalb nun im Viterbi-Pfad keine Teilsequenzen enthalten sind, die dem fairen (U) Würfel zugeordnet werden. 

Tipp: Vergleichen Sie die  Wahrscheinlichkeiten aus dem neuen Parametersatz mit den Standardeinstellungen.

Übung HMM_5 Der Pfad wahrscheinlichster Zustände
Wenn Sie diese Aufgabe unmittelbar nach HMM_3 ausführen, kann der nächste Schritt übersprungen werden, ansonsten:
 
    Stellen Sie den Modus auf Allgemeines Hidden-Markov-Modell übertragen Sie mit copy and paste den oben angegebenen Parametersatz und übernehmen Sie ihn in das Modell durch Drücken der entsprechenden Taste.

Kopieren Sie die oben angegebene "Ausgewürfelte Sequenz" in das Eingabefenster.

Drücken Sie die Taste max a posteriori Pfad.

 
  Betrachten Sie den Pfad wahrscheinlichster Zustände im Ausgabefenster. Offensichtlich ist dieser ebenfalls geeignet, eine korrekte Vorhersage des zugrundeliegenden Pfades (Verwendung der Würfel) zu liefern.

Versuchen Sie ein HMM zu konstruieren, bei dem diese Übereinstimmung nicht gegeben ist.

 

Was Sie jetzt verstanden haben sollten

 HMMS sind ein mächtiges stochastisches Werkzeug, das in der Bioinformatik für viele Anwendungen geeignet ist.

Wir haben uns mit obigen Übungen ein grundlegendes Verständnis des Modelles an sich, sowie der wichtigsten Prinzipien einer Anwendung erarbeitet.