1-BIN-301, 2-AIN-501 Metódy v bioinformatike, ZS 2018/19

Úvod · Pravidlá · Termíny a zadania · Prednášky a poznámky · Facebook (oznamy a diskusie) (návod a pravidlá)
Zadania domácich úloh a články na journal club nájdete v časti Termíny a zadania.
Pozrite si ukážkové príklady na skúšku.
Rozpis skupín pre journal club je zverejnený.


CI06

Z MBI
Prejsť na: navigácia, hľadanie

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

  • Problém s modelovaním rozdelenia dĺžok - v základnom modeli je geometrické
  • Zovseobecnene HMM v jednom stave vygenerujú viac znakov
  • Viterbi alg. a spol budú pomalšie (kvadratické od dĺžky sekvencie)

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