Zobrazenie zdroja stránky CI08

==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 <math>P(A|A,t) = (1+3e^{-\frac{4}{3} t})/4 </math>, <math>P(C|A,t)=(1-e^{-\frac{4}{3} t})/4</math>
** 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 <math>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)</math>

* Chceme pravdepodobnost <math>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)</math>

* 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 <math>A[v,a] = \sum_{b,c} A[y,b]A[z,c]P(b|a,t_y)P(c|a,t_z)</math>
* Celkova pravdepodobnost je <math>P(X_1=x_1, X_2=x_2,\dots X_n=x_n|T,R)=\sum_a A[r,a] q_a</math> pre koren r.

'''Zlozitost, zlepsenie'''
* Zlozitost <math>O(n|\Sigma|^3)</math>
* Pre nebinarne stromy exponencialne
* Zlepsenie <math>A[v,a] = (\sum_{b} A[y,b]P(b|a,t_y))(\sum_c A[z,c](c|a,t_z))</math>
* Zlozitost <math>O(n|\Sigma|^2)</math> 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 <math>B[v,a]=\sum_{b,c} B[u,b]A[x,c]P(a|b,t_v)P(c|b,t_v)</math>
* Ziadana pravdepodobnost je <math>B[v,a]A[v,a]/P(X_1=x_1, X_2=x_2,\dots X_n=x_n|T,R)</math>