Alignments mit Hidden Markov Modellen. Wofür sind HMMs gut? Gehört eine Sequenz zu einer...

Alignments mit Hidden Markov Modellen

Wofür sind HMM‘s gut?

Gehört eine Sequenz zu einer bestimmten Familie?

Falls eine Sequenz aus einer Familie stammt, was kann man über ihre interne Struktur sagen?

Markov Kette

Modell zum Generieren von Sequenzen

Die Wahrscheinlichkeit für das Auftreten eines Symbols hängt nur vom Vorgängersymbol ab

Wie wahrscheinlich ist eine Sequenz / Nukleotidfolge

Markov Kette

Beispiel für DNA:

Markov Kette

Transitionswahrscheinlichkeit:

rst = P(xi = t | xi-1 = s)

Wahrscheinlichkeit einer Sequenz:

P(x) = P(xL | xL-1)*P(xL-1 | xL-2)*

..

*P(x2 | x1)*P(x1)

= P(x1)Пi=2rxi-1

xi

Markov Kette

Beginzustand x0 = B mit:

P(x1 = s) = rBs

Endzustand xL+1 = E mit:

P(E | xL = t) = rtE

Hidden Markov Model

Keine 1 zu 1 Übereinstimmung von Zuständen und generierten Symbolen

Einbettung von Markov Ketten in die Zustände

Es gibt bestimmte vordefinierte Wahrscheinlichkeiten, dass ein Zustandübergang erfolgt

Sei ek(b) = P(xi = b | πi-1 = k) die WK, dass Symbol b im Zustand k auftritt (wobei π die Zustandsequenz ist)

HMM

Beispiel: unfaires Casino:

HMM

Beispiel: unfaires Casino:Problem: Wie findet man die richtige (wahrscheinlichste)

Zustandssequenz, die der vorliegenden Symbolsequenz zugrunde liegt?

Viterbi Algorithmus

Beispiel: CpG - Inseln Das Auftreten einer bestimmten Base (A, T, G, C) an einer

bestimmten Stelle ist nicht gleich wahrscheinlich

In bestimmten DNA-Bereichen: Hohe Wahrscheinlichkeit, dass C zu einem T mutiert

Somit kleinere Wahrscheinlichkeit, dass ein C vor einem G steht

Es gibt allerdings Regione in welchen die Mutationswahrscheinlichket (von C zu T) deutlich kleiner ist (zum Beispiel bei den Startregionen diverser Gene)

Viterbi Algorithmus

Beispiel: CpG - Inseln

Markov Kette

Viterbi Algorithmus

Beispiel: CpG - Inseln

Verschiedene Wahrscheinlichkeiten für das Auftreten eines Symbols (A, T, G, C), je nach dem ob es innerhalb (+ Modell) oder ausserhalb (- Modell) der CpG – Inseln stattfindet

Daraus leitet sich die WK rst für jedes dieser beiden Modelle:

rst+ = cst

+/∑t`cst`+ rst

- = cst-/∑t`cst`

-

(wobei cst die Anzahl der Fälle in welchen Symbol t Symbol s folgte ist)

rst+ und rst

- statistisch ermittelbar

Viterbi Algorithmus

+ A C G T - A C G T

A 0.180 0.274 0.426 0.120 A 0.300 0.205 0.285 0.210

C 0.171 0.368 0.274 0.188 C 0.322 0.298 0.078 0.302

G 0.161 0.339 0.375 0.125 G 0.248 0.246 0.298 0.208

T 0.079 0.355 0.384 0.182 T 0.177 0.239 0.292 0.292

Viterbi Algorithmus

Beispiel: CpG – InselnHMM

Viterbi Algorithmus

Ein rekursiver Algorithmus zum Finden des wahrscheinlichsten Pfades π* (mit π* = argmaxP(x, π))

Sei vk(i) die WK eines wahrscheinlichsten Pfades, der in Zustand k endet mit Beobachtung i

Sei vk(i) bekannt für alle i, dann für i+1 gilt:

vl(i+1) = el(xi+1)max(vk(i)rkl)

Viterbi Algorithmus

Versteckte Zustände

Beobachtete Zustände

Initiale WK eines Anfangszustandes

Sonne Fußball spielen Sonne 0.63

Wolken Spazieren Wolken 0.17

Regen Putzen Regen 0.20

- Lesen - -

Viterbi Algorithmus

