Hidden-Markov-ModellezurBestimmung ... · Hidden-Markov-ModellezurBestimmung wahrscheinlichsterEreignisse Hans-JoachimBöckenhauer DennisKomm Volkshochschule Zürich 07.Mai2014 Algorithmen

Hidden-Markov-Modelle zur Bestimmungwahrscheinlichster Ereignisse

Hans-Joachim BöckenhauerDennis Komm

Volkshochschule Zürich

07. Mai 2014

Algorithmen in der Biologie Hidden-Markov-Modelle

Eine Fragestellung aus der Biologie


Beobachtung einer Bakterienkultur

Wie verändert sich eine Bakterienkultur über die Zeit?

Konkreter Versuchsaufbau:Nährlösung unter sich verändernden Einflüssen(Temperaturanstieg, Hinzugabe von Chemikalien, . . . )Wir wollen untersuchen:Wann sind Bakterien krank, wann gesund?Wenn gesund, wird Protein von Bakterium produziertVeränderte Bakterien-DNA (Fluoreszenz-Marker)Beobachte Fluoreszenz-Level über die Zeit



Wir machen folgende Beobachtungen:

Zeit in Minuten

Beo

bach

tung

© 2000 Macmillan Magazines Ltd

!"##"$% #& '(#)$"

**, !"#$%& ' ()* +,- ' ., /"!$"%0 .,,, ' 111234567829:;

