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.


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)