1、第五章第五章多序列对位排列和进化分析多序列对位排列和进化分析（I）生物信息学chicken PLVSS-PLRGEAGVLPFQQEEYEKVKRGIVEQCCHNTCSLYQLENYCNxenopus ALVSG-PQDNELDGMQLQPQEYQKMKRGIVEQCCHSTCSLFQLESYCNhuman LQVGQVELGGGPGAGSLQPLALEGSLQKRGIVEQCCTSICSLYQLENYCNmonkey PQVGQVELGGGPGAGSLQPLALEGSLQKRGIVEQCCTSICSLYQLENYCNdog LQVRDVELAGAPGEGGLQPLALEGALQKRGIVE
2、QCCTSICSLYQLENYCNhamster PQVAQLELGGGPGADDLQTLALEVAQQKRGIVDQCCTSICSLYQLENYCNbovine PQVGALELAGGPGAGG-LEGPPQKRGIVEQCCASVCSLYQLENYCNguinea pig PQVEQTELGMGLGAGGLQPLALEMALQKRGIVDQCCTGTCTRHQLQSYCNBring the greatest number of similar characters into the same column of the alignmentMultiple Sequence Alignmen
3、t(MSA)多序列对位排列多序列对位排列Find out which parts“do the same thing”为什么要做为什么要做MSA？用于描述一组序列之间的相似性关系，以便了解一个基因家族用于描述一组序列之间的相似性关系，以便了解一个基因家族的基本特征，寻找的基本特征，寻找motif，保守区域等。用于预测新序列的二，保守区域等。用于预测新序列的二级和三级结构，进而推测其生物学功能。级和三级结构，进而推测其生物学功能。用于描述同源序列之间的亲缘关系的远近，应用到分子进化用于描述同源序列之间的亲缘关系的远近，应用到分子进化分析中。是构建分子进化树的基础。分析中。是构建分子进化树的基础。
4、为什么要做为什么要做MSA？abcGene treeABCSpecies treeWe often assume that gene trees give us species trees为什么要做为什么要做MSA？Contig assembly怎么做怎么做MSA？动态规划算法（dynamic programming）：MSA改进算法（heuristic algorithm）：1.渐进法（progressive methods）：Clustal,T-Coffee,MUSCLE 2.迭代法（iterative methods）：PRRP,DIALIGN 3.其它算法：Partial Order
5、Algorithm、profile HMM、meta-methods(MAFFT)http:/www.ebi.ac.uk/Tools/msa/Current Opinion in Structural Biology 2006,16:368373u Clustal：目前目前应用最广泛的应用最广泛的 MSA 方法方法u 可可在线分析在线分析u 可可在本地计算机运行在本地计算机运行Clustal使用方法使用方法u 序列输入序列输入、输出、输出格式格式FASTANBRF/PIR EMBL/SWISSPROTALNGCG/MSFGCG9/RSFGDEALNNBRF/PIRGCG/MSFPHYLIPNE
6、XUSGDE/FASTAInputOutputsequence 1ATTGCAGTTCGCA sequence 2ATAGCACATCGCAsequence 3ATGCCACTCCGCChttp:/www.clustal.org/两两比对两两比对构建距离矩阵构建距离矩阵构建指导树构建指导树（guide tree）将距离最近的两条将距离最近的两条序列用动态规划的序列用动态规划的算法进行比对；算法进行比对；“渐进渐进”的加上其的加上其他的序列他的序列Clustal W/X算法基础算法基础u Clustal在线分析方法（在线分析方法（ClustalW）多序列对位排列结果多序列对位排列结果粘贴或上载序
7、列粘贴或上载序列EBI的的ClustalW分析网页分析网页 http:/www.ebi.ac.uk/Tools/msa/clustalw2/调整参数调整参数http:/www.ebi.ac.uk/Tools/msa/clustalw/help/AlignmentsResult Summary自带自带Help文件文件Using ClustalX for multiple sequence alignment by Jarno Tuimala 两种工作模式两种工作模式:Multiple Alignment Profile Alignmentu Clustal离线分析方法（离线分析方法（Clusta
8、lX）下载安装下载安装第一步：输入序列第一步：输入序列FileLoad sequences1、序列为多重、序列为多重fasta格式（可进行编格式（可进行编辑，保存为辑，保存为txt文件）文件）2、序列文件所在路径不能有空格和、序列文件所在路径不能有空格和中文字符（如放在系统桌面），否则中文字符（如放在系统桌面），否则ClustalX无法载入无法载入3、为便于识别、为便于识别每条序列，可在每条序列，可在后输入物种名后输入物种名称，并用空格和称，并用空格和其它描述内容分其它描述内容分开，如：开，如：Human gi|301129180|ref|NP_001180303.1|resistin Hom
9、o sapiens第二步：设定比对参数第二步：设定比对参数第三步：进行序列比对，得到结果第三步：进行序列比对，得到结果第四步：评价比对质量第四步：评价比对质量打开比对结果打开比对结果:1、可在、可在ClustalX中直接输出打印中直接输出打印2、可用写字板打开、可用写字板打开aln文件文件3、可将、可将aln文件以图形展示，更直观文件以图形展示，更直观更改参数、手动编辑，使之具有生物学意义更改参数、手动编辑，使之具有生物学意义u 可进一步可进一步对对排列好的序列进行修饰排列好的序列进行修饰（1）Boxshade 突出相同或相似位点突出相同或相似位点（http:/www.ch.embnet.or
10、g/software/BOX_form.html）在在EBI ClustalW结果网页结果网页复制复制序列比对结果序列比对结果在在“Boxshade”网页网页粘贴序列，在粘贴序列，在“Input sequence format”栏目栏目选择选择“ALN”，在，在“Output format”栏目栏目选择选择“RTF_new”修饰过的排列结果修饰过的排列结果在结果网页点击在结果网页点击“here is your output number 1”u 可进一步可进一步对对排列好的序列进行修饰排列好的序列进行修饰（2）ESPript 多种修饰多种修饰 功能功能，突出相同或相似位点，突出相同或相似位点在
11、在ESPript分析网页分析网页“Aligned Sequences”栏上载栏上载Alignments文文件件在在“Output layout”和和“Output file or device”栏选择栏选择修饰后的比对结果修饰后的比对结果http:/espript.ibcp.fr/ESPript/cgi-bin/ESPript.cgi在在EBI ClustalW结果网页结果网页下载下载“Alignments”(CLUSTALW format)GeneDochttp:/www.nrbsc.org/gfx/genedocFile Import 修饰排列结果修饰排列结果选择输入文件的选择输入文件的格
12、式（如格式（如ALN）u 可进一步可进一步对对排列好的序列进行修饰排列好的序列进行修饰（3）第五章第五章多序列对位排列和进化分析多序列对位排列和进化分析（II）生物信息学 2.系统发生分析（系统发生分析（Phylogenetic analysis)u 分析基因或蛋白质的进化关系分析基因或蛋白质的进化关系u 系统发生（进化）树（系统发生（进化）树（phylogenetic tree）A tree showing the evolutionary relationships among various biological species or other entities that are be
13、lieved to have a common ancestor.经典进化生物学：经典进化生物学：比较：比较：形态形态、生理结构生理结构、化石化石分子进化生物学：分子进化生物学：比较比较DNA和和蛋白质蛋白质序列序列研究系统发生的方法研究系统发生的方法Residues 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 hypothes
14、is of positional homology between bases/Amino AcidsEasyonly with substitutionsDifficultalso with indels=(A,(B,C),(D,E)Newick format节点节点Node分支分支BranchABCDE末端节点末端节点 可以是物种可以是物种，群体，或，群体，或者蛋白质、者蛋白质、DNA、RNA分子等分子等OTU祖先节点祖先节点/树根树根Root系统发生树术语系统发生树术语内部节点内部节点/分歧点分歧点该分支可能的祖先该分支可能的祖先HTUA clade（进化支进化支）is a group
15、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超度量树超度量树进化树进化树分支树分支树系统发生树术语系统发生树术语Rooted tree vs.Unrooted treetwo major
16、ways to root trees:A BCD102352d(A,D)=10+3+5=18Midpoint=18/2=9By midpoint or distance有有根根树树ACBD无无根根树树系统发生树术语系统发生树术语outgroup外群、外围支外群、外围支plantplantplantfungusanimalanimalanimalUnrooted treerootRooted treebacteriumanimalanimalanimalfungusplantplantplantMonophyletic groupMonophyleticgroupRooted tree vs.U
17、nrooted tree选择外群（Outgroup）选择一个或多个已知与分析序列关系较远的序列作为外类群外类群可以辅助定位树根外类群序列必须与进化树上其它序列同 源，但外类群序列与这些序列间的差异必须比这些序列之间的差异更显著。eukaryoteeukaryoteeukaryoteeukaryotearchaeaarchaeaarchaeabacteria outgroup外群外群How to root a tree?系统发育树构建步骤系统发育树构建步骤多序列比对（自动比对、手工校正）多序列比对（自动比对、手工校正）选择建树方法（选择建树方法（替代模型替代模型）建立进化树建立进化树进化树评估进
18、化树评估最大简约法最大简约法(maximum parsimony,MP)距离法距离法(distance)最大似然法最大似然法(maximum likelihood,ML)贝叶斯法贝叶斯法(Bayesian inference)统计分析统计分析BootstrapLikelihood Ratio Test UPGMA邻近法邻近法(Neighbor-joining,NJ)最小进化法最小进化法(minimum evolution)距离法距离法距离法又称距离矩阵法，首先通过各个序列之间的比较，根据一定的假设（进化根据一定的假设（进化距离模型）推导得出分类群之间的进化距距离模型）推导得出分类群之间的进化距
19、离，构建一个进化距离矩阵。离，构建一个进化距离矩阵。进化树的构建则是基于这个矩阵中的进化距离关系。CatDogRatDog3Rat45Cow676CatDogRat11224Cow计算序计算序列的距列的距离，建离，建立距离立距离矩阵矩阵通过通过距离距离矩阵矩阵建进建进化树化树Step1.计算序列的距离，建立距离矩阵计算序列的距离，建立距离矩阵Uncorrected“p”distance(=observed percentsequence difference)Kimura 2-parameter distance(estimate of the true number of substitut
20、ions between taxa)对位排列，对位排列，去除空格去除空格（选择替代模型）（选择替代模型）由进化距离构建进化树的方法有很多，常见有：1.Unweighted Pair Group Method with Arithmetic mean(UPGMA)2.Neighbor-Joining Method(NJ法/邻位连接法)3.Minimum Evolution(MP法/最小进化法)Step2.通过矩阵建树通过矩阵建树最大简约法（MP）最早源于形态性状研究，现在已经推广到分子序列的进化分析中。最大简约法的理论基础是奥卡姆（Ockham）哲学原则，对所有可能对所有可能的拓扑结构进行计算，
21、找出所需替代数的拓扑结构进行计算，找出所需替代数最小的那个拓扑结构，作为最优树。最小的那个拓扑结构，作为最优树。最大简约法(Maximum Parsimony)Find the tree that explains the observed sequences with a minimal number of substitutionsSequence1T G CSequence2T A CSequence3A G GSequence4A A G1 2 3PositionMP法建树流程法建树流程If 1 and 2 are grouped a total of four changes are
22、 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 changes456BESTMP法建树步骤法建树步骤最大似然法(Maximum
23、Likelihood)最大似然法(ML)最早应用于对基因频率数据的分析上。其原理为选取一个特定的替代模型来分析给定的一组序列数据，使得获得的每一个拓扑结构的似然率都为最大值，然后再挑出其中似然率最大的拓扑结构作为最优树。ML法建法建树流程树流程CAGATGCCATGC Pick an Evolutionary Model For each position,Generate all possible tree structures Based on the Evolutionary Model,calculate Likelihood of these Trees and Sum them t
24、o get the Column Likelihood for each OTU cluster.Calculate Tree Likelihood by multiplying the likelihood for each position Choose Tree with Greatest LikelihoodInferring the maximum likelihood treeHolder&Lewis(2003)Nature Reviews Genetics 4,275-284 Bayesian inference:What is the probability that the
25、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的优势：Comparison of MethodsDistanceMaximum parsimonyMaxim
26、um 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
27、 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 methodsBioinformatics:Sequence and Genome Analysis,2nd edition,b
28、y 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 Assessing tree reliabilityPhylogenetic reconstruction is a problem of statistical inference.One must assess the reliabilit
29、y 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?A statistical technique that uses intensive random resampling of data to estimate a statistic whose underlying distr
30、ibution is unknown.评估进化树的可靠性评估进化树的可靠性自展法自展法（bootstrapping method）从排列的多序列中随机有放回的抽取某一列，构成相同长度的新的排列序列重复上面的过程，得到多组新的序列对这些新的序列进行建树，再观察这些树与原始树是否有差异，以此评价建树的可靠性The Bootstrap Computational method to estimate the confidence level of a certain phylogenetic tree.ratGAGGCTTATChumanGTGGCTTATCturtleGTGCCCTATGfruit
31、fly CTCGCCTTTGoakATCGCTCTTGduckweed ATCCCTCCGG0123456789Samplerathumanturtlefruit flyoakduckweedInferred treeMore replicates(between 100-1000)ratGGAAGGGGCThumanGGTTGGGGCTturtleGGTTGGGCCCfruitfly CCTTCCCGCCoakAATTCCCGCTduckweed AATTCCCCCT0011222345Pseudo sample 1ratCCTTTTAAAThumanCCTTTTAAATturtleCCCC
32、CTAAATfruitfly CCCCCTTTTToakCCTTTCTTTTduckweed CCTTTCCCCG4455567778Pseudo sample 2自展法检验流程自展法检验流程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-552MSA程序可对任何序列进行比对，选择程序可对任何序列进行
33、比对，选择什么样的序列进行比对非常重要！什么样的序列进行比对非常重要！用于构建进化树的序列必须是同源序列用于构建进化树的序列必须是同源序列MSA是构建分子进化树的关键步骤是构建分子进化树的关键步骤u 分子进化树构建（分子进化树构建（ClustalW）页面下方页面下方 显示显示Cladogram Tree点击点击“Show as Phylogram Tree”展示展示Phylogram Tree不推荐：仅提供距离法建树，且没有进行评估不推荐：仅提供距离法建树，且没有进行评估输入比对后的序列（或上载输入比对后的序列（或上载Alignments文件）文件）EBI的的ClustalW2-phyloge
34、ny分析网页分析网页http:/www.ebi.ac.uk/Tools/phylogeny/clustalw2_phylogeny/u 看图工具看图工具下载下载“Phylip tree file”（ph文件文件）TreeView 进化树编辑打印软件进化树编辑打印软件（在在http:/taxonomy.zoology.gla.ac.uk/rod/treeview.html）输入比对后的序列（或上载输入比对后的序列（或上载Alignments文件）文件）用用TreeView软件打开上述文件软件打开上述文件可以不同格式展示进化树（可以不同格式展示进化树（1、2、3）EBI的的ClustalW2-ph
35、ylogeny分析网页分析网页PHYLIP 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
36、.csit.fsu.edu/基于贝叶斯方法的建树工具分子进化分析软件分子进化分析软件更多工具更多工具http:/evolution.gs.washington.edu/phylip/software.html提供最大简约法（MP）、最大似然法（ML）和距离法三种建树方法。其中距离法包括邻接法（NJ）、最小进化法（ME）和UPGMA三种算法。u 分子进化树构建方法分子进化树构建方法 Pig gi|218855168|gb|ACL12051.1|FAD24 pr Cattle gi|146186885|gb|AAI40653.1|NOC3L Human gi|18389433|dbj|BAB841
37、94.1|AD24 H Mouse gi|18389431|dbj|BAB84193.1|AD24 M Chicken gi|118092837|ref|XP 421670.2|PR Zebrafish gi|50838808|ref|NP 001002863.192981000.02优点：优点：图形界面，集序列查询、比对、进化树构建为一体，帮助文件详尽，免费http:/ Clustal工作界面工作界面Clustal部分参数定义部分参数定义 Gap opening penalty：增大数值使 gap 数目减少 Gap extension penalty：增大数值使 gap 长度变短 Weigh
38、t transition：AG 转换或 CT 转换（multiple DNA sequence alignment）Hydrophilic gap：选择“on”将增加形成 gap 的机会（multiple protein sequence alignment）Residue-specific gap penalties：选择“on”将增加在某些氨基酸残基处形成 gap 的机会，而减少在另一些氨基酸残基处形成 gap 的机会（multiple protein sequence alignment）http:/espript.ibcp.fr/ESPript/cgi-bin/ESPript.cgiB
39、uffon(1707-1788)Natural History of Animals 始祖鸟化石始祖鸟化石复原图复原图2.7%differencexl,Xenopus laevis;xt,Xenopus tropicalis;gg,Gallus gallus;rn,Rattus norvegicus;mm,Mus musculus;hs,Homo sapiens.BMC Evolutionary Biology 2007 7:164 由于同一位点多重替代（multiple substitution）的发生，观测到的差异比实际替代数要小原原始始序序列列后后代代序序列列13 mutations =3 differencesDegree of divergenceTotal number of substitutions为了估算出正确的分歧时间（期望替代数），必须对观测到的替代数进行校正在进化的任意时间点，任意位点的核苷酸都可能发生回复和平行突变。替代模型替代模型Substitution model替代模型替代模型