Wetter heute

Wetter

gestern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Versteckte Zustände

Fußball Spazieren Putzen Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

Viterbi AlgorithmusFußball Putzen Lesen

Sonne

Wolken

Regen

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Viterbi AlgorithmusFußball Putzen Lesen

Sonne

Wolken

Regen

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Viterbi AlgorithmusFußball Putzen Lesen

Sonne

Wolken

Regen

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.63

Viterbi AlgorithmusFußball Putzen Lesen

Sonne

Wolken

Regen

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.63*0.6 ≈ 0.378

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken

Regen

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.63*0.6 ≈ 0.378

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken

Regen

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.17*0.25

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken 0.042

Regen

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.17*0.25 ≈ 0.042

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.2*0.05 ≈ 0.010

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.378

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.378*0.500

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.378*0.500*0.15

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.378*0.500*0.15 ≈ 0.028

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.042

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.042*0.375

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.042*0.375*0,15 ≈ 0.002

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.010*0.125*0.15 ≈ 0.0001

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Max(0.028, 0.002, 0.0001) = 0.028

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Max(0.028, 0.002, 0.0001) = 0.028

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.378*0.25*0.25 ≈ 0.023

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.042*0.125*0.25 ≈ 0.001

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028

Wolken 0.042

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.010*0.675*0.25 ≈ 0.001

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028

Wolken 0.042 0.023

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Max(0.023, 0.001, 0.001) = 0.023

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028

Wolken 0.042 0.023

Regen 0.010

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028

Wolken 0.042 0.023

Regen 0.010 0.033

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028

Wolken 0.042 0.023

Regen 0.010 0.033

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028 0.0007

Wolken 0.042 0.023

Regen 0.010 0.033

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028 0.0007

Wolken 0.042 0.023 0.005

Regen 0.010 0.033 0.006

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028 0.0007

Wolken 0.042 0.023 0.005

Regen 0.010 0.033 0.006

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.378+0.028+0.0007 ≈ 0.407

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028 0.0007

Wolken 0.042 0.023 0.005

Regen 0.010 0.033 0.006

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.378+0.033+0.006 ≈ 0.416

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028 0.0007

Wolken 0.042 0.023 0.005

Regen 0.010 0.033 0.006

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

0.378+0.033+0.006 ≈ 0.417

Viterbi AlgorithmusFußball Putzen Lesen

Sonne 0.378 0.028 0.0007

Wolken 0.042 0.023 0.005

Regen 0.010 0.033 0.006

Wetter heute

Wetter

Ges

tern

Sonne Wolken Regen

Sonne 0.500 0.250 0.250

Wolken 0.375 0.125 0.375

Regen 0.125 0.675 0.375

Beobachtete Zustände

Verst.

Zust.

Fuß

ball

Spazi

eren

Pu

tzen

Lesen

Sonne 0.60 0.20 0.15 0.05

Wolken 0.25 0.25 0.25 0.25

Regen 0.05 0.10 0.35 0.50

WK für Anfangszustand

Sonne Wolken Regen

0.63 0.17 0.2

Max(0.407, 0.416, 0.417) = 0.417

Viterbi Algorithmus

Viterbi Algorithmus

Initialisierung (i = 0): v0(0) = 1, vk(0) = 0 für alle k > 0

Rekursion (i = 1..L): vl(i) = el(xi)maxk(vk(i-1)rkl)

ptri(l) = argmaxk(vk(i-1)rkl)

Terminierung: P(x, π*) = maxk(vk(L)rk0)

