如何建树

MakingTreeEasyJob常用的建树方法建树五步曲常用的软件AlarChung@2002.2.15如何检验你的树多学一点理论常用的建树方法常用的建树方法分为两大类，一类是基于距离的方法（distance-based)，这类方法的代表是邻接法(NJ)和UPGMA法；另一类是基于性状性质的方法(character-based)，这类方法的代表是最大简约法(MP)和极大似然法(ML)。距离法速度很快，能够分析大量的数据，但由于所有的数据均被抽象为距离，这过程中不可避免的产生了信息量的损失，从一定意义上来说，得到的结果并不能反映真实的情况，但近年来距离法已经有了很大的改进，在大多数情况下它都能给出比较准确的结果，而且由于速度快，所以应用很广。性状法分析的对象是序列中的各个位点(site)，在分析过程中信息量没有损失，从这个意义上说它能比距离法得出更加真实的结果。但性状法的一个缺陷就是它的分析过程是建立在一个进化模型上的，这个模型的好坏，直接影响到所得结果的正确性。我们知道，生物的进化是一个极其复杂的过程，一个人为的模型很难能完全反映真实的进化过程。近年来各种模型不断出现，老的模型也不断发展，使的得到的结果能更真实的反映进化关系。性状法较之距离法由于考虑的因素更多，处理的信息更大，所以在速度上也会更慢一些。MP，ML，NJ，哪种方法更好？这个不能一概而论。MP法在处理近缘物种时效果很好，但在处理分歧年代比较久远的物种时表现不太好，因为在序列中存在着许多回复突变，这种系统误差目前还没有太多的解决办法。ML法无论在处理分歧年代久远的物种还是近缘物种时表现都不错，但速度太慢，不容易对生成的结果进行检验。如果可能的话，尽量采用这种方法。NJ法在处理近缘关系物种时并不太适合，因为它们之间的差异比较小。在处理分歧年代久远的物种间和进化很快且分子钟不恒定的物种间的关系时（如各种细菌），它的表现要比MP法好。而且由于速度快，能对生成的结果进行各种检验，增加结果的可靠性。Tips:一般来说，NJ法的结果会与ML法的结果更近一些！多学一些PhylogeneticTree的理论RYXZABCDE11117232nodebranchABCDE五个末端节点代表着这棵系统树的五个物种（taxa），XYZR这四个内部节点代表了祖先（ancestraltaxa)。当然这样的祖先很可能已经灭绝，是人为假设的。枝上标注的数字表示两个节点之间发生的变化数目。这个数字可以代表枝长，但并不是所有的情况下都是这样。如果两个节点间的的距离（变换数）等于这两个节点间所有枝长的总和，则我们说这棵树具有可加性(additive)。并不是所有的树都具有可加性，如果在两个节点间的进化过程中，一些位点变化了两次又回到了起始状态（如A–G–A)，那么它们间所观察到的变化数就会比实际的枝长要小，这样的树就不具有可加性。何为有根树（Rooted)和无根树（Unrooted)?ABCDABCDRootedUnrooted如果在一棵树中存在一个节点，从这个节点出发，可以向同一方向访问所有的其它节点，我们就说这棵树是有根的，而根就是那个特殊的节点。注：对于给定数量的物种，无根树的数目总是比有根树少对于给定的物种数，有根树和无根树有多少?ABCDACBDADBC(1)(2)(3)对于四个物种，只有如图所示的三种无根树，而有根树则有15种。当物种数增加时，无根树和有根树的数目会以惊人的速度增加计算的公式如下UnrootedRooted(2s-5)!2s-3(s-3)!(2s-3)!2s-2(s-2)!Note:当给定的物种数为100个时，得到的无根树的数目会超过整个宇宙的原子数的总和！它们是一样的树吗?ABCDBACDABCDBCDA(1)(2)能正确区分一棵树和它表现的形式，这一点是非常重要的。在上图中，第一个例子中的两棵树虽然表现形式不同，但它们都是一样的，完全没有任何差别；第二个例子比起第一个例子看起来更让人容易混淆，但这两种树还是一样的，没有任何区别。注意：对于一棵phylogenetictree，我们更注重的是它的分枝情况，即topology，而枝长往往并不是那么重要。树搜索的基本策略123A123B1123B2123B3444123C1145123C1245123C1354123C1454153C1524树搜索的基本策略(续)1、exhaustiveSearch:搜索所有的树，选出最优树。2、branchandbound:先生成一个随机树，而后搜索时以该树为标准，如果发现更好的树则标准变化，当一个阶（level)上的值较标准差时，则它以后的所有树都不会被考虑，这样就节省了时间。3、stepwiseaddition:这种搜索在每一阶（level)上都计算各棵树的值，只有值最好的树才会被用于产生下一阶。这种方法并不能保证所生成的树是最优树，但速度快。4、branchswapping:这种方法在搜索的过程中有枝的交换（swapping）和重排，具体过程比较复杂。后两种被称为heuristicsearch，这种算法不能保证找到最优树，但在速度与准确度方面作出了平衡，所以被广泛采用。一般来说，branchswapping策略用的比较多。DistanceMethods简介基于distance的方法所分析的数据并不是序列alignment本身，而是由这些alignment中所派生出来的一种距离矩阵，简单的来说这种矩阵更像一种相似百分比（homology%)的表格，但实际上并不是那么简单。我们很容易理解，一个与目标只有10%差异的序列当然会比一个差了30%的与目标更有关系。也很容易想像两个由共同祖先派生出来的序列，但们所经过的时间越长，则它们之间的差异也越大。但这种假设也可能会有不妥的地方，因为有可能由相同祖先派生出来的一个种系进化的比另一个种系快，或者就算它们进化的一样快，如果在同一位点上发生了多次突变，这样所观察到的差异也不能代表它们之间的分歧。举例来说，如果在一个位点上祖先是A，一个种系还是A，没有发生变化，而另一个种系由A－C而后又变回A，那么这两种系之间并没有观察到差异，但事实上它们之间还是存在着差异的。由于我们所研究的序列往往不是太长，在长期的进化过程中，这些序列中的许多位点很可能发生了多次突变，但我们由序列所观察到的差异无法反映这种差异，序列之间的差异在距离法中往往都被低估了！现在距离法中计算距离时，并不是简单的计算两个序列之间的差异百分比，而是有着多种的模式。最常用的KimuraTwoParameters距离算法的基本思路就是，转换与颠换发生的频率是不一样的，由A－G要比由A－C更容易一些，则在计算距离时，颠换所产生的差异就要比转换要高。当然还有许多计算距离的算法和模式，在这里就不一一介绍了！NeighborJoining(NJ)法简介NJ法又称邻接法，是距离法中应用最广的一种方法。它的具体分析过程可以描述成这样：NetdivergenceOriginalMatrixCorrectedMatrixFindthetwotaxawiththelowestdivergencescoreCalculatethedistancefromeachofthosetaxatothenodethatjointhemFromnewmatrix(leveldecreaseby1)level=1?NYENDMaximumParsimony(MP)法简介MP法假设，最有可能的树能以最少的变化数来解释alignment中的数据，这与自然界中许多事物都走捷径的常理一致，比如光走的是直线，这样它所经过的距离最短。简而言之，MP法所找到的树使由一个共同祖先进化到多个子系所需的进化步数最少。在一个alignment中，每一位点(site）称为一个character；在一个character上，不同物种可以拥用不同的状态。这样就引出了一个新的概念－－信息位点(informativesite)。在一个alignment中，并不是所有的character都是informativesite。很显然，如果在一个character中，所有的物种都具有相同的状态，那么这样的character并不是informativesite。另外，如果一种状态只在一个物种中出现，那么这样的character也不是信息位点。1=A2=A3=A4=A5=A6=A1=A2=C3=G4=T5=A6=A1=A2=C3=A4=C5=A6=A全部一样C只在2中出现G只在3中出现T只在4中出现MaximumParsimony(MP)法简介(续)MP法究竟是如何寻找最优树的呢？下面通过一个简单的例子来加以说明：假定在一个只含有六个物种的Alignment中，其中一个信息位点的状态如下：1=A2=C3=A4=G5=G6=C105棵无根树2C3A6C5G1A4G其中一棵1A2C3A4G5G6CWXYZ以Taxon1为根MaximumParsimony(MP)法简介(续)从上图可以看到，节点WXYZ的状态是不确定的，但由简约法的原则我们可以做出以下推导：1A2C3A4G5G6CWXYZ1A2C3A4G5G6CAorGGorCGGorCMaximumParsimony(MP)法简介(续)1A2C3A4G5G6CGGGC如果将不确定的节点ZXW分别确定为CGG，那么得到的结果如上图左。在这幅图中，进化中产生分化的过程用红粗线标注。可以看到，这棵树只用了4个变化就完成了进化过程。1A2C3A4G5G6CAGGC如果将不确定的节点ZXW分别确定为CGA，那么得到的结果如上图右。在这幅图中，进化中产生分化的过程用红粗线标注。可以看到，这棵树要用5个变化才能完成进化过程。MP法会计算每一棵有根树所需的最小进化步骤，从中选出最简约的一棵树来。当然，这里所说中只是一个信息位点，MP法建树时会将所有的信息位点进行加权，从中选出最优树。MaximumLikelihood(ML)法简介极大似然法搜索最优树的基本出发点是树具有从数据集观察得出的最大可能性。举例来说：在一个数据集中(Alignment)，四个物种分别具有以下的状态：1=C2=T3=T4=GCTTGXY共有3棵无根树我们从可能的3棵无根树中任意选一个出来说说ML是如何工作的。如果我们的进化模型是时间可逆的，那么我们可以将根定在任意的节点上。如果我们将根置于X上，那么我们可以得到一棵有根树(见下页)Figure1MaximumLikelihood(ML)法简介(续)XYGCTT我们并不知道节点XY的状态，但由于X上可能有4种状态，Y上也可能有4种状态，所以有可能有16种状态可以生成Figure2的树，我们从中选择1种可能加以讲解。ATGCTTFigure2Figure3Figure3这种状态出现的概率可以由以下公式计算得出：PFig3=PA*PAG*PAC*PAT*PTT*PTT其中PA可以是1/4，也可以是A在序列中出现的频率，这要看进化模型。由根的状态A到枝末端G状态的可能性也可以由进化模型的矩阵表中计算得出。其余的枝的进化概率也能以这样的方式计算出来。由于有16种状态可以生成Figure2，所以Figure2的概率为PFig2=PFig3+PFig4+……+PSCENARIO16MaximumLikelihood(ML)法简介(续)很容易想到，PFig2只是由观察一个位点所得到的可能性，那么这棵树对于全部位点具有的可能性必须一一加以计算，最终的概率为Ptree=PiNi=1由于这个值常常小到一般的计算机无法处理，所以一棵树的概率(likelihood)常常表示为一种对数形式，即loglikelihood：lnLi，这样，复杂的乘法就可以很容易的变为加法：lnLtree=lnLi∑Ni=1可以想像，ML法对要对所有的有根树一一进行lnlikelihood值的计算，并从中选出最大可能性的树。对于一个有超过30个牧种和上千个性状的数据集来说，这样的计算量就算对许多超级计算机来说，也是不可实现的。为此，人们对ML法做了许多