Database Reference
In-Depth Information
oberste Reihe des HMM in Abbildung 13.17 besteht aus
delete states
, die keine Ami-
nosauren erzeugen, sondern lediglich die Funktion haben, einzelne Positionen in den
alignments
zu uberspringen und damit die Modellierung von
gaps
ermoglichen. Im
Prinzip bewegt man sich von links nach rechts durch das Modell, entlang der ein-
gezeichneten Pfeile. Nur die
insert states
gestatten Schleifen (
loops
), um mehrfache
Einfugungen zwischen
match states
modellieren zu konnen. Die Ubergangswahr-
scheinlichkeit vom Zustand q zum Zustand q
wird mit
(q
|
q) bezeichnet.
Ein Weg q
1
,...,q
N
durch dieses Modell erzeugt nun eine Sequenz von Ami-
nosauren ξ
1
,...,ξ
L
mit einer bestimmten Wahrscheinlichkeit. Im Allgemeinen ist
N
T
= L,da
insert states
mehrfach Aminosauren produzieren konnen, wahrend
dele-
te states
gar keine Aminosauren hervorbringen. Sei ξ
l(i)
die im Zustand q
i
erzeug-
te Aminosaure. Die Wahrscheinlichkeit
Prob
(ξ
1
,...,ξ
L
,q
1
,...,q
N
), dass der Weg
q
1
,...,q
N
genommen wird und die Sequenz ξ
1
,...,ξ
L
generiert, berechnet sich dann
zu
3
N
Prob
(ξ
1
,...,ξ
L
,q
1
,...,q
N
)=
T
(m
N+1
|
q
N
)
·
T
(q
i
|
q
i−1
)P (x
l(i)
|
q
i
)
i=1
wobei q
0
= m
0
bzw. q
N+1
= m
N+1
ein fiktiver Anfangs- bzw. Endzustand ist und
man P (ξ
l(i)
|
q
i
) = 1 setzt, falls es sich bei q
i
um einen
delete state
handelt.
Die Wahrscheinlichkeit, mit der eine Proteinsequenz ξ
1
,...,ξ
L
von einem sol-
chen HMM erzeugt wird, ist dann
Prob
(ξ
1
,...,ξ
L
)=
Prob
(ξ
1
,...,ξ
L
,q
1
,...,q
N
)
(13.31)
q
1
,...,q
N
erzeugt
ξ
1
,...,ξ
L
Die Summation uber alle moglichen Wege fuhrt auf eine exponentielle Komplexitat.
Mit Hilfe von Hidden Markov Models einer einfacheren Topologie und dem Propaga-
tionsalgorithmus aus Abschnitt 13.3 lasst sich
Prob
(ξ
1
,...,ξ
L
) allerdings wesentlich
effektiver berechnen.
Man behandelt die (unbekannten) Zustande als versteckte Zustande H
i
,die
beobachtbare Merkmale O
i
-namlich gerade die Aminosauren einer Sequenz - mit
gewissen Wahrscheinlichkeiten P (o
i
|
h
i
) erzeugen. Ein passendes Modell ist (aus-
schnittweise) in Abbildung 13.18 zu sehen. Dies ist ein sehr einfaches HMM und
insbesondere ein Bayessches Netz, dessen Unabhangigkeitsstruktur durch die Rela-
tionen
H
i
{H
1
,O
1
,...,H
i−2
,O
i−2
,O
i−1
}|H
i−1
,
i≥ 3
und
O
i
{
H
1
,O
1
,...,H
i−1
,O
i−1
}|
H
i
,
i
≥
2
beschrieben wird. Der zugehorige Verbindungsbaum hat die in Abbildung 13.19
gezeigte Form. Entlang dieses Baumes lassen sich nun die notigen Propagations-
schritte zur Berechnung der gesuchten Wahrscheinlichkeit
Prob
(ξ
1
,...,ξ
L
)mitei-
ner Variante des Spiegelhalter-Lauritzen-Algorithmus (s. Abschnitt 13.3) bzw. des
3
Eigentlich musste man hier und in den folgenden Formeln korrekt
Prob
(
·|model
)schreiben,da
naturlich die Parameter des Modells hier ganz wesentlich eingehen.
