CI06: Rozdiel medzi revíziami

Aktuálna revízia z 08:31, 28. október 2020

Obsah

1 HMM opakovanie
2 Inferencia pomocou najpravdepodobnejšej cesty, Viterbiho algoritmus
3 Inferencia - dopredný algoritmus
4 Inferencia - posterior decoding
5 Trénovanie HMM
6 Tvorba stavového priestoru modelu
7 Zovšeobecnené HMM
8 Párové HMM (pair HMM)

HMM opakovanie

Parametre HMM:

$a_{{u,v}}$ : prechodová pravdepodobnosť zo stavu $u$ do stavu $v$
$e_{{u,x}}$ : pravdepodobnosť emisie $x$ v stave $u$
$\pi _{{u}}$ : pravdepodobnosť, že začneme v stave $u$

Sekvencia $S=S_{1}S_{2}\dots S_{n}$
Anotácia $A=A_{1}A_{2}\dots A_{n}$

$Pr(S,A)=\pi _{{A_{1}}}e_{{A_{1},S_{1}}}\prod _{{i=2}}^{n}a_{{A_{{i-1,A_{i}}}}}e_{{A_{i},S_{i}}}$

Trénovanie

Proces, pri ktorom sa snažíme čo najlepšie odhadnúť pravdepodobnosti $a_{{u,v}}$ a $e_{{u,x}}$ v modeli podľa trénovacích dát

Usudzovanie (inferencia)

Proces, pri ktorom sa snažíme pre sekvenciu $S$ nájsť anotáciu $A$ , ktorá sekvenciu $S$ emituje s veľkou pravdepodobnosťou.

Inferencia pomocou najpravdepodobnejšej cesty, Viterbiho algoritmus

Hľadáme najpravdepodobnejšiu postupnosť stavov $A$ , teda $\arg \max _{A}\Pr(A,S)$ . Úlohu budeme riešiť dynamickým programovaním.

Podproblém $V[i,u]$ : Pravdepodobnosť najpravdepodobnejšej cesty končiacej po $i$ krokoch v stave $u$ , pričom vygeneruje $S_{1}S_{2}\dots S_{i}$ .

Rekurencia:
- $V[1,u]=\pi _{u}e_{{u,S_{1}}}$ (*)
- $V[i,u]=\max _{w}V[i-1,w]a_{{w,u}}e_{{u,S_{i}}}$ (**)

Algoritmus:

Nainicializuj $V[1,*]$ podľa (*)
for i=2 to n=dĺžka reťazca

for u=1 to m=počet stavov

vypočítaj $V[i,u]$ pomocou (**)

Maximálne $V[n,j]$ je pravdepodobnosť najpravdepodobnejšej cesty

Aby sme vypísali anotáciu, pamätáme si pre každé $V[i,u]$ stav $w$ , ktorý viedol k maximálnej hodnote vo vzorci (**).

Zložitosť: $O(nm^{2})$

Poznámka: pre dlhé sekvencie budú čísla $V[i,u]$ veľmi malé a môže dôjsť k podtečeniu. V praxi teda používame zlogaritmované hodnoty, namiesto násobenia súčet.

Inferencia - dopredný algoritmus

Aká je celková pravdepodobnosť, že vygenerujeme sekvenciu $S$ , t.j. $\sum _{A}Pr(A,S).$ Podobný algoritmus ako Viterbiho.

Podproblém $F[i,u]$ : pravdepodobnosť, že po $i$ krokoch vygenerujeme $S_{1},S_{2},\dots S_{i}$ a dostaneme sa do stavu $u$ .

$F[i,u]=\Pr(A_{i}=u\wedge S_{1},S_{2},\dots ,S_{i})=\sum _{{A_{1},A_{2},\dots ,A_{i}=u}}\Pr(A_{1},A_{2},...,A_{i}\wedge S_{1},S_{2},...,S_{i})$

$F[1,u]=\pi _{u}e_{{u,S_{1}}}$

$F[i,u]=\sum _{v}F[i-1,v]a_{{v,u}}e_{{u,S_{i}}}$

Celková pravdepodobnosť $\sum _{u}F[n,u]$

Inferencia - posterior decoding

Aposteriórna pravdepodobnosť stavu u na pozícii i: $Pr(A_{i}=u|S_{1}\dots S_{n})$

Pre každý index i chceme nájsť stav u s najväčšiou aposteriórnou pravdepodobnosťou, dostaneme tak inú možnú anotáciu.

Spustíme dopredný algoritmus a jeho symetrickú verziu, spätný algoritmus, ktorý počíta hodnoty $B[i,u]=\Pr(A_{i}=u\wedge S_{{i+1}}\dots S_{n})$

Aposteriórna pravdepodobnosť stavu u na pozícii i: $Pr(A_{i}=u|S_{1}\dots S_{n})=F[i,u]B[i,u]/\sum _{u}F[n,u].$

Posterior decoding uvažuje všetky anotácie, nielen jednu s najvyššou pravdepodobnosťou. Môže však vypísať anotáciu, ktorá má sama o sebe nulovú pravdepodobnosť (napr. počet kódujúcich báz v géne nie je deliteľný 3).

Trénovanie HMM

Stavový priestor + povolené prechody väčšinou ručne
Parametre (pravdepodobnosti prechodu, emisie a počiatočné) automaticky z trénovacích sekvencií
- Ak máme anotované trénovacie sekvencie, jednoducho počítame frekvencie
- Ak máme iba neanotované sekvencie, snažíme sa maximalizovať vierohodnosť trénovacích dát v modeli. Používajú sa heuristické iteratívne algoritmy, napr. Baum-Welchov, ktorý je verziou všeobecnejšieho algoritmu EM (expectation maximization).
Čím zložitejší model a viac parametrov máme, tým potrebujeme viac trénovacích dát, aby nedošlo k preučeniu, t.j. k situácii, keď model dobre zodpovedá nejakým zvláštnostiam trénovacích dát, nie však ďalším dátam.
Presnosť modelu testujeme na zvláštnych testovacích dátach, ktoré sme nepoužili na trénovanie.

