1-BIN-301, 2-AIN-501 Methods in Bioinformatics, 2021/22

Introduction · Rules · Tasks and dates · Materials · Moodle · Discussion


CI06

Z MBI
Revízia z 09:31, 28. október 2020; Brona (Diskusia | príspevky)

(rozdiel) ← Staršia verzia | Aktuálna úprava (rozdiel) | Novšia verzia → (rozdiel)
Prejsť na: navigácia, hľadanie

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