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


CI08

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

Felsensteinov algoritmus 1981

  • Mame dany strom T s dlzkami hran a bazy v listoch (jeden stlpec zarovnania) a model substitucii (zadany napr. maticou rychlosti R). Spocitajme pravdepodobnost, ze z modelu dostaneme prave tuto kombinaciu baz v listoch.
  • Oznacenie:
    • Nech X_v je premenna reprezentujuca bazu vo vrchole v a nech x_v je konkretna baza v liste v.
    • Nech listy su 1..n a vnut. vrcholy n+1..2n-1, pricom koren je 2n-1.
    • Nech p_v je rodic vrchola v a nech dlzka hrany z v do rodica je t_v.
    • Nech P(a|b,t) je pravdepodobnost, ze b sa zmeni na a za cas t (spocitame z matice R, vid minule cvicenia).
      • Napr. v Jukes-Cantorovom modeli P(A|A,t)=(1+3e^{{-{\frac  {4}{3}}t}})/4, P(C|A,t)=(1-e^{{-{\frac  {4}{3}}t}})/4
    • Nech q_a je pravdepodobnost bazy a v koreni (ekvilibrium matice R)
      • Napr. v Jukes-Cantorovom modeli q_a = 1/4
  • Ak by sme poznali bazy vo vsetkych vrcholoch, mame P(X_{1}=x_{1}\dots X_{{2n-1}}=x_{{2n-1}}|T,R)=q_{{x_{{2n-1}}}}\prod _{{v=1}}^{{2n-2}}P(x_{v}|x_{{p_{v}}},t_{v})
  • Chceme pravdepodobnost P(X_{1}=x_{1},X_{2}=x_{2},\dots X_{n}=x_{n}|T,R)=\sum _{{x_{{n+1}}\dots x_{{2n-1}}\in \{A,C,G,T\}^{{n-1}}}}P(X_{1}=x_{1}\dots X_{{2n-1}}=x_{{2n-1}}|T,R)
  • Pocitat sucet cez exponencialne vela dosadeni hodnot za vnutorne vrcholy je neefektivne, spocitame rychlejsie dynamickym programovanim.
  • Nech A[v,a] je pravdepodobnost dat v podstrome s vrcholom v ak X_v=a
  • A[v,a] pocitame od listov ku korenu
  • V liste A[v,a] = [a=x_v]
  • Vo vnut. vrchole s detmi y a z mame A[v,a]=\sum _{{b,c}}A[y,b]A[z,c]P(b|a,t_{y})P(c|a,t_{z})
  • Celkova pravdepodobnost je P(X_{1}=x_{1},X_{2}=x_{2},\dots X_{n}=x_{n}|T,R)=\sum _{a}A[r,a]q_{a} pre koren r.

Zlozitost, zlepsenie

  • Zlozitost O(n|\Sigma |^{3})
  • Pre nebinarne stromy exponencialne
  • Zlepsenie A[v,a]=(\sum _{{b}}A[y,b]P(b|a,t_{y}))(\sum _{c}A[z,c](c|a,t_{z}))
  • Zlozitost O(n|\Sigma |^{2}) aj pre nebinarne stromy

Chybajuce data

  • Ak v niektorom liste mame neznamu bazu N, nastavime A[v,a]=1
  • Podobne sa spracovavaju medzery v zarovnani, aj ked mohli by sme mat aj model explicitne ich modelujuci

Aposteriorna pravdepodobnost (nerobili sme)

  • Co ak chceme spocitat pravdepodobnost P(X_v=a|X_1=x_1, X_2=x_2,\dots X_n=x_n,T,R)? Zaujimaju nas teda sekvencie genomov predkov.
  • Potrebujeme B[v,a]=pravdpodobnost dat ak podstrom v nahradim listom s bazou a.
  • B[v,a] pocitame od korena k listom
  • V koreni B[v,a] = q_a
  • Vo vrchole v s rodicom u a surodencom x mame B[v,a]=\sum _{{b,c}}B[u,b]A[x,c]P(a|b,t_{v})P(c|b,t_{v})
  • Ziadana pravdepodobnost je B[v,a]A[v,a]/P(X_{1}=x_{1},X_{2}=x_{2},\dots X_{n}=x_{n}|T,R)