生物信息学概论第五章基于特征的系统发生分析

第五章:基于特征的系统发生分析本章内容•简约法•信息位点与非信息位点——特征数据•无权简约法与加权简约法——算法•推断出祖先序列•一致树•树的置信度•各种系统发生分析方法的比较•分子系统发生分析•基于距离的方法“着眼于大的全景”，却忽略了许多潜在的有用信息。所有这些有用的信息是遗传分类学家关注的焦点，并且引起了挑战性的（但是能解决的）计算问题，这些问题引起了很多程序员的兴趣•因为基于距离的方法和基于特征的方法所采用的分析有着本质上的区别，所以它们关于进化关系结论的一致性可以看作是对一棵系统发生树的正确性的积极认可。•分子系统发生分析主要分成三个步骤：（1）分子序列或特征数据的分析；（2）系统发生树的构造；（3）结果的检验。•其中，第一步的作用是通过分析，产生距离或特征数据，为建立系统发生树提供依据。数据系统发生树检验生物体信息位点简约法树的置信度•构成系统发生树的分子数据：特征数据基于特征的系统发生分析距离数据基于距离的系统发生分析5.1简约法•简约法的概念是所有基于特征的系统发生树重建方法的核心•在生物学中，描述按照进化途径中突变事件最少的标准来优先选择一个进化途径的过程。•两个简单假设：（1）突变是罕见事件；（2）一个模型引发了越不合理的事件，这个模型就越不可能是正确的。因此，突变最少的进化关系就越有可能是物种之间真实的进化关系。5.1.1信息位点和非信息位点根据信息的信息内容可以两类：•信息位点(informative):含有信息的位点信息位点就是指能由位点产生的突变数目把一棵树与其它树区分开来的位点;•非信息位点(uninformative):不含有信息的位点–不变位点(invariant):属于非信息位点，比较的所有序列都有同样的核苷酸。即每一棵描述所有序列间进化关系的树都有相同的突变数目(0)。4个物种三种可能的无根树1234132414231GG2GGG3G4((1,2)(3,4))1GG3GGG2G4((1,3)(2,4))1GG4GGG2G3((1,4)(2,3))序列位点1位点2位点3位点4位点5位点61GGGGGG2GGGAGT3GGATAG4GATCAT图5.14条同源序列的比对（每条序列有6个核苷酸）6个位点构造4个物种之间进化关系的可能无根树不变位点序列位点1位点2位点3位点4位点5位点61GGGGGG2GGGAGT3GGATAG4GATCAT1GG2GGG3A4((1,2)(3,4))1GG3GGG2A4((1,3)(2,4))1GG4AGG2G3((1,4)(2,3))不变位点非信息位点序列位点1位点2位点3位点4位点5位点61GGGGGG2GGGAGT3GGATAG4GATCAT不变位点非信息位点非信息位点1GG2GAA3T4((1,2)(3,4))1GG3AGG2T4((1,3)(2,4))((1,4)(2,3))1GG4TGG2A3序列位点1位点2位点3位点4位点5位点61GGGGGG2GGGAGT3GGATAG4GATCAT不变位点非信息位点非信息位点非信息位点1GG2ATT3C4((1,2)(3,4))1GG3TAA2C4((1,3)(2,4))1GG4CAA2T3((1,4)(2,3))序列位点1位点2位点3位点4位点5位点61GGGGGG2GGGAGT3GGATAG4GATCAT不变位点非信息位点非信息位点非信息位点信息位点1GG2GAA3A4((1,2)(3,4))1GG3AGG2A4((1,3)(2,4))1GG4AGG2A3((1,4)(2,3))序列位点1位点2位点3位点4位点5位点61GGGGGG2GGGAGT3GGATAG4GATCAT不变位点非信息位点非信息位点非信息位点信息位点信息位点1GG2TGG3T4((1,2)(3,4))1GG4TGT2G3((1,4)(2,3))1GG3GGT2T4((1,3)(2,4))T•信息位点的共同特征：如果一个位点是信息位点，那么它(1)至少有两种不同的核苷酸，并且(2)这些核苷酸至少出现两次。5.1.2无权简约法无权简约法信息位点最简约树5.1.2无权简约法•最简约树：考虑每个信息位点所有可能的树，分别给每棵树进行打分，统计每个位点的核苷酸最小替换数目。所有简约信息位点最小核苷酸替换数的总和最小的树记为最简约树。信息位点1信息位点2信息位点3信息位点4信息位点5信息位点6…信息位点N总和树15158346…1099树2932687…5134…………………………树N1266928…8187•4条序列比对的例子可能是最简单的例子：在只包含4条序列的分析中，每个信息位点只能支持3棵可能的树中的1棵，含有最多信息位点的树就是最简约树。信息位点1信息位点2信息位点3信息位点4信息位点5信息位点6…信息位点N总和树1√XXXXX…X99树2X√XX√X…√34树3XX√XX√…X87•5条或更多序列数据集的计算复杂得多。原因在于：⑴随序列数增加，无根树数目也增加；⑵每个信息位点可能有多棵树（而四条序列分析中，只有一棵），整个数据集的最简约树不一定是含最多信息位点的树；⑶每棵树的核苷酸替换数目的计算更加困难。•n个物种可能得到无根系统发生树(Nu)数目：Nu=(2n-5)!/2n-3(n-3)!下图是描述5条不同序列之间关系的3棵有根数。这3棵有根树有相同的简约度，它们的最小替换数都是2。由简约规则，推断出的祖先的候选核苷酸分别列在每个内部节点的旁边。T512346789GGAAGA(GA)(GAT)(a)A123456789GGTAGA(GT)(GTA)(b)123456789GTGAAGGA(GA)(c)计算祖先核苷酸位置的算法：如果一个内部节点的两个直接后代节点上的核苷酸的交集非空，那么这个节点的最可能的候选核苷酸集就是这个交集；否则为它的两个后代节点上的核苷酸集的并集。•上述方法只适用于信息位点，不适用于非信息位点。•非信息位点的最小替换数：外部节点上不同核苷酸数目减去1(与树的拓扑结构无关)•例如：5条序列的比对中，有一个位置上的核苷酸是G、G、A、G和T，则最小替换数就是3-1=2。•非信息位点对所有可能的树的贡献都是等价的，在简约分析中往往被完全排除。•树的长度（length）：当一棵树在信息位点和非信息位点的替换数的总和是一个确定的数值时，这个数值就是指树的长度。5.1.3加权简约法•赋值的必要性：“突变是罕见事件”将所有突变看成是等价的，但之前的学习已经告诉我们插入和删除比替换可能性小；长插入和长删除比短插入和短删除少见；转换概率大于颠换；功能相关的突变比无关的突变发生的概率小……•因此，我们给各种突变赋予相对概率值，在简约算法中可将这些值转化为权值。我们无法得到一组适用于所有数据集的权值，原因有三：（1）一些序列比其他序列更容易插入和删除；（2）即使是同源基因，对功能的重要性也因不同的基因、不同的物种而有所差别；（3）不同的基因和物种有不同的替换偏好。因此，最佳的权值通常来自对实验数据集的分析，可获得的最佳实验数据集是实际分析过的数据集。例如：假如转换出现频率为颠换的3倍，那么对同一序列集的简约分析就可以给所有的转换替换赋权值1，给所有的颠换替换赋权值0.33。5.2推断出的祖先序列•简约法最值得注意的副产品是分析过程中产生的推断出的祖先序列，即使这些祖先可能在数亿年前就已经灭绝。–哪怕图5.1中序列1和序列2的共同祖先可能在数亿年以前就已经灭绝，简约法也能够相当准确地推断出其序列第5个位置上的核苷酸是‘G’–对于单个核苷酸，这可能是微不足道的，但是对于整个基因或基因组来说，它对了解进化过程的作用是不可替代的•推断出的树中的内部分支的信息位点称作共源性状（synapomorphies,几个物种共有的遗传状态）。•其他信息位点称作同形性状（homoplasies,），它是通过趋同进化、平行进化和逆转进化，由物种独立发展出来的特征，而不是从共同祖先遗传得到的。哺乳动物啮齿动物•例如同形性状共源性状•应用进化论对创世论的反驳利用简约分析推断出祖先，不仅填补了分子进化研究中空白，还能从现存后代序列中推断出中间状态；5.3快速搜索策略•即使信息位点的数目较少，用未改进的简约法对较多序列的比对进行手工计算也是不现实。分析10条序列需要考虑200万棵树。•由于数据集十分庞大，计算困难，因此研究出一些改进的算法，不用考虑所有可能的树就能够方便可靠地确定最简约树。–分支约束法–启发式搜索5.3.1分支约束法分支约束法（BranchandBoundMethod）–Hardy和Penny于1982年提出。–Branch——分支–Bound——边界、约束步骤：⑴为最简约树的长度确定一个上限L。L的值可以是随机选择的任何一棵描述被研究物种之间关系的树的长度。但是如果用近似最简约的树（例如UPGMA产生的树）来建立上限更有效。⑵树的生长过程，即在描述部分序列之间关系的树中每次增加一个分支。这个方法的原理是：①由数据子集得到的任何一棵树，如果它的替换数大于L，那么当剩下的序列加入后，总的分支长度必定变得更大，那么原先的长度为L的树为最简约树。•换而言之，最简约树不可能是包含上述特定分支模式的树②如果在分析过程中，如果发现比初始建立的上限为L的树替换数更少的树，那么L的值将随之修正，这样余下的数据集的分析将更为有效。分支约束法搜索最简约树的过程•表示3个物种(A,B,C)之间关系的无根树只有1棵(A1);•用这棵树作为起始点，将第4个物种(D)插入到树A1中，得到四个物种的3种无根树(B1,B2,B3);•如果插入后得到的树的长度大于原来的树，例如B3，舍弃该树。•继续插入第5个物种，重复上述步骤，直到所有待分析物种都被插入到树中。下图是用分支约束法搜索简约树的过程BACA1STOPABCDB3ABCDB2ABCDB1ABCDEABCDEABCDEABCDEABCDEABCDEABCDEABCDEABCDEABCDEC2.1C2.2C2.3C2.4C2.5STOPSTOPSTOPSTOPSTOPC1.1C1.2C1.3C1.4C1.5图5.4用分支约束法搜索最简约树的过程分支约束法快速搜索策略的优缺点优点：•分支约束法保证在分析完成时没有遗漏更简约的树，具有比穷举法搜索快几个数量级的优点；能分析多达20条序列。缺点：•对于多于1×1021可能的无根树的分析，计算量还是太大。5.3.2启发式搜索•对大于20条序列的多序列进行比对必须采用近似的更为有效的算法。它并不一定总能找到最简约的树。•启发式(heuristic)方法的假设：各个可能的树并不总是相互独立的。•最简约数和次简约数拓扑结构相似，因此首先构建一棵初始树，从它开始寻找更短的树。•因此启发式搜索通过子树分支交换，把它们嫁接到该步分析中找到的最好的那棵树的其他位置上，从而产生一棵拓扑结构和初始树相似的树。•同分支约束法一样，如果初始树很接近于最简约树（例如UPGMA产生的树），启发式搜索会更有效。图5.5分支交换再接1234567剪除1245673•第一轮分析中，由初始树产生出上百棵新树，其中所有比初始树短的新树都在第二轮分析中被剪枝和嫁接。不断重复这个过程，直到某一轮通过剪枝和嫁接无法产生与前一轮等长或更短的树。•大量序列比对的可能的无根树的数目是一个天文数字，这种比对深度对计算造成了很大困难，把多个序列比对分成几个较少序列的比对可以较好的解决这一问题。例如：同源哺乳动物序列灵长类序列啮齿类序列部分偶蹄、兔类、灵长、啮齿探知树中灵长类所在树干的末段之间的关系确定树中啮齿类所在树干的末段之间的关系检验更早的分支、更具体的灵长类树干和啮齿类树干的最后位置5.4一致树•简约法产生多棵等价的简约数是很常见的。•此时最简单的方法是用一个一致树(consensustree)作为代表来概括所有等价的简约树。方法如下：（1）在所有树中都一致的分支点在一致树中表示成二叉分支点。（2）不一致的分支点蜕变成连接三个或更多后代分支的内部节点。严格一致树(strictconsensustree)：只要