π*L= argmaxk(vk(L)(rk0)

Backtracking (i = L..1): π*i-1 = ptri(π* i)

Paarweises Alignment mit HMM

F(i-1, j-1) F(i, j-1)

F(i-1, j)

F(i,j) = max[F(i-1,j-1)+s(xi,yj),

F(i-1,j)-d,

F(i,j-1)-d]

+s(xi, yj)-d

-d

Paarweises Alignieren mit HMM Alignment mit affinen Gapkosten:Optimaler score für ein Alignment von x1..xi und y1..yj, der keinen Gap am Ende

hat

M(i,j) = max[M(i-1,j-1)+s(xi,yj),

Ix(i-1,j-1)+s(xi,yj),

Iy(i-1,j-1)+s(xi,yj)]

Optimaler score für ein Alignment von x1..xi und y1..yj, wo am Ende x mit einen Gap aligniert wird

Ix(i,j) = max[M(i-1,j)-d,

Ix(i-1,j)-e]

Optimaler score für ein Alignment von x1..xi und y1..yj, wo am Ende y mit einen Gap aligniert wird

Iy(i,j) = max[M(i,j-1)-d,

Iy(i,j-1)-e]

L G A xi

L G V yj

L G A xi

L G _ yj

L G _ xi

L G V yj

Paarweises Alignieren mit HMM Alignment mit affinen Gapkosten:

M(i,j) = max[M(i-1,j-1)+s(xi,yj),

Ix(i-1,j-1)+s(xi,yj),

Iy(i-1,j-1)+s(xi,yj)]

Ix(i,j) = max[M(i-1,j)-d,

Ix(i-1,j)-e]

Iy(i,j) = max[M(i,j-1)-d,

Iy(i,j-1)-e]

A|A|C| - - - |A|ATTCCG|A|C|T |ACA|C|T|ACC|T| - - - - - -|C|G|C|- -

Paarweises Alignieren mit HMM Alignment mit affinen Gapkosten:

M(i,j) = max[M(i-1,j-1)+s(xi,yj),

Ix(i-1,j-1)+s(xi,yj),

Iy(i-1,j-1)+s(xi,yj)]

Ix(i,j) = max[M(i-1,j)-d, anderer Block, neue Gapfolge

Ix(i-1,j)-e] selber Block, fortgesetzte Gapfolge

Iy(i,j) = max[M(i,j-1)-d, anderer Block, neue Gapfolge

Iy(i,j-1)-e] selber Block, fortgesetzte Gapfolge

}

}

Paarweises Alignment mir HMM

Paarweises Alignment mir HMM

V L S P KH L _ _ K

Paarweises Alignment mir HMM

V L S P KH L _ _ K

Paarweises Alignment mir HMM

V L S P KH L _ _ K

Paarweises Alignment mir HMM

V L S P KH L _ _ K

Paarweises Alignment mir HMM

V L S P KH L _ _ K

Paarweises Alignment mir HMM

V L S P KH L _ _ K

Paarweises Alignieren mit HMMNFA für Alignment mit affinen Gapkosten: dazugehöriges Wahrscheinlichkeitsmodell:

Paarweises Alignment mit HMM

AA 0.21AC 0.01AG 0.05AT 0.04CA 0.02….

1-2

Match

A- 0.2C- 0.4G- 0.3T- 0.1

Gap Y

1-

-A 0.2-C 0.4-G 0.3-T 0.1

Gap X

1-H B M GX GX M M X A

A - T

- A

A T

T T

1/3 1- 1-2

.21 . 1 .2 .04 …

Begin

Paarweises Alignieren mit HMMDas Wahrscheinlichkeitsmodell mit Begin und End Zuständen:

Paarweises Alignieren mit HMMWas ist neu?

Es wird nicht mehr eine einzelne Sequenz generiert sondern ein paarweises Alignment

Man benötigt eine zusätzliche Dimension und deshalb wird vk(i) zu vk(i,j) erweitert

Paarweises Alignieren mit HMMAngepasster Viterbi Algorithmus:

Initialisierung: vM(0,0) = 1, alle anderen v*(i,0), v*(0,j) sind 0

Rekursion (i = 1..n, j = 1..m): vM(i,j) = pxiyj

max[(1-2δ-τ)vM(i-1,j-1), (1-ε-τ)vX(i-1,j-1), (1-ε-τ)vY(i-1,j-1)]

vX(i,j) = qximax[δvM(i-1,j), εvX(i-1,j)]

vY(i,j) = qyimax[δvM(i,j-1), εvX(i,j-1)]

Terminierung: vE = τmax(vM(n,m),vX(n,m),vY(n,m))

Paarweises Alignieren mit HMMlokales Alignment mit HMM:

Zuerst definieren wir ein Random-Modell:

Paarweises Alignieren mit HMMlokales Alignment mit HMM:

Zusammenfassung

Markov Ketten: Modelle für Sequenzgenerierung

HMM: verschiedene WK für dieselben Symbole abhängig vom Kontext

Viterbi Algorithmus: Algorithmus zum finden des wahrscheinlichsten Pfades durch die Zustände

Alignment mit HMM: Überführung von score-Gleichungen in die Wahrscheinlichkeitsmodelle

Ende

Fragen???