Tvorba stavového priestoru modelu

Promótor + niekoľko prokaryotických génov
Repeaty v intrónoch: multiple path problem
Intrón má dĺžku aspoň 10

Zovšeobecnené HMM

Predstavme si HMM s dvoma stavmi, napr. gén / negén, pričom každý stav má prechod do seba aj do druhého stavu
Úloha: Nech p je pravdepodobnosť, že zostaneme v tom istom stave, (1-p), že prejdeme do druhého stavu. Aká je pravdepodobnosť, že v stave zostaneme presne k krokov (k>=1)?
- Riešenie: $p^{k}(1-p)$
- Toto rozdelenie sa nazýva geometrické a pravdepodbnosť exponenciálne rýchlo klesá s rastúcim k
Keď sa pozrieme na histogram reálny dĺžkov génov / exónov a iných oblastí, väčšinou sa enpodobá na geometrické rozdelnie, môže priponínať napr. normálne rozdelenie s určitou priemenrou dĺžkou a rozptylom okolo
- Jednoduché HMM teda dobre nemodeluje tento fenomén
Zovšeobecnené HMM (semi-Markov) pracuje tak, že v stave má ľubovoľné rozdelenie pravdepodobnosti dĺžok. Model vôjde do stavu, vygeneruje dĺžku k z tohto rozdelenia, potom vygeneruje k znakov z príslušnej emisnej tabuľky a na záver sa rozhodne, ktorým prechodom opustí stav
Úloha: ako spočítame pravdepodobnosť konkrétnej sekvencie a konkrétnej postupnosti stavov aj s dĺžkami? (zaveďme si aj nejaké vhodné označenie)
Úloha: ako treba upraviť Viterbiho algoritmus pre tento model? Aká bude jeho zložitosť?
- Zložitosť bude kvadraticky rásť od dĺžky sekvencie, predtým rástla lineárne
Predstavme si teraz, že rozdelenie dĺžok má hornú hranicu D takú, že všetky dĺžky väčšie ako D majú nulovú pravdepodobnosť.
- Úloha: ako sa toto obmedzenie prejaví v zložitosti Viterbiho algoritmu?
- Uloha: navrhnite, ako modelovať zovšeobecnený HMM s rozdelením dĺžok ohraničeným D pomocou normálneho stavu, kde sa jedne zovšeobecnený stav nahradí vhodnou postupnosťou D obyčajných stavov.

Párové HMM (pair HMM)

Nebrali sme, uvedene pre zaujimavost

Emituje dve sekvencie
V jednom kroku moze emitovat:
- pismenka v oboch sekvenciach naraz
- pismenko v jednej skevencii
- pismenko v druhej sekvencii

Priklad: HMM s jednym stavom v, takym, ze

$e_{{v,x,x}}=p_{1}$
$e_{{v,x,y}}=p_{2}(x\neq y)$ ,
$e_{{v,x,-}}=p_{3}$ ,
$e_{{v,-,x}}=p_{3}$
tak, aby sucet emisnych pravdepodobnosti bol 1
Co reprezentuje najpravdepodobnejsia cesta v tomto HMM?

Zlozitejsi HMM: tri stavy M, X, Y, uplne navzajom poprepajane

$e_{{M,x,x}}=p_{1}$
$e_{{M,x,y}}=p_{2}(x\neq y)$ ,
$e_{{X,x,-}}=1/4$ ,
$e_{{Y,-,y}}=1/4$ ,
Co reprezentuje najpravdepodobnejsia cesta v tomto HMM?

Viterbiho algoritmus pre parove HMM

V[i,j,u] = pravdepodobnost najpravdepodobnejsej postupnosti stavov, ktora vygeneruje x1..xi a y1..yj a skonci v stave u
$V[i,j,u]=\max _{w}\left\{{\begin{array}{l}V[i-1,j-1,w]\cdot a_{{w,u}}\cdot e_{{u,x_{i},y_{j}}}\\V[i-1,j,w]\cdot a_{{w,u}}\cdot e_{{u,x_{i},-}}\\V[i,j-1,w]\cdot a_{{w,u}}\cdot e_{{u,-,y_{j}}}\\\end{array}}\right.$
Casova zlozitost O(mnk^2) kde m a n su dlzky vstupnych sekvencii, k je pocet stavov

Ako by sme spravili parove HMM na hladanie genov v dvoch sekvenciach naraz?

Predpokladajme rovnaky pocet exonov
V exonoch medzery len cele kodony (oboje zjednodusuje)
Inde hocijake medzery

@@ Riadok 1: / Riadok 1: @@
-=CI06=
 ==HMM opakovanie==
 Parametre HMM:

CI06: Rozdiel medzi revíziami

Aktuálna revízia z 08:31, 28. október 2020

Obsah

HMM opakovanie

Inferencia pomocou najpravdepodobnejšej cesty, Viterbiho algoritmus

Inferencia - dopredný algoritmus

Inferencia - posterior decoding

Trénovanie HMM

Tvorba stavového priestoru modelu

Zovšeobecnené HMM

Párové HMM (pair HMM)

Navigačné menu

Osobné nástroje

Menné priestory

Varianty

Zobrazení

Operácie

Hľadať

Navigácia

Nástroje