1-BIN-301, 2-AIN-501 Methods in Bioinformatics, 2023/24

Introduction · Rules · Tasks and dates · Materials · Moodle
Quizzes can be found in Moodle.
Homework assignments and journal club papers can be found in Tasks and dates.
Exam rules, example questions and syllabus
Groups for journal club have each their own group in Moodle.


CI06

Z MBI
Revízia z 08: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