U VO D DO FYLOGENETICKÉ ANALÝZY I. Úvod zákl. pojmy, počet stromů, typy dat Práce se sekvencemi DNA a proteinů databáze (GenBank, ENTREZ, BLAST), seřazení sekvencí (Clustal) Rozdělení metod a kritéria jejich hodnocení Maximální úspornost (Maximum parsimony, MP) MP a konzistence Evoluční modely a distanční metody výběr modelu, UPGMA, neighbor-joining Uvod Definice základních pojmů a) periferal branch rooted tree dichotomy polytomy fo\ (bifurcation) (multifurcation) terminal M node internal node internal branch c) path root J dráha d) e) unrooted tree central branch fylogenetický strom = fylogenie (phylogeny) s kořenem, bez kořene větve (branches, edges) vnější, vnitřní, centrální uzly (nodes, vertices) vnitřní, terminální (externí) dichotomie, polytomie OTU, HTU network No. Taxons Unrooted trees Rooted trees 3 4 více než elektronů ve viditelném 5 6 7 8 9 10 vesmíru (Eddingtonovo číslo) 11 12 13 14 15 20 30 40 50 1 3 15 105 945 10 395 135 135 2 027 025 34 459 425 654 729 075 13 749 310 575 316 234 143 225 7 905 853 580 625 213 458 046 676 875 8 200 794 532 637 891 559 375 4,9518xl038 » l,00986xl057 3 15 105 945 10 395 135 135 2 027 025 34 459 425 654 729 075 13 749 310 575 316 234 143 225 7 905 853 580 625 213 458 046 676 875 8 200 794 532 637 891 559 375 4,9518xl038 l,00986xl057 _2,75292xl076 Úvod Jaké typy dat můžeme použít? DATA Distance Diskrétní znaky Imunologie DNA-DNA hybridizace Binární 11010010011 Vícestavové ABCDEF • neseřazené • seřazené ACGTTAGCT A->B->C Úvod 1. Nukleotidové a proteinové sekvence: Hsapiens MTPMRKINPLMKLINHSFIDLPTPSNISAWWNFGS báze = stav znaku P_troglod ATGACCCcGACaCGCAAAATTAACCCACTAATAAA pozice (site) = znak 2. Restrikční data: * restriction-site data * restriction-fragment data (RFLP) Restrikční místo = znak přítomnost/absence = stav znaku = fragment = znak přítomnost/absence stav znaku absence nezávislosti! Typy dat Typy dat Úvod 3. Alozymy: alela = znak, přítomnost/absence = stav znaku lokus = znak, alela = stav znaku lokus = znak, alelová frekvence = stav znaku 4. Pořadí genů 5. Retroelementy: SINE (Alu, B1, B2), LINE 6. VNTR, STR, SNP Úvod VlaStnOSti ZnakŮ: * nezávislost (morfologie, alozymy, pořadí genů) * homologie Problém homologie sekvencí paralogous -► xenologous orthologous Práce se sekvencemi DNA databáze: • EMBL (European Molecular Biology Laboratory) - European Bioinformatics Institute, Hinxton, UK: http://www.ebi.ac.uk/embl/ • GenBank - NCBI (National Center for Biotechnology Information), Bethesda, Maryland, USA: http://www.ncbi. nlm.nih. gov/Genbank/ • DDBJ (DNA Data Bank of Japan) - National Institute of Genetics, Mishima, Japan: http://www.ddbj. nig.ac.jp/ Proteinové databáze: • SWISS-PROT - University of Geneve & Swis Institute of Bioinformatics: http://www.expasy.ch/sprot/ a http://www.ebi.ac.uk/swissprot/ • PIR (Protein Information Resource) - NBRF (National Biomedical Research Foundation, Washington, D.C., USA) & Tokyo University & JIPID (Japanese International Protein Information Database, Tokyo) & MIPS (Martinsried Institute for Protein Sequences, Martinsried, Germany): http://www-nbrf.georgetown.edu/ • PRF/SEQDB (Protein Resource Foundation) - Osaka, Japan: http://www.prf.or.jp/en/os.htm • PDB (Protein Data Bank) - University of New Jersey, San Diego & Super-computer Center, University of California & National Institute of Standards and Technology: http://www.rcsb.org/pdb/ Práce se sekvencemi GenBank: ORIGIN 1 tgaaatgaag 61 cacccaaagc 121 tagtacattt 181 ttaatcaatg 241 ttatactaat 301 tacagtcata 361 taccatcctc 421 attaaacttg 481 catcaaatgc 541 ctaatcagcc 601 cctactttca 661 tacggtgaag 721 ttagacataa 781 cttaatgcca 841 ccctatgtcc 901 aaaattttac 961 aatattaaca 1021 taattttatc Formáty souborů atattctctt tggcattcta atgtatatcg atataggcca acatcaaatt aactcttctc cgtgaaacca ggggtagcta gttatcgccc catgaccaac tcaacatagc aatcattagt atgctactca aaccccaaaa tgatcgattc aaaatcatgc agttaatgta cca ctcaagacat attaaactac tacattaaac taaaacaatt aatgctttaa ttccatatga acaacccgcc aactgaaact atacgttccc ataactgtgg cgtcaaggca ccgcaaaacc ataccaaatt acactaagaa tagtagttcc tccgtgaacc gcttaataac caagaagaag ttcttgtgta tattttcccc atcaacataa agacatatct ctatcccctt caccaatgcc ttatcagaca cttaaataag tgtcatgcat tgaaaggaca caatcaccta ttaactctcc cttgaaagac caaaatatga aaaactctaa aaagcaaagc gaactactcc cataaattta aagcatataa actgatacaa gtgttatctg ccccatttgg cctcttctcg tctggttctt acatctcgat ttggtatttt gcacacagtc aggctaatta aaacccccca atatattatt ctcatatttt tcacactcta actgaaaatg ccaccaccag catagtacaa gcaagtacat accatgaata acatacacca tctattaatc ctccgggccc acttcagggc ggtatcgggt tttattttgg tagacgcacc ttcatgcttg accccctcct aactatcaaa agtacttgta ttacgcaata cttagatgga Práce se sekvencemi Formáty souborů FASTA: >H_sapiens ATGACCCCAATACGCAAAATTAACCCCCTAATAAAATTAATTAACCACTCATTCATCGACCTCCCCACCC CATCCAACATCTCCGCATGATGAAACTTCGGCTCACTCCTTGGCGCCTGCCTGATCCTCCAAATCACCAC AGGACTATTCCTAGCCATACACTACTCACCAGACGCCTCAACCGCCTTTTCATCAATCGCCCACATCACT CGAGACGTAAATTATGGCTGAATCATCCGCTACCTTCACGCCAATGGCGCCTCAATATTCTTTATCTGCC TCTTCCTACACATCGGGCGAGGCCTATATTACGGATCATTTCTCTACTCAGAAACCTGAAACATCGGCAT • • • >P_troglod ATGACCCCGACACGCAAAATTAACCCACTAATAAAATTAATTAATCACTCATTTATCGACCTCCCCACCC CATCCAACATTTCCGCATGATGGAACTTCGGCTCACTTCTCGGCGCCTGCCTAATCCTTCAAATTACCAC AGGATTATTCCTAGCTATACACTACTCACCAGACGCCTCAACCGCCTTCTCGTCGATCGCCCACATCACC CGAGACGTAAACTATGGTTGGATCATCCGCTACCTCCACGCTAACGGCGCCTCAATATTTTTTATCTGCC TCTTCCTACACATCGGCCGAGGTCTATATTACGGCTCATTTCTCTACCTAGAAACCTGAAACATTGGCAT • • • >P_paniscus ATGACCCCAACACGCAAAATCAACCCACTAATAAAATTAATTAATCACTCATTTATCGACCTCCCCACCC CATCCAATATTTCCACATGATGAAACTTCGGCTCACTTCTCGGCGCCTGCCTAATCCTTCAAATCACCAC AGGACTATTCCTAGCTATACACTACTCACCAGACGCCTCAACCGCCTTCTCATCGATCGCCCACATTACC CGAGACGTAAACTATGGTTGAATCATCCGCTACCTTCACGCTAACGGCGCCTCAATACTTTTCATCTGCC TCTTCCTACACGTCGGTCGAGGCCTATATTACGGCTCATTTCTCTACCTAGAAACCTGAAACATTGGCAT Práce se sekvencemi Formáty souborů PHYLIP ("interleaved" format): 6 1120 H_sapiens P_troglod P_paniscus G_gorilla P_pygmaeus H_lar ATGACCCCAA ATGACCCCGA ATGACCCCAA ATGACCCCTA ATGACCCCAA ATGACCCCCC ATTCATCGAC ATTTATCGAC ATTTATCGAC ATTCATTGAC ACTCATCGAC ACTTATCGAC TACGCAAAAT CACGCAAAAT CACGCAAAAT TACGCAAAAC TACGCAAAAC TGCGCAAAAC CTCCCCACCC CTCCCCACCC CTCCCCACCC CTCCCTACCC CTCCCCACCC CTTCCAGCCC TAACCCCCTA TAACCCACTA CAACCCACTA TAACCCACTA CAACCCACTA TAACCCACTA CATCCAACAT CATCCAACAT CATCCAATAT CGTCCAACAT CATCAAACAT CATCCAACAT ATAAAATTAA ATAAAATTAA ATAAAATTAA GCAAAACTAA ATAAAATTAA ATAAAACTAA CTCCGCATGA TTCCGCATGA TTCCACATGA CTCCACATGA CTCTGCATGA TTCTATATGA TTAACCACTC TTAATCACTC TTAATCACTC TTAACCACTC TTAACCACTC TCAACCACTC TGAAACTTCG TGGAACTTCG TGAAACTTCG TGAAACTTCG TGGAACTTCG TGAAACTTTG Práce se sekvencemi Formáty souborů NEXUS (PAUP*, "interleaved"): #NEXUS begin data; dimensions ntax=6 nchar=1120; format datatype=DNA interleave datatype=DNA missing=? gap=-; matrix ATGACCCCGACACGCAAAATTAACCCACTAATAAAATTAATTAATCACTC ATGACCCCAACACGCAAAATCAACCCACTAATAAAATTAATTAATCACTC ATGACCCCAATACGCAAAATTAACCCCCTAATAAAATTAATTAACCACTC ATGACCCCTATACGCAAAACTAACCCACTAGCAAAACTAATTAACCACTC ATGACCCCAATACGCAAAACCAACCCACTAATAAAATTAATTAACCACTC ATGACCCCCCTGCGCAAAACTAACCCACTAATAAAACTAATCAACCACTC P_troglod P_paniscus H_sapiens G_gorilla P_pygmaeus H_lar P_troglod P_paniscus H_sapiens G_gorilla P_pygmaeus H_lar ATTTATCGACCTCCCCACCCCATCCAACATTTCCGCATGATGGAACTTCG ATTTATCGACCTCCCCACCCCATCCAATATTTCCACATGATGAAACTTCG ATTCATCGACCTCCCCACCCCATCCAACATCTCCGCATGATGAAACTTCG ATTCATTGACCTCCCTACCCCGTCCAACATCTCCACATGATGAAACTTCG ACTCATCGACCTCCCCACCCCATCAAACATCTCTGCATGATGGAACTTCG ACTTATCGACCTTCCAGCCCCATCCAACATTTCTATATGATGAAACTTTG end; Práce se sekvencemi Formáty souborů Clustal: P_troglod ATGACCCCGACACGCAAAATTAACCCACTAATAAAATTAATTAATCACTCATTTATCGAC P_paniscus ATGACCCCAACACGCAAAATCAACCCACTAATAAAATTAATTAATCACTCATTTATCGAC H_sapiens ATGACCCCAATACGCAAAATTAACCCCCTAATAAAATTAATTAACCACTCATTCATCGAC G_gorilla ATGACCCCTATACGCAAAACTAACCCACTAGCAAAACTAATTAACCACTCATTCATTGAC P_pygmaeus ATGACCCCAATACGCAAAACCAACCCACTAATAAAATTAATTAACCACTCACTCATCGAC H_lar ATGACCCCCCTGCGCAAAACTAACCCACTAATAAAACTAATCAACCACTCACTTATCGAC ******** ******* ***** *** **** **** ** ****** * ** *** P_troglod CTCCCCACCCCATCCAACATTTCCGCATGATGGAACTTCGGCTCACTTCTCGGCGCCTGC P_paniscus CTCCCCACCCCATCCAATATTTCCACATGATGAAACTTCGGCTCACTTCTCGGCGCCTGC H_sapiens CTCCCCACCCCATCCAACATCTCCGCATGATGAAACTTCGGCTCACTCCTTGGCGCCTGC G_gorilla CTCCCTACCCCGTCCAACATCTCCACATGATGAAACTTCGGCTCACTCCTTGGTGCCTGC P_pygmaeus CTCCCCACCCCATCAAACATCTCTGCATGATGGAACTTCGGCTCACTTCTAGGCGCCTGC H_lar CTTCCAGCCCCATCCAACATTTCTATATGATGAAACTTTGGTTCACTCCTAGGCGCCTGC ** ** **** ** ** ** ** ****** ***** ** ***** ** ** ****** Práce se sekvencemi Seřazení sekvencí (alignment) Sekvence 1 Sekvence 2 TTGTACGACGG TTGTACGACG TTGTACGACGG TTGT---ACGACGG TTGTACGACG TTGTACGACG gap penalty Sekvence 1 Sekvence 2 ACTTGTGCTTC ACGTGCTGCTC Path 1 ACGTGCTGCTC ACTTGTGCTTC Path 2 G C A G GG C A • • y y • • • • M • T GP = g + hl g - gap penalty h - gap extension penalty l - gap length • • • C G A C G G • • T C G T C G T G C C A • • • • • • • • • • • • • • • • A C T T G T G C T T C Práce se sekvencemi Progresivní seřazení - ClustalX 3 fáze: 1. Seřazení dvojic sekvencí -> párové distance 2. Konstrukce „guide tree" (NJ) 3. Seřazení všech sekvencí podle stromu I, I, Práce se sekvencemi Problém progresivního seřazení 6 druhů: gorila kůň panda AGGTT AG-TT AG-TT tučňák kuře pštros A-GTT A-GTT AGGTT AGGTT AG-TT AG-TT AG-TT AG-TT AGGTT gorila kůň panda tučňák kuře pštros AGGTT AG-TT AG-TT A-GTT A-GTT AGGTT AGGTT A-GTT A-GTT A-GTT A-GTT AGGTT Rozdělení metod Rozdělení metod Typy dat distance znaky •UPGMA • neighbor-joining • Fitch-Margoliash • minimum evolution • maximum parsimony • maximum likelihood • Bayesian a. Rozdělení metod Jak hodnotit jednotlivé metody? • výkonnost (efficiency): jak rychlá je metoda? • síla (power): • konzistence (consistency): • robustnost (robustness): kolik znaků je třeba? vede zvyšující se počet znaků ke správnému stromu? jak metoda funguje při neplatnosti předpokladů? • falzifikovatelnost (falsifiability): umožňuje testování platnosti předpokladů? Maximální úspornost (maximum parsimony, MP) Parsimonie I II III A 1 0 1 B 0 0 1 C 1 0 0 D 0 1 0 E 1 0 1 William of Occam (c. 1285 - c. 1349): Occamova břitva minimální počet kroků = 3 skutečný počet kroků = 5 2 extra kroky -> homoplasie 2 kroky Parsimonie Odhad počtu kroků Fitchův (1971) algoritmus 1. arbitrárni kořen 2. top -» bottom: w= C nebo T x = T y = A nebo T z = T 3. bottom-> top: z = T nebo A C T T TA C T T TA 3 Parsimonie Problém homoplasie: • parsimony-informative and non-informative characters (sites) - invariant sites (symplesiomorphies) - singletons (autapomorphies) • index konzistence (consistency i., CI) y y ~y - retenční index (retention i., Rl) = 7 = 7 81 ~s' • upravený Cl (rescaled Cl, RC) CI M Zg7-£m~, - index homoplasie (homoplasy i., HI) RC = CI x RI HI = 1 - CI m = min. no. of possible steps s = min. no. needed for explaining the tree g = max. no. of steps for any tree Parsimonie • Fitch parsimony: • Wagner parsimony: • Dollo parsimony: ... restriction-site and Metody parsimonie X^Yand Y^X unordered characters (A^TorA^ G etc.) X^Yand Y^X ordered characters (1 -> 2 -> 3) X -> Y and Y -> X, then no X -> Y restriction-fragment data Camin-Sokal p.: SINE, LINE X->Y, noY^X weighed (transversion) p. "relaxed Dollo criterion" generalized parsimony: cost matrix (step matrix) Hledání optimálního stromu a měření spolehlivosti 1. Exaktní metody: a) vyčerpávající hledání (exhaustive search) b) branch-and-bound Hledání optimálního stromu 2. Heuristický přístup: stepwise addition star decomposition branch swapping Hledání optimálního stromu NNI 3 4 1 2 ,5 3t \ / 5 -6 2- j- j t r- • 7 1 SPR TBR 3 4 \ —* 5 3 4 3 1 5 3 4 2 3 5 2 3 4 3 /I _ ^5 3 4 2 6 2 6 ,3 4 3 6 7 4 5 4 5 1 5 4 * nearest-neighbor interchanges (NNI) * subtree prunning and regrafting (SPR) * tree bisection and reconnection (TBR) 2 6 5 2 7 Parsimonie a konzistence Parsimonie "správný" p>>q V 0.5 Felsensteinova zóna P < í(l - q) x 15 VY "chybný" 1 B D ((A,C),(B,D)) Parsimonie a konzistence Parsimonie Parsimonie a konzistence Parsimonie Původní báze A C G T Báze po substituci ACG -% % % % -% % % % -% %%% T % % % -% Q Jukes-Cantor (JC): stejné frekvence bází stejné frekvence substitucí Evoluční modely a distanční metody Kimura 2-parameter (K2P): transice * transverze Evoluční modely r Q = - p a p p - p a a p - p p a p - v J Jestliže a = (3, K2P = JC Evoluční modely Felsenstein (F81): různé frekvence bází r *\ Q = 71 C 7tA 7tA 7tG 7lG 71 A 71 71 C C 7lT 7lT 7lT 71 G V. Jestliže tiA = tiC = tiG = ttT, F81 = JC Hasegawa-Kishino-Yano (HKY): různé frekvence bází transice * transverze r Q — - 7TCP 7TGa 7TTP 71A P — 7TGP 7iAa 7TCP — 7rTP 7TAP 7ica 7TGP — V. General time-reversible (GTR, REV): různé frequence bází různé frekvence všech substitucí Evoluční modely nestejné frekvence bází Jukes-Cantor (JC) 7rA=7rc=7rG=7rj CC—ß více než 1 typ substituce Felsenstein (F81) CC—ß Kimura's two-parameter (K2P) a*ß Felsenstein (F84) a=c=d=f='\, ö=(1+K/ttr), e=(1+K/^Y), kde ^R=^A+^G 2 typy transicí Hasegawa-Kishino-Yano (HKY) c&ß Tamura-Nei (TrN) Ofrß Kimura's three- substitution-type (K3ST) 7lf = 7rc=7TG=7lj Cfrß General-time reversible (GTR) a, b, c, d, e, f Evoluční modely Heterogenita substitučních rychlostí v různých částech sekvence Gama (ľ) rozdělení: • parametr tvaru a • diskrétní gama model • invariantní pozice -> GTR+ r+i Substitution rate Porovnání modelů Který model vybrat? Evoluční modely Likelihood ratio test (LRT): nested models LR = 2(ln/_2 - lnL1) Chi-square, p2 - p1 d.f. Akaike information criterion (AIC): nonnested models AIC = -2lnL + 2p, where p = number of free parameters better model smaller AIC • Bayesian information criterion (BIC): nonested models BIC = -2lnL + pln/V, where N = sample size Evoluční modely Porovnání modelů hierarchický LRT - ModelTest (Crandall and Posada) Porovnání modelů Evoluční modely dynamický LRT Porovnání modelů Evoluční modely Více parametrů => více realismu, ale ■ ■ ■ ■ ■ ■ také více neurčitosti, protože jsou odhadovány ze stejného množství dat Distance Distance • počítány pro každý pár taxonů, z matice distancí (nebo podobností) konstruován strom • distanční metody založeny na předpokladu, že pokud bychom znali skutečné distance mezi všemi studovanými taxony, mohli bychom velmi jednoduše rekonstruovat správnou fylogenii • výhoda: velmi rychlé a jednoduché (lze i na kalkulačce) Distance Distance 1 10 20 30 sekvence 1: ACCCGTTAAGCTTAACGTACTTGGATCGAT sekvence 2: ACCCGTTAGGCTTAATGTACGTGGATCGAT p-distance: p = kin = 3/30 = 0.10 problém saturace: Time Distance pro některé modely: Distance JC 3 ( 4 ^ d = ~ -ln| 1 ~ -D ! xy 4 V 3 ) D = 1 - (a + f + k+p) F81 ( D ^ d = -B lnj 1 " — j xy I B ) D = jako JC B = 1 - (7Ta2 + 7Tc2 + 7Tg2 + TTt2) K2P 1 { 1 \ 1 { 1 1 d = -lni -l+-lnl -1 xy 2 U~24 U~2Q) rozdíly typu transicí: P = c + h + i + n rozdíly typu transverzí: Q = b + d + e + g + j + l + m + o F84 ( P (A-B) Q ^ d = -2Aln| 1-----—\ + xy I 2 A 2 AC J Q 2( A ~ B-C )ln| I" — j V 2C ) 7Ty= 7TQ+ 7Tj, 7Tr = 71 a + 7Tq, A = 7c7tt/7Zy + XaTTg/Xr, B = TIqTIt + 7TA7TG, C=^Y,^agjakoK2P GTR dxy = "stopa IIln TI 1 Fxy- n = diagonální matice průměrných četností bází v sekvencích X a Y Distance pro některé modely: Distance 0.0 0.5 1.0 1.5 Expected differences per site Shluková analýza - UPGMA Distance šimpanz (S) bonobo (B) gorila (G) člověk (Č) orangutan (O) šimp. 0,0118 0,0427 0,0382 0,0953 bonobo gorila člověk orang. 0,0416 0,0327 0,0916 0,0371 0,0965 0,0928 1. Najdi min d(ij) 2. Vypočítej novou matici d(ŠB-k) = [d(B-k)+d(Š-k)]/2 3. Opakuj 1 a 2. SB gorila (G) člověk (Č) orangutan (O) SB 0,0422 0,0355 0,0935 0,0371 0,0965 0,0928 UPGMA: d[(BŠČ)G] = {d(BG)+d(ŠG)+d(ČG)}/3 WPGMA: d[(BŠČ)G] = {d[(BŠ)G] + d(ČG)}/2 single-linkage complete-linkage gorila člověk orang. S B C G Distance UPGMA a konzistence aditivní distance: dAB + dCD < max (dAC + dBD, dAD + dBC) tj. vzdálenost mezi 2 taxony je rovna součtu větví, které je spojují A A D B C ultrametrické distance: dAC < max (dAB, dBC) C B aditivní strom ultrametrický strom UPGMA a konzistence Distance Distance Spojení sousedů (neighbor-joining, NJ) Algoritmická metoda Princip minimální evoluce -> minimalizuje součet délek větví S Každý pár uzlů adjustován na základě divergence od ostatních Konstrukce jediného aditivního stromu hvězdicový nalezení přepočítání a) n strom b) nejbližších sousedů distancí opakování postupu ... Distance Nevýhody distančních dat: 1. ztráta části informace během transformace 2. jakmile data transformována na distance, nelze se vrátit zpět (odlišné sekvence mohou dát stejné distance) 3. nelze sledovat evoluci na různých částech sekvence 4. obtížná biologická interpretace délek větví 5. nelze kombinovat různé distanční matice