UVOD 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 Definice základních pojmů Uvod a) periferal branch rooted tree dichotomy polytomy (bifurcation) (multifunction) terminal < node internal node b) internal branch c) path root 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álni (externí) • dichotomie, polytomie • OTU, HTU f d a b c e g star tree ^ i 2345 632 146 5 Kolik existuje stromů? Uvod x (2n - 5)! 2 n - 3(n - 3)! X/ (2n - 3)! 2n-2(n-2)! No. Taxons Unrooted trees Rooted trees 3 1 3 4 více než elektronů ve viditelném 3 1S S vesmíru (Eddingtonovo číslo) 1S 10S 6 10S 94S 7 94S 10 39S S 10 39S 13S 13S 9 13S 13S 2 027 02S 10 2 027 02S 34 4S9 42S 11 34 4S9 42S 6S4 729 07S 12 6S4 729 07S 13 749 310 S7S 13 13 749 310 S7S 316 234 143 22S 14 316 234 143 22S 7 90S SS3 SS0 62S 1S 7 90S SS3 SSO 62S 213 4SS 046 676 S7S 20 213 4SS 046 676 S7S S 200 794 S32 637 S91 SS9 37S 30 S 200 794 S32 637 S91 SS9 37S 4,9SlSxl03S 40 4,9SlSxl03S l,009S6xl0S7 SO 2,7S292xl076 Úvod Jaké typy dat můžeme použít? DATA Distance Imunologie DNA-DNA hybridizace Diskrétní znaky Binární 11010010011 Vícestavové ABCDEF • neseřazené • seřazené ACGTTAGCT A®B®C Uvod Typy dat 1. Nukleotidové a proteinové sekvence: H_sapiens MTPMRKINPLMKLINHSFIDLPTPSNISAWWNFGS báze = stav znaku P_troglod ATGACCCcGAcACGCAAAATTAACCCACTAATAAA pozice (site) = znak 2. Restrikční data ± ± ± Reštrikční místo = znak přítomnost/absence = stav znaku * restriction-site data * restriction-fragment data (RFLP) fragment = znak přítomnost/absence = stav znaku absence nezávislosti! Typy dat 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 (A/u, B1, B2), LINE 6. VNTR, STR, SNP Vlastnosti znaku: * nezávislost (morfologie, alozymy, pořadí genU) * homologie Problém homologie sekvencí paralogous 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.ddbi.nig.ac.ip/ 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. orjp/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 Formáty souborů GenBank: ORIGIN 1 61 121 181 241 301 3 61 421 481 541 601 661 721 781 841 901 961 1021 // tgaaatgaag cacccaaagc tagtacattt ttaatcaatg ttatactaat tacagtcata taccatcctc attaaacttg catcaaatgc ctaatcagcc cctactttca tacggtgaag ttagacataa cttaatgcca ccctatgtcc aaaattttac aatattaaca taattttatc 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 ATGACCCCAA TACGCAAAAT TAACCCCCTA ATAAAATTAA TTAACCACTC P troglod ATGACCCCGA CACGCAAAAT TAACCCACTA ATAAAATTAA TTAATCACTC P paniscus ATGACCCCAA CACGCAAAAT CAACCCACTA ATAAAATTAA TTAATCACTC G gorilla ATGACCCCTA TACGCAAAAC TAACCCACTA GCAAAACTAA TTAACCACTC P pygmaeus ATGACCCCAA TACGCAAAAC CAACCCACTA ATAAAATTAA TTAACCACTC H_lar ATGACCCCCC TGCGCAAAAC TAACCCACTA ATAAAACTAA TCAACCACTC ATTCATCGAC CTCCCCACCC CATCCAACAT CTCCGCATGA TGAAACTTCG ATTTATCGAC CTCCCCACCC CATCCAACAT TTCCGCATGA TGGAACTTCG ATTTATCGAC CTCCCCACCC CATCCAATAT TTCCACATGA TGAAACTTCG ATTCATTGAC CTCCCTACCC CGTCCAACAT CTCCACATGA TGAAACTTCG ACTCATCGAC CTCCCCACCC CATCAAACAT CTCTGCATGA TGGAACTTCG ACTTATCGAC CTTCCAGCCC CATCCAACAT TTCTATATGA 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 P_troglod ATGACCCCGACACGCAAAATTAACCCACTAATAAAATTAATTAATCACTC P_paniscus ATGACCCCAACACGCAAAATCAACCCACTAATAAAATTAATTAATCACTC H_sapiens ATGACCCCAATACGCAAAATTAACCCCCTAATAAAATTAATTAACCACTC G_gorilla ATGACCCCTATACGCAAAACTAACCCACTAGCAAAACTAATTAACCACTC P_pygmaeus ATGACCCCAATACGCAAAACCAACCCACTAATAAAATTAATTAACCACTC H_lar ATGACCCCCCTGCGCAAAACTAACCCACTAATAAAACTAATCAACCACTC P_troglod ATTTATCGACCTCCCCACCCCATCCAACATTTCCGCATGATGGAACTTCG P_paniscus ATTTATCGACCTCCCCACCCCATCCAATATTTCCACATGATGAAACTTCG H_sapiens ATTCATCGACCTCCCCACCCCATCCAACATCTCCGCATGATGAAACTTCG G_gorilla ATTCATTGACCTCCCTACCCCGTCCAACATCTCCACATGATGAAACTTCG P_pygmaeus ACTCATCGACCTCCCCACCCCATCAAACATCTCTGCATGATGGAACTTCG H_lar 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 ACTTGTGCTTC Sekvence 2 ACGTGCTGCTC Path 1 ACGTGCTGCTC ACTTGTGCTTC Path 2 G C A G GG C A • • y y y • y • • y • • GP = g + hl g - gap [penalty h - gap extensi on penalty l -gap length • • • C G A C G G • • T C G T C G T G C C A • • • • • • • • • • • • • • • • ACTTGTGCTTC 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. II. III Práce se sekvencemi Problém progresivního seřazení 6 druhů: gorila kun panda AGGTT AG-TT AG-TT tučnák kuře pštros A-GTT A-GTT AGGTT AGGTT AG-TT AG-TT AG-TT AG-TT AGGTT gorila kun panda tučná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 E o o> o 0) o "O o 'cd Typy dat distance znaky íms •UPGMA O O • neighbor- joining • Fitch- • maximum tériun imalit Margoliash parsimony • maximum krit opt • minimum evolution likelihood • Bayesian a. Rozdělení metod Jak hodnotit jednotlivé metody? • výkonnost (efficiency): jak rychlá je metoda? • síla (power): kolik znaků je třeba? • konzistence (consistency): vede zvyšující se počet znaků ke správnému stromu? • robustnost (robustness): 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 a) 2 kroky 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 1 krok Odhad počtu kroků Fitchův (1971) algoritmus Parsimonie a) 6 (A) 5 (A) b) 4 (T) [c,t] 2 (T) J (T) C) 1 d) DELTRAN (DELayed TRANsformation) 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 celková délka = 3 ACCTRAN (ACCelerated TRANsformation) Parsimonie Problém homoplasie: • parsimony-informative and non-informative characters (sites) - invariant sites (symplesiomorphies) - singletons (autapomorphies) index konzistence (consistency i., Cl) ^ V ^ V retenční index (retention i., Rl) m r ™ < ¥ CI = ^— RI upravený CI (rescaled CI, RC) £ s, £ gi - £ m index homoplasie (homoplasy i., HI) ' < < i RC = n m m = min- no. of possible steps Hf - in s = min- no. needed for explaining the tree - 1 - n g = max. no. of steps for any tree Parsimonie Metody parsimonie Fitch parsimony: X ® Y and Y ® X unordered characters (A ® T or A ® G etc.) Wagner parsimony: X ® Y and Y ® X ordered characters (1 ® 2 ® 3) Dollo parsimony: X ® Y and Y ® X, then no X ® Y ... restriction-site and restriction-fragment data Camin-Sokal p.: SINE, LINE X ® Y, no Y ® 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 4 SPR 1 3 7 i 3 / \ i 5 .4 1 _ nearest-neighbor interchanges (NNI) subtree prunning and regrafting (SPR) TBR 3 4 2 6 5 2 2 6 3 6 * tree bisection and reconnection (TBR) Parsimonie Parsimonie a konzistence 0 -I-1-1-1-1-1 q 05 W Parsimonie a konzistence Success Parsimonie Parsimonie a konzistence dlouhé větve „přitažlivost dlouhých větví" (long-branch attraction, LBA) Evoluční modely a distanční metody Báze po substituci A C G T A -% % % % Původní báze C % -% % % G % % % T % % % -% r — a a a Q = a — a a a a — a a a a ) Jukes-Cantor (JC): stejné frekvence bází stejné frekvence substitucí Evoluční modely Kimura 2-parameter (K2P): transice + transverze r Q = — a b b — b a a b — b a b — J Jestliže a = b, K2P = JC Evoluční modely Felsenstein (F81): různé frekvence bází Q = — pt pa — pt pa — pt pa — J Jestliže pA = pC = pG = pT, F81 = JC Hasegawa-Kishino-Yano (HKY) různé frekvence bází transice + transverze r Q = — PtP — pTa pAa — PtP — J 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) pA=pC=pG=pT _a=j3 více než 1 typ substituce 2 typy transicí Evoluční modely Heterogenita substitučních rychlostí v různých částech sekvence Gama (l~) rozdělení: 0.08 r • parametr tvaru a ^0.06 a = 200 • diskrétní gama model § A / • invariantní pozice ® GTR+ r+i c £ 0.04 a = 0.5 / y / a = 2 / 1 / / / 1 a = 50 0.02 0 1 2 Substitution rate Porovnání modelů Který model vybrat? Evoluční modely • Likelihood ratio test (LRT): nested models LR = 2(lnL2 -lnL1) Chi-square, p2 - pi d.f. Akaike information criterion (AIC): nonnested models AIC = -2lnL + 2p, where p = number of free pars. better model ® smaller AIC • Bayesian information criterion (BIC): nonested models BIC = -2lnL + plnN, where N = sample size Evoluční modely Porovnání modelů hierarchický LRT - ModelTest (Crandall and Posada) Evoluční modely Porovnání modelů dynamický LRT Evoluční modely Porovnání modelů Real data A C G T A C G T O A C G T K2P C G T A C G T O A C G T • O HKY85 A C G A C G T O o • 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 Distance pro některé modely: JC d vy = — 3 ln 1 — D 4 V 3 y N / D = 1 - (a + / + k + p) F81 d vy =— Blníl — D1 D = jako JC B = 1 - (^a2 + p2 + PG + PT2) K2P 1 ( 1 1 1 d l l l Í 1 1 rozdíly typu transicí: P = c + h + i + n rozdíly typu transverzí: Q = b + d + e + g + j + / + m + o F84 , ^ P (A — B)Q 1 vy V 2A 2 AC J 2(A B C)ln^1 Q J Py = PC + Pt, Pr = PA + PG, A = PcPt/py + PaPg/Pr, B = pcpt + PaPG, C = PrPy, P a Q jako K2P GTR d vy =—stopa [H ln(n—1 Fxy)] n = diagonální matice průměrných četností bází v sekvencích X a Y Distance pro některé modely: Expected differences per site Shluková analýza - UPGMA šimpanz (Š) 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 Distance 1. Najdi min d(ij) 2. Vypočítej novou matici d(ŠB-k) = [d(B-k)+d(Š-k)]/2 3. Opakuj 1 a 2. ŠB gorila (G) člověk (Č) orangutan (O) UPGMA: d[(BŠČ)G] WPGMA: d[(BŠČ)G] single-linkage complete-linkage ŠB 0,0422 0,0355 0,0935 gorila člověk orang. 0,0371 0,0965 0,0928 = = {d(BG)+d(ŠG)+d(ČG)}/3 {d[(BŠ)G] + d(ČG)}/2 Š B Č G O 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 D B C ultrametrické distance: dAC £ max (dAB, dBC) B aditivní strom ultrametrický strom Distance UPGMA a konzistence 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í ) m strom b) nejbližších sousedů c) distancí opakování postupu ... 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