分子进化树构建方法课件

第五章第五章系谱分析系谱分析生物信息学第五章生物信息学1 2.系统发生分析（系统发生分析（Phylogenetic analysis)u分析基因或蛋白质的进化关系分析基因或蛋白质的进化关系u系统发生（进化）树（系统发生（进化）树（phylogenetic tree）A tree showing the evolutionary relationships among various biological species or other entities that are believed to have a common ancestor.2.系统发生分析（Phylogenetic anal2经典进化生物学：经典进化生物学：比较：比较：形态形态、生理结构生理结构、化石化石分子进化生物学：分子进化生物学：比较比较DNA和和蛋白质蛋白质序列序列研究系统发生的方法研究系统发生的方法经典进化生物学：研究系统发生的方法3Residues that are lined up in different sequences are considered to share a common ancestry(i.e.,they are derived from a common ancestral residue).An Alignment is an hypothesis of positional homology between bases/Amino AcidsEasyonly with substitutionsDifficultalso with indelsResidues that are lined up in 4=(A,(B,C),(D,E)Newick format节点节点Node分支分支BranchABCDE末端节点末端节点 可以是物种，可以是物种，群体，或者蛋群体，或者蛋白质、白质、DNA、RNA分子分子等等OTU祖先节点祖先节点/树树根根Root系统发生树术语系统发生树术语内部节点内部节点/分歧点分歧点该分支可能的祖先该分支可能的祖先HTU=(A,(B,C),(D,E)Newick 5A clade（进化支进化支）is a group of organisms that includes an ancestor and all descendents of that ancestor.genetic changeno meaningPhylogramCladogramtimeTaxon ATaxon BTaxon CTaxon D111635Taxon ATaxon BTaxon CTaxon DTaxon ATaxon BTaxon CTaxon DUltrametric tree超度量树超度量树进化树进化树分支树分支树系统发生树术语系统发生树术语A clade（进化支）is a group of org6Rooted tree vs.Unrooted treetwo major ways to root trees:A BCD102352d(A,D)=10+3+5=18Midpoint=18/2=9By midpoint or distance有有根根树树ACBD无无根根树树系统发生树术语系统发生树术语outgroup外群、外围支外群、外围支Rooted tree vs.Unrooted treet7plantplantplantfungusanimalanimalanimalUnrooted treerootRooted treebacteriumanimalanimalanimalfungusplantplantplantMonophyletic groupMonophyleticgroupRooted tree vs.Unrooted treeplantplantplantfungusanimalani8选择外群（Outgroup）选择一个或多个已知与分析序列关系较远的序列作为外类群外类群可以辅助定位树根外类群序列必须与进化树上其它序列同 源，但外类群序列与这些序列间的差异必须比这些序列之间的差异更显著。eukaryoteeukaryoteeukaryoteeukaryotearchaeaarchaeaarchaeabacteria outgroup外群外群How to root a tree?选择外群（Outgroup）选择一个或多个已知与分析序列关9系统发育树构建步骤系统发育树构建步骤多序列比对（自动比对、手工校正）多序列比对（自动比对、手工校正）选择建树方法（选择建树方法（替代模型替代模型）建立进化树建立进化树进化树评估进化树评估最大简约法最大简约法(maximum parsimony,MP)距离法距离法(distance)最大似然法最大似然法(maximum likelihood,ML)贝叶斯法贝叶斯法(Bayesian inference)统计分析统计分析BootstrapLikelihood Ratio Test UPGMA邻近法邻近法(Neighbor-joining,NJ)最小进化法最小进化法(minimum evolution)系统发育树构建步骤多序列比对（自动比对、手工校正）选择建树方10距离法距离法距离法又称距离矩阵法，首先通过各个序列之间的比较，根据一定的假设（进化距离模型）根据一定的假设（进化距离模型）推导得出分类群之间的进化距离，构建一个进化推导得出分类群之间的进化距离，构建一个进化距离矩阵。距离矩阵。进化树的构建则是基于这个矩阵中的进化距离关系。CatDogRatDog3Rat45Cow676CatDogRat11224Cow计算序计算序列的距列的距离，建离，建立距离立距离矩阵矩阵通过距通过距离矩阵离矩阵建进化建进化树树距离法距离法又称距离矩阵法，首先通过各个序列之间的比较，11Step1.计算序列的距离，建立距离矩阵计算序列的距离，建立距离矩阵Uncorrected“p”distance(=observed percentsequence difference)Kimura 2-parameter distance(estimate of the true number of substitutions between taxa)对位排列，对位排列，去除空格去除空格（选择替代模型）（选择替代模型）Step1.计算序列的距离，建立距离矩阵Uncorrect12由进化距离构建进化树的方法有很多，常见有：1.Unweighted Pair Group Method with Arithmetic mean(UPGMA)2.Neighbor-Joining Method(NJ法/邻位连接法)3.Minimum Evolution(MP法/最小进化法)Step2.通过矩阵建树通过矩阵建树由进化距离构建进化树的方法有很多，常见有：Step2.通过13最大简约法（MP）最早源于形态性状研究，现在已经推广到分子序列的进化分析中。最大简约法的理论基础是奥卡姆（Ockham）哲学原则，对所有可能的拓扑结构进行计算，找出所对所有可能的拓扑结构进行计算，找出所需替代数最小的那个拓扑结构，作为最优树。需替代数最小的那个拓扑结构，作为最优树。最大简约法(Maximum Parsimony)Find the tree that explains the observed sequences with a minimal number of substitutions最大简约法（MP）最早源于形态性状研究，现在已经推广到分14Sequence1TG CSequence2TA CSequence3A G GSequence4A A G1 2 3PositionMP法建树流程法建树流程If 1 and 2 are grouped a total of four changes are needed.If 1 and 3 are grouped a total of five changes are needed.If 1 and 4 are grouped a total of six changes are needed.Position 1 (1,2):1 change;(1,3)or(1,4):2 changesPosition 2 (1,3):1 change;(1,2)or(1,4):2 changesPosition 3 (1,2):1 change;(1,3)or(1,4):2 changesSequence1TGCSequence2TACSequen15456BESTMP法建树步骤法建树步骤456BESTMP法建树步骤16最大似然法(Maximum Likelihood)最大似然法(ML)最早应用于对基因频率数据的分析上。其原理为选取一个特定的替代模型来分析给定的一组序列数据，使得获得的每一个拓扑结构的似然率都为最大值，然后再挑出其中似然率最大的拓扑结构作为最优树。最大似然法(Maximum Likelihood)最大似然17ML法建法建树流程树流程CAGATGCCATGCML法建树流程CAGATGCCATGC18Pick an Evolutionary Model For each position,Generate all possible tree structures Based on the Evolutionary Model,calculate Likelihood of these Trees and Sum them to get the Column Likelihood for each OTU cluster.Calculate Tree Likelihood by multiplying the likelihood for each positionChoose Tree with Greatest LikelihoodInferring the maximum likelihood treePick an Evolutionary Model Inf19Holder&Lewis(2003)Nature Reviews Genetics 4,275-284 Bayesian inference:What is the probability that the model/theory is correct given the observed data?Pr(T|D)Maximum Likelihood:What is the probability of seeing the observed data(D)given a model/theory(T)?Pr(D|T)SpeedNo need for bootstrapping构建进化树的新方法构建进化树的新方法贝叶斯推断贝叶斯推断(Bayesian inference)与ML相比，BI的优势：Holder&Lewis(2003)Nature Rev20Comparison of MethodsDistanceMaximum parsimonyMaximum likelihoodUses only pairwise distancesUses only shared derived charactersUses all dataMinimizes distance between nearest neighborsMinimizes total distanceMaximizes tree likelihood given specific parameter valuesVery fastSlowVery slowEasily trapped in local optimaAssumptions fail when evolution is rapidHighly dependent on assumed evolution modelGood for generating tentative tree,or choosing among multiple treesBest option when tractable(30 taxa,homoplasy rare)Good for very small data sets and for testing trees built using other methodsComparison of MethodsDistanceM21Bioinformatics:Sequence and Genome Analysis,2nd edition,by David W.Mount.p254Choosing a Method for Phylogenetic Prediction http:/cshprotocols.cshlp.org/cgi/content/full/2008/5/pdb.ip49Molecular Biology and Evolution 2005 22(3):792-802 Bioinformatics:Sequence and G22Assessing tree reliabilityPhylogenetic reconstruction is a problem of statistical inference.One must assess the reliability of the inferred phylogeny and its component parts.Questions:(1)how reliable is the tree?(2)which parts of the tree are reliable?(3)is this tree significantly better than another one?Assessing tree reliability23A statistical technique that uses intensive random resampling of data to estimate a statistic whose underlying distribution is unknown.评估进化树的可靠性评估进化树的可靠性自展法自展法（bootstrapping method）从排列的多序列中随机有放回的抽取某一列，构成相同长度的新的排列序列重复上面的过程，得到多组新的序列对这些新的序列进行建树，再观察这些树与原始树是否有差异，以此评价建树的可靠性A statistical technique that u24The Bootstrap Computational method to estimate the confidence level of a certain phylogenetic tree.ratGAGGCTTATChumanGTGGCTTATCturtleGTGCCCTATGfruitfly CTCGCCTTTGoakATCGCTCTTGduckweed ATCCCTCCGG0123456789Samplerathumanturtlefruit flyoakduckweedInferred treeMore replicates(between 100-1000)ratGGAAGGGGCThumanGGTTGGGGCTturtleGGTTGGGCCCfruitfly CCTTCCCGCCoakAATTCCCGCTduckweed AATTCCCCCT0011222345Pseudo sample 1ratCCTTTTAAAThumanCCTTTTAAATturtleCCCCCTAAATfruitfly CCCCCTTTTToakCCTTTCTTTTduckweed CCTTTCCCCG4455567778Pseudo sample 2The Bootstrap Computational me25自展法检验流程自展法检验流程Bootstrapping doesnt really assess the accuracy of a tree,only indicates the consistency of the data对ML法而言，自展法太耗时，可用aLRT法检验进化树的可靠性Anisimova&Gascuel(2006)Syst.Biol.55(4):539-552自展法检验流程Bootstrapping doesnt r26MSA程序可对任何序列进行比对，选择什么程序可对任何序列进行比对，选择什么样的序列进行比对非常重要！样的序列进行比对非常重要！用于构建进化树的序列必须是同源序列用于构建进化树的序列必须是同源序列MSA是构建分子进化树的关键步骤是构建分子进化树的关键步骤MSA程序可对任何序列进行比对，选择什么样的序列进行比对非常27u分子进化树构建（分子进化树构建（ClustalW）页面下方页面下方 显示显示Cladogram Tree点击点击“Show as Phylogram Tree”展示展示Phylogram Tree不推荐：仅提供距离法建树，且没有进行评估不推荐：仅提供距离法建树，且没有进行评估输入比对后的序列（或上载输入比对后的序列（或上载Alignments文件）文件）EBI的的ClustalW2-phylogeny分析网页分析网页http:/www.ebi.ac.uk/Tools/phylogeny/clustalw2_phylogeny/分子进化树构建（ClustalW）页面下方 显示Cladog28u看图工具看图工具下载下载“Phylip tree file”（ph文件）文件）TreeView 进化树编辑打印软件进化树编辑打印软件（在在http:/taxonomy.zoology.gla.ac.uk/rod/treeview.html）输入比对后的序列（或上载输入比对后的序列（或上载Alignments文件）文件）用用TreeView软件打开上述文件软件打开上述文件可以不同格式展示进化树（可以不同格式展示进化树（1、2、3）EBI的的ClustalW2-phylogeny分析网页分析网页看图工具下载“Phylip tree file”（ph文件）29PHYLIP http:/evolution.genetics.washington.edu/phylip.html 免费的集成进化分析工具PAUP http:/paup.csit.fsu.edu/商业软件，集成的进化分析工具MEGA http:/ http:/atgc.lirmm.fr/phyml/最快的ML建树工具PAML http:/abacus.gene.ucl.ac.uk/software/paml.html ML建树工具Tree-puzzle http:/www.tree-puzzle.de/较快的ML建树工具MrBayes http:/mrbayes.csit.fsu.edu/基于贝叶斯方法的建树工具分子进化分析软件分子进化分析软件更多工具更多工具http:/evolution.gs.washington.edu/phylip/software.htmlPHYLIP http:/evolution.g30提供最大简约法（MP）、最大似然法（ML）和距离法三种建树方法。其中距离法包括邻接法（NJ）、最小进化法（ME）和UPGMA三种算法。u分子进化树构建方法分子进化树构建方法优点：优点：图形界面，集序列查询、比对、进化树构建为一体，帮助文件详尽，免费http:/ History of Animals Buffon(1707-1788)33始祖鸟化石始祖鸟化石复原图复原图始祖鸟化石复原图342.7%difference2.7%difference35xl,Xenopus laevis;xt,Xenopus tropicalis;gg,Gallus gallus;rn,Rattus norvegicus;mm,Mus musculus;hs,Homo sapiens.BMC Evolutionary Biology 2007 7:164 xl,Xenopus laevis;BMC Evolut36分子进化树构建方法课件37分子进化树构建方法课件38分子进化树构建方法课件39由于同一位点多重替代（multiple substitution）的发生，观测到的差异比实际替代数要小原原始始序序列列后后代代序序列列13 mutations =3 differencesDegree of divergenceTotal number of substitutions由于同一位点多重替代（multiple substituti40为了估算出正确的分歧时间（期望替代数），必须对观测到的替代数进行校正在进化的任意时间点，任意位点的核苷酸都可能发生回复和平行突变。替代模型替代模型Substitution model为了估算出正确的分歧时间（期望替代数），必须对观测到的替代数41替代模型替代模型替代模型42