-, "E2 "5 ?84>5 H,, <3B<D<B64? 98?? ?<384K8> <3 849\ :M 5\788 ;<97:F9:?:3<8> 1878 5749Z8B;4364??JL 43B 5\8<7 k6:78>98398 <3583><5J 14>`6435<C8B2#\8 5<;89:67>8 :M 5\8 k6:78>98398 :M :38 >69\ 98?? <> >\:13 <3

O<K2 .2 #8;@:74? :>9<??45<:3> S<3 5\<> 94>8 >6@87<;@:>8B :3 43:D874?? <39784>8 <3 k6:78>98398T :9967 1<5\ 4 @87<:B :M 47:63BHP, ;<3658>L 7:6K\?J 5\788M:?B ?:3K87 5\43 5\8 5J@<94? 98??FB<D<><:35<;82 #\8 4;@?<56B8 :M :>9<??45<:3> <> ?47K8 9:;@478B 1<5\ =4>8?<38?8D8?> :M dOG k6:78>983982 "5 ?84>5 +,I :M 98??> 1878 M:63B 5:8A\<=<5 :>9<??45:7J =8\4D<:67 <3 849\ :M 5\8 5\788 ;:D<8>L 4>B8587;<38B =J 4 O:67<87 434?J><> 97<587<:3 S>88 Y85\:B>T2 #\8743K8 :M @87<:B>L 4> 8>5<;458B =J 5\8 B<>57<=65<:3 :M @84ZF5:F@84Z<3587D4?>L <> HW," +,;<3 S;843" >!B!L = ! W-T2 "M587 >8@545<:3LdOG ?8D8?> <3 5\8 51: ><=?<3K 98??> :M583 78;4<38B 9:778?458B 1<5\:38 43:5\87 M:7 ?:3K @87<:B> :M 5<;8 SO<K2 -4]9T2 Q4>8B :3 5\8434?J><> :M HRX >8@545<:3 8D835> <3 5\8 - ;:D<8>L 18 ;84>678B 434D874K8 \4?MF5<;8 M:7 ><=?<3K B89:778?45<:3 :M XP" H,;<3L 1\<9\ <>?:3K87 5\43 5\8 5J@<94? 98??FB<D<><:3 5<;8> :M P,]R,;<3 63B87 5\8>89:3B<5<:3>2 #\<> <3B<9458> 5\45 5\8 >5458 :M 5\8 3851:7Z <> 5743>F;<558B 5: 5\8 @7:K83J 98??>L B8>@<58 4 >57:3K 3:<>8 9:;@:38352 [8:=>87D8B ><K3<C9435 D47<45<:3> <3 5\8 @87<:B 43B 4;@?<56B8 :M 5\8:>9<??45:7 :65@65 =:5\ M7:; 98?? 5: 98?? SO<K2 -BTL 43B :D87 5<;8 <3 4><3K?8 98?? 43B <5> B8>983B435> SO<K2 -4]9T2 N3 >:;8 <3B<D<B64?>L@87<:B> 1878 :;<558B :7 @\4>8 B8?4J8B <3 :38 98?? 78?45<D8 5: <5>><=?<3K SO<K2 -4L 9T2%89835 5\8:785<94? 1:7Z \4> >\:13 5\45 >5:9\4>5<9 8MM895> ;4J

=8 78>@:3><=?8 M:7 3:<>J :@8745<:3 <3 345674? K838F8A@78>><:33851:7Z>H.2 U<;6?45<:3> :M 5\8 78@78>><?45:7 5\45 54Z8 <35: 499:6355\8 >5:9\4>5<9 345678 :M 78495<:3 8D835> 43B B<>9785838>> :M 3851:7Z9:;@:3835> 4?>: 8A\<=<5 ><K3<C9435 D47<4=<?<5JL 78B69<3K 5\8 9:778F?45<:3 5<;8 M:7 :>9<??45<:3> M7:; <3C3<5J S<3 5\8 9:35<36:6> ;:B8?T5: 4=:65 51: @87<:B> SQ:A HL O<K2 H9L <3>85>T2 N3 K83874?L 18 1:6?B?<Z8 5: B<>5<3K6<>\ >69\ >5:9\4>5<9 8MM895> M7:; @:>><=?8 <357<3><94??J9:;@?8A BJ34;<9> S>69\ 4> <3587;<558398 :7 9\4:5<9 =8\4D<:67T2O675\87 >56B<8> 478 388B8B 5: <B835<MJ 43B 9\4749587<f8 5\8 >:6798>:M k695645<:3> <3 5\8 78@78>><?45:7 43B :5\87 B8><K38B 3851:7Z>2 N3@475<96?47L ?:3K87 8A@87<;835> @87M:7;8B 63B87 9\8;:>545<9 9:3FB<5<:3> >\:6?B 834=?8 ;:78 9:;@?858 >545<>5<94? 9\4749587<f45<:3 :M

TetR

LacIλ cI

Repressilator Reporter

TetR

G FP

a

PLlac01

PLtet01

PLtet01

pS C101origin

ColE1

tetR-lite

gfp-aav

lacI-lite

λ cI-lite

ampR

kanR

λPR

2*+3%" 4 !"#$%&'(%)"#* +,$)-# .#+ $)/'0.%)"# "1 %2, &,3&,$$)0.%"&4 5* 52, &,3&,$$)0.%"&#,%6"&74 52, &,3&,$$)0.%"& )$ . (8(0)( #,-.%)9,:1,,+;.(7 0""3 ("/3"$,+ "1 %2&,, &,3&,$$"&

-,#,$ .#+ %2,)& ("&&,$3"#+)#- 3&"/"%,&$* .$ $2"6# $(2,/.%)(.008 )# %2, (,#%&, "1 %2,

0,1%:2.#+ 30.$/)+4 <% '$,$ =>0.(?@ .#+ =>%,%?@* 62)(2 .&, $%&"#-* %)-2%08 &,3&,$$);0,

3&"/"%,&$ ("#%.)#)#- !"# .#+ $%$ "3,&.%"&$* &,$3,(%)9,08A* .$ 6,00 .$ =B* %2, &)-2% 3&"/"%,&

1&"/ 32.-, ! C$,, D,%2"+$E4 52, $%.;)0)%8 "1 %2, %2&,, &,3&,$$"&$ )$ &,+'(,+ ;8 %2,

3&,$,#(, "1 +,$%&'(%)"# %.-$ C+,#"%,+ F!&$%GE4 52, ("/3.%);0, &,3"&%,& 30.$/)+ C&)-2%E

,H3&,$$,$ .# )#%,&/,+).%,:$%.;)0)%8 IJ= 9.&).#%@@ C'()*""+E4 <# ;"%2 30.$/)+$* %&.#$(&)3:

%)"#.0 '#)%$ .&, )$"0.%,+ 1&"/ #,)-2;"'&)#- &,-)"#$ ;8 5@ %,&/)#.%"&$ 1&"/ %2, ,- #.!& //01

"3,&"# C;0.(7 ;"H,$E4 '* K%.;)0)%8 +).-&./ 1"& . ("#%)#'"'$ $8//,%&)( &,3&,$$)0.%"& /"+,0

CL"H @E4 52, 3.&./,%,& $3.(, )$ +)9)+,+ )#%" %6" &,-)"#$ )# 62)(2 %2, $%,.+8 $%.%, )$ $%.;0,

C%"3 0,1%E "& '#$%.;0, C;"%%"/ &)-2%E4 !'&9,$ M* L .#+ ! /.&7 %2, ;"'#+.&),$ ;,%6,,# %2,

%6" &,-)"#$ 1"& +)11,&,#% 3.&./,%,& 9.0',$N M* 0 ! O!@* #P ! PQ L* 0 ! O* #P ! PQ !*

0 ! O* #P"# ! @P$ R4 52, '#$%.;0, &,-)"# CME* 62)(2 )#(0'+,$ '#$%.;0, &,-)"#$ CLE .#+

C!E* )$ $2.+,+4 -* ?$()00.%)"#$ )# %2, 0,9,0$ "1 %2, %2&,, &,3&,$$"& 3&"%,)#$* .$ ";%.)#,+ ;8#'/,&)(.0 )#%,-&.%)"#4 >,1%* . $,% "1 %83)(.0 3.&./,%,& 9.0',$* /.&7,+ ;8 %2, FSG )# '* 6,&,'$,+ %" $"09, %2, ("#%)#'"'$ /"+,04 B)-2%* . $)/)0.& $,% "1 3.&./,%,&$ 6.$ '$,+ %" $"09, .

$%"(2.$%)( 9,&$)"# "1 %2, /"+,0 CL"H @E4 !"0"'& ("+)#- )$ .$ )# 54 <#$,%$ $2"6 %2,

#"&/.0)T,+ .'%"("&&,0.%)"# 1'#(%)"# "1 %2, U&$% &,3&,$$"& $3,(),$4

steady stateunstable

Maximum proteins per cell, α (× KM)

Prot

ein

lifet

ime/

mR

NA

lifet

ime,

β A

B

C

b

steady statestable

0 500 10000

4,000

6,000

Time (min)

Prot

eins

per

cel

l

0 500 1,000-1

0

1

0 500 1,0000

2,000 2,000

4,000

6,000

Time (min)

0 500 1,000-1

0

1

c

0 100 200 300 400 500 6000

20

40

60

80

100

120

60 140 250 300 390 450 550 600

Fluo

resc

ence

(arb

itrar

y un

its)

Time (min)

Time (min)

a

b

c

2*+3%" 6 B,3&,$$)0.%)"# )# 0)9)#- ;.(%,&).4 5* '* 52, -&"6%2 .#+ %)/,("'&$, "1 IJ=,H3&,$$)"# 1"& . $)#-0, (,00 "1 ,- #.!& 2"$% $%&.)# D!V@PP ("#%.)#)#- %2, &,3&,$$)0.%"&

30.$/)+$ CJ)-4 @.E4 K#.3$2"%$ "1 . -&"6)#- /)(&"("0"#8 6,&, %.7,# 3,&)"+)(.008 ;"%2 )#

W'"&,$(,#(, C5E .#+ ;&)-2%:U,0+ C'E4 -* 52, 3)(%'&,$ )# 5 .#+ ' ("&&,$3"#+ %" 3,.7$ .#+%&"'-2$ )# %2, %)/,("'&$, "1 IJ= W'"&,$(,#(, +,#$)%8 "1 %2, $,0,(%,+ (,004 K(.0, ;.&*

V%/4 L.&$ .% %2, ;"%%"/ "1 - )#+)(.%, %2, %)/)#- "1 $,3%.%)"# ,9,#%$* .$ ,$%)/.%,+ 1&"/;&)-2%:U,0+ )/.-,$4

Elowitz, Leibler, 2000, Nature 403

Für das Fluoreszenz-Level beobachten wirNiedrig, Mittel, Mittel, Hoch, Mittel, Hoch, Mittel, Hoch

Was folgt nun für den Gesundheitszustand des Bakteriums?


Hidden-Markov-Modelle


„Das unfaire Kasino“

Ein fairer Würfel (Alle Resultate mit Wahrscheinlichkeit 16)

Ein unfairer Würfel (Resultat „6“ mit Wahrscheinlichkeit 12)

Zu Beginn wird ein Würfel gewählt (Wahrscheinlichkeit 12)

Nach Wurf kann gewechselt werden (Wahrscheinlichkeit 120)

Markov-ModellZustand: Benutzter WürfelÜbergangs-Wahrscheinlichkeit: Wahrscheinlichkeit, denWürfel zu wechselnEmissions-Wahrscheinlichkeit: Wahrscheinlichkeit, einekonkrete Augenzahl zu beobachten; abhängig vom Zustand


Wahrscheinlichkeit einer konkreten Ausgabe

Nehmen wir an, wir beobachten die Zahlen 6, 6, 6, 6Ausserdem vermuten wir, dass zunächst zweimal der unfaireWürfel verwendet wurde, dann zweimal der faireDies entspricht einem festen Pfad durch unser Markov-Modell

Wie gross ist die Wahrscheinlichkeit?



Betrachten wir nur das Werfen der ersten 61 Ereignis A = „Der unfaire Würfel wird zu Beginn gewählt“2 Ereignis B = „Es wird 6 gewürfelt“

Jetzt können wir einfach die Wahrscheinlichkeiten ausrechnen

Wahr (Der unfaire Würfel wird zu Beginn gewählt und 6 gewürfelt)= Wahr (A und B)

= Wahr (A) ·Wahr (B unter der Voraussetzung A)= Wahr (A) ·Wahr (B |A)

=12· 12



Nun führen wir diese Anwendung für 6, 6, 6, 6 fort

12· 12· 1920· 12· 120· 16· 1920· 16

Wahrscheinlichkeit, dass schliesslich wieder eine 6 geworfen wird



Hidden-Markov-ModellAber was passiert, wenn wir nur die Ausgaben beobachten?

Nehmen wir an, wir beobachten die Zahlen 6, 5, 2, 6, 6Was ist der wahrscheinlichste Pfad?Für drei Zahlen ist der unfaire Würfel „besser“Für zwei Zahlen der faireEs ist nicht klar, ob es sich „lohnt,“ den Würfel zu wechseln



Anzahl möglicher Pfade für n Würfe ist 2n

Für 300 Würfe ist dies mehr als

1090

Aber müssen wir wirklich alle ausprobieren?NeinDynamische Programmierung


Dynamische Programmierung

Prinzip der dynamischen ProgrammierungLösung für die gesamte Eingabe zusammensetzen aus Teillösungenfür Teilprobleme, beginnend mit den kleinsten Teilproblemen

Problem: Finde geeignete Teilprobleme

Idee (Viterbi, 1967):Alle wahrscheinlichsten Pfade für Anfangsstücke (Präfixe) dergegebenen Folge von Würfen, die in gegebenem Zustandenden, als TeilproblemeBerechne wahrscheinlichste Pfade für längere Präfixe aus denwahrscheinlichsten Pfaden für kürzere Präfixe



„fair“

„unfair“

X1 X2 X3 X4 X5 X6 X7

Nehmen wir an, die schraffierten Felder sind bereits ausgefülltWahrscheinlichste Pfade der Länge 3 sind bekannt(z.B. Pfad, der in X3 endet: unfair, fair, fair)Berechne jetzt solchen Pfad der Länge 4, der in „fair“ endetVerlängere bekannte Pfade und nimm wahrscheinlicheren



Beobachtete Würfelfolge 6, 5, 2, 6, 6Erstelle Tabelle (ähnlich wie bei Alignment)Merke, welcher Pfad bislang der beste war

„fair“

„unfair“

6 5 2 6 6

12 ·

16

112

12 ·

12

14

Wahrscheinlichkeit, dass 5ausgegeben wird und der

Zustand „fair“ ist

Wahrscheinlichkeit deswahrscheinlichsten Pfades

der Länge 2 zu „fair“×

Wahrscheinlichkeit, dass 5in „fair“ ausgegeben wird

16

max{ 1

12 ·1920,

14 ·

120

}19240191440

191440

19800

361172800

36116000

685920736000

6859640000

685976800000

13032125600000

Der wahrscheinlichste Pfad ist also der, bei dem nur der unfaireWürfel verwendet wurde



Beobachtete Würfelfolge 6, 5, 2, 6, 6Erstelle Tabelle (ähnlich wie bei Alignment)Merke, welcher Pfad bislang der beste war

„fair“

„unfair“

6 5 2 6 6

12 ·

16

112

12 ·

12

14

Wahrscheinlichkeit, dass 5ausgegeben wird und der

Zustand „fair“ ist

Wahrscheinlichkeit deswahrscheinlichsten Pfades

der Länge 2 zu „fair“×

Wahrscheinlichkeit, dass 5in „fair“ ausgegeben wird

16

max{ 1

12 ·1920,

14 ·

120

}19240191440

191440

19800

361172800

36116000

685920736000

6859640000

685976800000

13032125600000

Der wahrscheinlichste Pfad ist also der, bei dem nur der unfaireWürfel verwendet wurde


Zurück zur Fragestellung aus der Biologie




Zeit in Minuten

Beo

bach

tung


!"##"$% #& '(#)$"

**, !"#$%& ' ()* +,- ' ., /"!$"%0 .,,, ' 111234567829:;




TetR

LacIλ cI


TetR

G FP

a

PLlac01

PLtet01

PLtet01

pS C101origin

ColE1

tetR-lite

gfp-aav

lacI-lite

λ cI-lite

ampR

kanR

λPR

2*+3%" 4 !"#$%&'(%)"#* +,$)-# .#+ $)/'0.%)"# "1 %2, &,3&,$$)0.%"&4 5* 52, &,3&,$$)0.%"&#,%6"&74 52, &,3&,$$)0.%"& )$ . (8(0)( #,-.%)9,:1,,+;.(7 0""3 ("/3"$,+ "1 %2&,, &,3&,$$"&

-,#,$ .#+ %2,)& ("&&,$3"#+)#- 3&"/"%,&$* .$ $2"6# $(2,/.%)(.008 )# %2, (,#%&, "1 %2,

0,1%:2.#+ 30.$/)+4 <% '$,$ =>0.(?@ .#+ =>%,%?@* 62)(2 .&, $%&"#-* %)-2%08 &,3&,$$);0,

3&"/"%,&$ ("#%.)#)#- !"# .#+ $%$ "3,&.%"&$* &,$3,(%)9,08A* .$ 6,00 .$ =B* %2, &)-2% 3&"/"%,&

1&"/ 32.-, ! C$,, D,%2"+$E4 52, $%.;)0)%8 "1 %2, %2&,, &,3&,$$"&$ )$ &,+'(,+ ;8 %2,

3&,$,#(, "1 +,$%&'(%)"# %.-$ C+,#"%,+ F!&$%GE4 52, ("/3.%);0, &,3"&%,& 30.$/)+ C&)-2%E

,H3&,$$,$ .# )#%,&/,+).%,:$%.;)0)%8 IJ= 9.&).#%@@ C'()*""+E4 <# ;"%2 30.$/)+$* %&.#$(&)3:

%)"#.0 '#)%$ .&, )$"0.%,+ 1&"/ #,)-2;"'&)#- &,-)"#$ ;8 5@ %,&/)#.%"&$ 1&"/ %2, ,- #.!& //01

"3,&"# C;0.(7 ;"H,$E4 '* K%.;)0)%8 +).-&./ 1"& . ("#%)#'"'$ $8//,%&)( &,3&,$$)0.%"& /"+,0

CL"H @E4 52, 3.&./,%,& $3.(, )$ +)9)+,+ )#%" %6" &,-)"#$ )# 62)(2 %2, $%,.+8 $%.%, )$ $%.;0,

C%"3 0,1%E "& '#$%.;0, C;"%%"/ &)-2%E4 !'&9,$ M* L .#+ ! /.&7 %2, ;"'#+.&),$ ;,%6,,# %2,

%6" &,-)"#$ 1"& +)11,&,#% 3.&./,%,& 9.0',$N M* 0 ! O!@* #P ! PQ L* 0 ! O* #P ! PQ !*

0 ! O* #P"# ! @P$ R4 52, '#$%.;0, &,-)"# CME* 62)(2 )#(0'+,$ '#$%.;0, &,-)"#$ CLE .#+

C!E* )$ $2.+,+4 -* ?$()00.%)"#$ )# %2, 0,9,0$ "1 %2, %2&,, &,3&,$$"& 3&"%,)#$* .$ ";%.)#,+ ;8#'/,&)(.0 )#%,-&.%)"#4 >,1%* . $,% "1 %83)(.0 3.&./,%,& 9.0',$* /.&7,+ ;8 %2, FSG )# '* 6,&,'$,+ %" $"09, %2, ("#%)#'"'$ /"+,04 B)-2%* . $)/)0.& $,% "1 3.&./,%,&$ 6.$ '$,+ %" $"09, .

$%"(2.$%)( 9,&$)"# "1 %2, /"+,0 CL"H @E4 !"0"'& ("+)#- )$ .$ )# 54 <#$,%$ $2"6 %2,

#"&/.0)T,+ .'%"("&&,0.%)"# 1'#(%)"# "1 %2, U&$% &,3&,$$"& $3,(),$4



Prot

ein

lifet

ime/

mR

NA

lifet

ime,

β A

B

C

b

steady statestable

0 500 10000

4,000

6,000

Time (min)

Prot

eins

per

cel

l

0 500 1,000-1

0

1

0 500 1,0000

2,000 2,000

4,000

6,000

Time (min)

0 500 1,000-1

0

1

c

0 100 200 300 400 500 6000

20

40

60

80

100

120

60 140 250 300 390 450 550 600

Fluo

resc

ence

(arb

itrar

y un

its)

Time (min)

Time (min)

a

b

c

2*+3%" 6 B,3&,$$)0.%)"# )# 0)9)#- ;.(%,&).4 5* '* 52, -&"6%2 .#+ %)/,("'&$, "1 IJ=,H3&,$$)"# 1"& . $)#-0, (,00 "1 ,- #.!& 2"$% $%&.)# D!V@PP ("#%.)#)#- %2, &,3&,$$)0.%"&

30.$/)+$ CJ)-4 @.E4 K#.3$2"%$ "1 . -&"6)#- /)(&"("0"#8 6,&, %.7,# 3,&)"+)(.008 ;"%2 )#

W'"&,$(,#(, C5E .#+ ;&)-2%:U,0+ C'E4 -* 52, 3)(%'&,$ )# 5 .#+ ' ("&&,$3"#+ %" 3,.7$ .#+%&"'-2$ )# %2, %)/,("'&$, "1 IJ= W'"&,$(,#(, +,#$)%8 "1 %2, $,0,(%,+ (,004 K(.0, ;.&*

V%/4 L.&$ .% %2, ;"%%"/ "1 - )#+)(.%, %2, %)/)#- "1 $,3%.%)"# ,9,#%$* .$ ,$%)/.%,+ 1&"/;&)-2%:U,0+ )/.-,$4




Bakterie kann sich in einem von drei Zuständen befinden:

1 Gesund2 OK3 Krank

DNA wurde so verändert, das Bakterien fluoreszieren, und zwar jemehr desto gesünder sie sind; Fluoreszenz-Level kann beobachtetwerden:

1 Hoch2 Mittel3 Niedrig




Zeit in Minuten

Beo

bach

tung


!"##"$% #& '(#)$"

**, !"#$%& ' ()* +,- ' ., /"!$"%0 .,,, ' 111234567829:;




TetR

LacIλ cI


TetR

G FP

a

PLlac01

PLtet01

PLtet01

pS C101origin

ColE1

tetR-lite

gfp-aav

lacI-lite

λ cI-lite

ampR

kanR

λPR

2*+3%" 4 !"#$%&'(%)"#* +,$)-# .#+ $)/'0.%)"# "1 %2, &,3&,$$)0.%"&4 5* 52, &,3&,$$)0.%"&#,%6"&74 52, &,3&,$$)0.%"& )$ . (8(0)( #,-.%)9,:1,,+;.(7 0""3 ("/3"$,+ "1 %2&,, &,3&,$$"&

-,#,$ .#+ %2,)& ("&&,$3"#+)#- 3&"/"%,&$* .$ $2"6# $(2,/.%)(.008 )# %2, (,#%&, "1 %2,

0,1%:2.#+ 30.$/)+4 <% '$,$ =>0.(?@ .#+ =>%,%?@* 62)(2 .&, $%&"#-* %)-2%08 &,3&,$$);0,

3&"/"%,&$ ("#%.)#)#- !"# .#+ $%$ "3,&.%"&$* &,$3,(%)9,08A* .$ 6,00 .$ =B* %2, &)-2% 3&"/"%,&

1&"/ 32.-, ! C$,, D,%2"+$E4 52, $%.;)0)%8 "1 %2, %2&,, &,3&,$$"&$ )$ &,+'(,+ ;8 %2,

3&,$,#(, "1 +,$%&'(%)"# %.-$ C+,#"%,+ F!&$%GE4 52, ("/3.%);0, &,3"&%,& 30.$/)+ C&)-2%E

,H3&,$$,$ .# )#%,&/,+).%,:$%.;)0)%8 IJ= 9.&).#%@@ C'()*""+E4 <# ;"%2 30.$/)+$* %&.#$(&)3:

%)"#.0 '#)%$ .&, )$"0.%,+ 1&"/ #,)-2;"'&)#- &,-)"#$ ;8 5@ %,&/)#.%"&$ 1&"/ %2, ,- #.!& //01

"3,&"# C;0.(7 ;"H,$E4 '* K%.;)0)%8 +).-&./ 1"& . ("#%)#'"'$ $8//,%&)( &,3&,$$)0.%"& /"+,0

CL"H @E4 52, 3.&./,%,& $3.(, )$ +)9)+,+ )#%" %6" &,-)"#$ )# 62)(2 %2, $%,.+8 $%.%, )$ $%.;0,

C%"3 0,1%E "& '#$%.;0, C;"%%"/ &)-2%E4 !'&9,$ M* L .#+ ! /.&7 %2, ;"'#+.&),$ ;,%6,,# %2,

%6" &,-)"#$ 1"& +)11,&,#% 3.&./,%,& 9.0',$N M* 0 ! O!@* #P ! PQ L* 0 ! O* #P ! PQ !*

0 ! O* #P"# ! @P$ R4 52, '#$%.;0, &,-)"# CME* 62)(2 )#(0'+,$ '#$%.;0, &,-)"#$ CLE .#+

C!E* )$ $2.+,+4 -* ?$()00.%)"#$ )# %2, 0,9,0$ "1 %2, %2&,, &,3&,$$"& 3&"%,)#$* .$ ";%.)#,+ ;8#'/,&)(.0 )#%,-&.%)"#4 >,1%* . $,% "1 %83)(.0 3.&./,%,& 9.0',$* /.&7,+ ;8 %2, FSG )# '* 6,&,'$,+ %" $"09, %2, ("#%)#'"'$ /"+,04 B)-2%* . $)/)0.& $,% "1 3.&./,%,&$ 6.$ '$,+ %" $"09, .

$%"(2.$%)( 9,&$)"# "1 %2, /"+,0 CL"H @E4 !"0"'& ("+)#- )$ .$ )# 54 <#$,%$ $2"6 %2,

#"&/.0)T,+ .'%"("&&,0.%)"# 1'#(%)"# "1 %2, U&$% &,3&,$$"& $3,(),$4



Prot

ein

lifet

ime/

mR

NA

lifet

ime,

β A

B

C

b

steady statestable

0 500 10000

4,000

6,000

Time (min)

Prot

eins

per

cel

l

0 500 1,000-1

0

1

0 500 1,0000

2,000 2,000

4,000

6,000

Time (min)

0 500 1,000-1

0

1

c

0 100 200 300 400 500 6000

20

40

60

80

100

120

60 140 250 300 390 450 550 600

Fluo

resc

ence

(arb

itrar

y un

its)

Time (min)

Time (min)

a

b

c

2*+3%" 6 B,3&,$$)0.%)"# )# 0)9)#- ;.(%,&).4 5* '* 52, -&"6%2 .#+ %)/,("'&$, "1 IJ=,H3&,$$)"# 1"& . $)#-0, (,00 "1 ,- #.!& 2"$% $%&.)# D!V@PP ("#%.)#)#- %2, &,3&,$$)0.%"&

30.$/)+$ CJ)-4 @.E4 K#.3$2"%$ "1 . -&"6)#- /)(&"("0"#8 6,&, %.7,# 3,&)"+)(.008 ;"%2 )#

W'"&,$(,#(, C5E .#+ ;&)-2%:U,0+ C'E4 -* 52, 3)(%'&,$ )# 5 .#+ ' ("&&,$3"#+ %" 3,.7$ .#+%&"'-2$ )# %2, %)/,("'&$, "1 IJ= W'"&,$(,#(, +,#$)%8 "1 %2, $,0,(%,+ (,004 K(.0, ;.&*

V%/4 L.&$ .% %2, ;"%%"/ "1 - )#+)(.%, %2, %)/)#- "1 $,3%.%)"# ,9,#%$* .$ ,$%)/.%,+ 1&"/;&)-2%:U,0+ )/.-,$4


Für das Fluoreszenz-Level beobachten wirNiedrig, Mittel, Mittel, Hoch, Mittel, Hoch, Mittel, Hoch

Was folgt nun für den Gesundheitszustand des Bakteriums?



Emissions-Wahrscheinlichkeiten(erworben durch empirische Untersuchungen)

1 GesundWahr (Hoch) = 0.5Wahr (Mittel) = 0.3Wahr (Niedrig) = 0.2

2 OKWahr (Hoch) = 0.2Wahr (Mittel) = 0.6Wahr (Niedrig) = 0.2

3 KrankWahr (Hoch) = 0.2Wahr (Mittel) = 0.3Wahr (Niedrig) = 0.5



Übergangs-Wahrscheinlichkeiten(ebenfalls erworben durch empirische Untersuchungen)

GesundWahr (Hoch) = 0.5Wahr (Mittel) = 0.3Wahr (Niedrig) =

0.2

OKWahr (Hoch) = 0.2Wahr (Mittel) = 0.6Wahr (Niedrig) =

0.2

KrankWahr (Hoch) = 0.2Wahr (Mittel) = 0.3Wahr (Niedrig) =

0.5

0.4

0.3

0.3

0.2

0.6

0.2

0.4

0.6



Zeit in Minuten

Beo

bach

tung


!"##"$% #& '(#)$"

**, !"#$%& ' ()* +,- ' ., /"!$"%0 .,,, ' 111234567829:;




TetR

LacIλ cI


TetR

G FP

a

PLlac01

PLtet01

PLtet01

pS C101origin

ColE1

tetR-lite

gfp-aav

lacI-lite

λ cI-lite

ampR

kanR

λPR

2*+3%" 4 !"#$%&'(%)"#* +,$)-# .#+ $)/'0.%)"# "1 %2, &,3&,$$)0.%"&4 5* 52, &,3&,$$)0.%"&#,%6"&74 52, &,3&,$$)0.%"& )$ . (8(0)( #,-.%)9,:1,,+;.(7 0""3 ("/3"$,+ "1 %2&,, &,3&,$$"&

-,#,$ .#+ %2,)& ("&&,$3"#+)#- 3&"/"%,&$* .$ $2"6# $(2,/.%)(.008 )# %2, (,#%&, "1 %2,

0,1%:2.#+ 30.$/)+4 <% '$,$ =>0.(?@ .#+ =>%,%?@* 62)(2 .&, $%&"#-* %)-2%08 &,3&,$$);0,

3&"/"%,&$ ("#%.)#)#- !"# .#+ $%$ "3,&.%"&$* &,$3,(%)9,08A* .$ 6,00 .$ =B* %2, &)-2% 3&"/"%,&

1&"/ 32.-, ! C$,, D,%2"+$E4 52, $%.;)0)%8 "1 %2, %2&,, &,3&,$$"&$ )$ &,+'(,+ ;8 %2,

3&,$,#(, "1 +,$%&'(%)"# %.-$ C+,#"%,+ F!&$%GE4 52, ("/3.%);0, &,3"&%,& 30.$/)+ C&)-2%E

,H3&,$$,$ .# )#%,&/,+).%,:$%.;)0)%8 IJ= 9.&).#%@@ C'()*""+E4 <# ;"%2 30.$/)+$* %&.#$(&)3:

%)"#.0 '#)%$ .&, )$"0.%,+ 1&"/ #,)-2;"'&)#- &,-)"#$ ;8 5@ %,&/)#.%"&$ 1&"/ %2, ,- #.!& //01

"3,&"# C;0.(7 ;"H,$E4 '* K%.;)0)%8 +).-&./ 1"& . ("#%)#'"'$ $8//,%&)( &,3&,$$)0.%"& /"+,0

CL"H @E4 52, 3.&./,%,& $3.(, )$ +)9)+,+ )#%" %6" &,-)"#$ )# 62)(2 %2, $%,.+8 $%.%, )$ $%.;0,

C%"3 0,1%E "& '#$%.;0, C;"%%"/ &)-2%E4 !'&9,$ M* L .#+ ! /.&7 %2, ;"'#+.&),$ ;,%6,,# %2,

%6" &,-)"#$ 1"& +)11,&,#% 3.&./,%,& 9.0',$N M* 0 ! O!@* #P ! PQ L* 0 ! O* #P ! PQ !*

0 ! O* #P"# ! @P$ R4 52, '#$%.;0, &,-)"# CME* 62)(2 )#(0'+,$ '#$%.;0, &,-)"#$ CLE .#+

C!E* )$ $2.+,+4 -* ?$()00.%)"#$ )# %2, 0,9,0$ "1 %2, %2&,, &,3&,$$"& 3&"%,)#$* .$ ";%.)#,+ ;8#'/,&)(.0 )#%,-&.%)"#4 >,1%* . $,% "1 %83)(.0 3.&./,%,& 9.0',$* /.&7,+ ;8 %2, FSG )# '* 6,&,'$,+ %" $"09, %2, ("#%)#'"'$ /"+,04 B)-2%* . $)/)0.& $,% "1 3.&./,%,&$ 6.$ '$,+ %" $"09, .

$%"(2.$%)( 9,&$)"# "1 %2, /"+,0 CL"H @E4 !"0"'& ("+)#- )$ .$ )# 54 <#$,%$ $2"6 %2,

#"&/.0)T,+ .'%"("&&,0.%)"# 1'#(%)"# "1 %2, U&$% &,3&,$$"& $3,(),$4



Prot

ein

lifet

ime/

mR

NA

lifet

ime,

β A

B

C

b

steady statestable

0 500 10000

4,000

6,000

Time (min)

Prot

eins

per

cel

l

0 500 1,000-1

0

1

0 500 1,0000

2,000 2,000

4,000

6,000

Time (min)

0 500 1,000-1

0

1

c

0 100 200 300 400 500 6000

20

40

60

80

100

120

60 140 250 300 390 450 550 600

Fluo

resc

ence

(arb

itrar

y un

its)

Time (min)

Time (min)

a

b

c

2*+3%" 6 B,3&,$$)0.%)"# )# 0)9)#- ;.(%,&).4 5* '* 52, -&"6%2 .#+ %)/,("'&$, "1 IJ=,H3&,$$)"# 1"& . $)#-0, (,00 "1 ,- #.!& 2"$% $%&.)# D!V@PP ("#%.)#)#- %2, &,3&,$$)0.%"&

30.$/)+$ CJ)-4 @.E4 K#.3$2"%$ "1 . -&"6)#- /)(&"("0"#8 6,&, %.7,# 3,&)"+)(.008 ;"%2 )#

W'"&,$(,#(, C5E .#+ ;&)-2%:U,0+ C'E4 -* 52, 3)(%'&,$ )# 5 .#+ ' ("&&,$3"#+ %" 3,.7$ .#+%&"'-2$ )# %2, %)/,("'&$, "1 IJ= W'"&,$(,#(, +,#$)%8 "1 %2, $,0,(%,+ (,004 K(.0, ;.&*

V%/4 L.&$ .% %2, ;"%%"/ "1 - )#+)(.%, %2, %)/)#- "1 $,3%.%)"# ,9,#%$* .$ ,$%)/.%,+ 1&"/;&)-2%:U,0+ )/.-,$4


Wir machen über die Zeit also folgende Beobachtungen:Niedrig, Mittel, Mittel, Hoch, Mittel, Hoch, Mittel, Hoch



Wir können nun folgende Tabelle ausfüllenWerte nach 6 Nachkommastellen abgeschnitten

Gesund

OK

Krank

Niedrig Mittel Mittel Hoch Mittel Hoch Mittel Hoch

0.06

0.06

0.16

0.008

0.04

0.03

0.0024

0.0144

0.0054

0.00144

0.001728

0.000648

0.000172

0.000622

0.000129

0.000062

0.000074

0.000024 0.000007

0.000002

0.000005

0.000002

0.000003

0.000001


Laufzeit-Analyse

Dieser Algorithmus ist als Viterbi-Algorithmus bekannt.Anzahl der Zustände: qLänge der beobachteten Sequenz: nTabelle hat Grösse q × nFür jede Zelle müssen q Werte verglichen werdenWir brauchen ca. q · q · n Vergleiche„Die Laufzeit wächst proportional mit q2 · n“


Laufzeit-Analyse

Hier ist q = 18; sei n = 300: Weniger als 100 000 VergleicheNaiver Ansatz: Mehr als 10143 Vergleiche


Laufzeit-Analyse

0

20000

40000

60000

80000

100000

120000

140000

0 2 4 6 8 10

An

za

hl V

erg

leic

he

Anzahl Zeichen in Sequenz

naivViterbi


CG -Inseln


Kodierende Bereiche der DNA

DNA wird aufgefasst als String über den Buchstaben A, C, G, TTeile sind „kodierende Bereiche,“ andere „steuernde Bereiche“CG -Inseln sind Bereiche im String, in denen die Folge CGhäufig vorkommtSie tauchen in der Nähe von Genen häufig auf, sonst seltenFinde CG -Inseln in gegebenen String

Analogie zum vorher vorgestellten unfairen Kasino:Die jeweiligen Würfel entsprechen den Situationen, ob manin einer CG -Insel istEs gibt aber für beide Situationen 4 verschiedeneBeobachtungen


Zusammenfassung

1 Wahrscheinlichkeitenmodellieren Situationen, wenn nicht alle Grössen bekannt sind

2 Markov-Modelleverknüpfen Zustände miteinander

3 BeispieleBeobachtungen im Labor, CG -Inseln

4 Dynamische Programmierungkann die Berechnungszeit verringern


Documents

Hidden-Markov-ModellezurBestimmung ... · Hidden-Markov-ModellezurBestimmung wahrscheinlichsterEreignisse Hans-JoachimBöckenhauer DennisKomm Volkshochschule Zürich 07.Mai2014 Algorithmen