CI06

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:

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

for u=1 to m=počet stavov

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

1. 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