1、Axon第第5 5章章 系统发生分析系统发生分析 Charles Darwin(1809-1882)第第1节节 系统发生与系统发生树系统发生与系统发生树 基本概念基本概念：4系统发生（phylogeny）是指生物形成或进化的历史4系统发生学(phylogenetics)研究物种之间的进化关系 4系统发生树（phylogenetic tree）表示形式，描述物种之间进化关系 WilliWilli HennigHennig(19131913-1976)系统发生学（分支学）创始人 经典系统发生学主要是物理或表型特征如生物体的大小、颜色、触角个数 现代系统发生学利用从遗传物质中提取的信息作为物种特征具
2、体地说就是核酸序列或蛋白质分子 关于现代人起源的研究:线粒体DNA所有现代人都是一个非洲女性的后代 分类单元（物种或序列）物种之间的进化关系 系统发生树性质：（1）如果是一棵有根树，则树根代表在进化历史上是最早的、并且与其它所有分类单元都有联系的分类单元；（2）如果找不到可以作为树根的单元，则系统发生树是无根树；（3）从根节点出发到任何一个节点的路径指明进化时间或者进化距离。4对于给定的分类单元数，有很多棵可能的系统发生树，但是只有一棵树是正确的。系统发生分析的目标寻找这棵正确的树、系统发生分析步骤（1）序列比对（2）确定替换模型（3）构建系统发生树（4）评价所建立的树4计算序列之间距离 令S
3、(i,j)是序列i和序列j比对位置得分的加权和),(),(),(),(1),(maxjiSjiSjiSjiSjidrr归一化的距离：其中Sr(i,j)是序列i和j随机化之后的比对得分的加权和，Smax(i,j)是可能的最大值令Sr(i,j)=0 为了适合于处理相似性较小的序列，可以进一步修改距离计算公式),(),(1),(maxjiSjiSjid),(),(ln),(maxjiSjiSjid4两类数据：距离距离离散特征离散特征 离散特征数据可分为 二态特征例如：DNA序列上的某个位置如果是剪切位点 多态特征例如：某一位置可能的碱基有、或 4系统发生树的构建方法分为两大类：基于距离的构建方法非加
4、权组平均法 邻近归并法 Fitch-Margoliash法 最小进化方法 基于离散特征的构建方法最大简约法 最大似然法 进化简约法 相容性方法 4根据建树算法在执行过程中采用的搜索方式，系统发生树的构建方法也可以分为以下3类。（1）穷尽搜索方法 即产生所有可能的树，然后根据评价标准选择一棵最优的树。（2）分支约束方法 即根据一定的约束条件将搜索空间限制在一定范围内，产生可能的树，然后择优。（3）启发式或经验性方法 根据先验知识或一定的指导性规则压缩搜索空间，提高计算速度。第2节 基于距离的系统发生树构建方法基于距离的系统发生树构建方法4基本思路是：给定一种序列之间距离的测度，在该距离测度下构建
5、一棵系统发生树，使得该树能够最好地反映已知序列之间的距离。10条核酸序列的距离矩阵 例，如果有三个物种，其两两距离如下：dab=0.08 dac =0.45 dbc=0.43通过求解方程，得到如图6.2所示的一棵树。1、最小二乘法4目标是构造一棵树T，该树的叶节点代表物种，用该树预测物种之间的距离。通过优化，使下式最小化：这里，Dij为物种i和j的实际观察距离（或序列之间的计算距离），dij是物种i和j在系统发生树T 中的距离，Wij是与物种i和j相关的权值。SSQ（T）是树T所有预测值与实际观察值偏差的累加和。权值Wij一般为1，或 Wij=1/Dij2niijijijijdDWTSSQ12
6、)()(2、连锁聚类方法选择距离最小的一对序列将这两个序列合二为一，形成一个新的对象（代表这两个序列的祖先）重新计算这个新的对象与其它序列的距离。单连锁聚类:d(x,u)=min(d(y,u),d(z,u)最大连锁聚类：d(x,u)=max(d(y,u),d(z,u)平均连锁聚类：d(x,u)=1/2(d(y,u)+d(z,u)其中x代表y和z的合并，u代表任意其它对象。3、非加权分组平均法（Unweighted Pair Group Method with Arithmetic mean,UPGMA）在平均连锁聚类过程中，一个新类到其它类之在平均连锁聚类过程中，一个新类到其它类之间的距离就是
7、简单的原距离平均值间的距离就是简单的原距离平均值。如果类中分类单元个数不一样，原距离矩阵中各个如果类中分类单元个数不一样，原距离矩阵中各个距离值对新距离计算的贡献就不一样，或者说是经过距离值对新距离计算的贡献就不一样，或者说是经过“加权加权”的，称这样的聚类为加权分组平均。的，称这样的聚类为加权分组平均。在非加权分组平均法中，在计算新分类到其它分类在非加权分组平均法中，在计算新分类到其它分类之间的平均距离时按照各分类中分类单元的数目进行之间的平均距离时按照各分类中分类单元的数目进行加权处理。加权处理。UPGMA算法的执行过程如下：(1)初始化：使每个物种自成一类，如果有n个物种，则开始时共有n
8、个类，每个类的大小为1，分别用n个叶节点代表每个类；(2)执行下列循环：l 寻找具有最小距离Dij的两个类i、j；建立一个新的聚类（ij)l 连接i和j形成新节点(ij)，生长两个新的分支，将i 和j 连接到(ij)，分支的长度为Dij/2；l 计算新分类到其它类的距离其中ni、nj、(ni+nj)分别为i类、j类、(ij)类的元素个数；l 在距离矩阵中删除与类i和类j相应的行和列，为类(ij)加入新的行和列；重复循环，直到仅剩一个类为止。重复循环，直到仅剩一个类为止。kjjijkijiikijDnnnDnnnD,),()()(4、邻近归并法 基本思想：在进行类的合并时，不仅要求待合并的类是相
9、近的，同时还要求待合并的类远离其它的类。重建时将距离最小的两个叶节点连接起来，合并这两个叶节点所代表的分类，形成一个新的分类。在树中增加一个父节点，并在距离矩阵中加入新的分类，同时删除原来的两个分类。重复上一次循环,直到只剩一个类为止。在每一次的循环中，在树中寻找两个物种的直接祖先。对于节点i，到其它节点的距离ui 按下式进行估算：ui=ki(Dik/(n-2)这里Dik是分类i和分类 k之间的距离选择Dij-ui-uj最小的一对节点i 和节点j 进行归并4算法如下：（1）初始化（与UPGMA一样）（2）循环 对于所有的分类单元i，计算ui=kI (Dik/(n-2)；选择一对分类单元i 和j
10、，使Dij-ui-uj最小；将i和j归并为新的类(ij)，在树中添加一个新的节点，代表新生成的分类，计算从i和j到新节点的分支长度；di,(ij）=1/2Di,j+1/2(ui-uj),dj,(ij）=1/2Di,j+1/2(uj-ui)计算新类与其它类的距离；D(ij）,k=1/2(Di,k+Dj,k-Di,j)删除聚类i和j，添加新类(ij)；如果有两个以上的分类存在，则继续执行循环；否则用长度为Di,j的分支连接剩余的两个类。图6.7 利用邻近归并算法构造的系统发生树图6.8 利用邻近归并算法构造的系统发生树第第3节节 基于特征的系统发生树构建方法基于特征的系统发生树构建方法4一般问题：
11、给定n个物种 m个用以描述物种的特征 每个物种所对应的特征值构建一棵系统发生树，使得某个目标函数最大。4输入一般为nm的特征矩阵M4在构建系统发生树假设特征是相互独立的，即一个特征的变化不影响另一个特征。4另外，还假设在进化过程中，两个物种分叉后独立进化，互不影响。1、最大简约法目标：构造一棵反映分类单元之间最小变化的系统发生树。所谓简约就是使代价最小。对于系统发生树最直观的代价计算就是沿着各个分支累加特征变化的数目。甲 乙 丙 丁 戊 节点1 节点3 节点2 根节点最大简约法的处理过程：（1）针对待比较的物种，选择核酸或蛋白质序列。有些分子比其它分子变化慢，适合于进行距离分析，例如哺乳类的线
12、粒体DNA、管家蛋白质等；（2）比较各个序列，产生序列的多重比对，确定各个序列符号的相对位置；（3）根据每个序列比对的位置（即多重对比排列的每一列），确定相应的系统发生树，该树用最少的进化动作产生序列的差异，最终生成完整的树。对于一棵系统发生树T 假设树中的节点用V(T)表示，树的边用E(T)，以uj、vj分别表示节点u和v的第j个特征，则树T的代价为：)(),(|)(TEvujjuvjTS单特征Fitch算法：首先对于每个待分析的物种，分配一个叶节点v，其值vc取对应物种的特征值。然后执行下面两步：(1)给每个节点v赋予一个集合Sv：如果v是叶节点，则Sv=vc；如果v是内部节点，并且u、w
13、是其子节点，如果SuSw，则Sv=SuSw；否则 S(v)=SuSw。这个过程是从叶节点开始，直至处理到根节点。如果用递归算法，则应该按后序遍历方式处理每个节点。（2）给定集合Sv，为每个内部节点v的特征c赋予值vc。如果v有一个父节点u满足ucSv,则将uc赋予vc，否则任取一个tSv赋予vc。这个过程的执行方向刚好与上一个过程相反，即从树根出发，直至叶节点为止，最后得到完全标定的树。应按前序遍历方式依次处理每个节点。2、最大似然法 最大似然法目标是寻找能够以较高概率产生观察数据的系统发生树。对于给定的一组物种，假设它们的观察值为M（M为向量）选择一棵树，使得P(M|T)最大，3、相容性方法
14、 定义目标函数考虑的另一方面是相容性(compatibility)，即与一棵树相一致的特征个数。很显然，相容的特征数越多越好。相容性方法实际上是简约方法的一种简化，在所有的特征都是二值的情况下，这种方法非常有用。令S代表一组分类单元T是关于S的系统发生树如果在解释叶节点中分类单元的特征数据时，只需要沿T的一条边变化，则称该特征与系统发生树T是相容的。0 0 1 1 1 0 0 1 *（a）(b)具有4个分类单元的系统发生树：(a)相容特征；(b)不相容特征。C(1,1)D(1,1)A(1,0)B(0,0)E(0,0)（T2：1,1）（T1：1,0）（T：0,0）图6.13 根据特征值组合表构造
15、的系统发生树系统发生树的可靠性系统发生树的可靠性对于所构建的系统发生树，统计分析的误差可能会对于所构建的系统发生树，统计分析的误差可能会影响所建树的可靠性。影响所建树的可靠性。问题：问题：整棵树和它的组成部分（分支）的置信度是多少？整棵树和它的组成部分（分支）的置信度是多少？这样得到正确的树的可能性比随机选出一棵是正确的树这样得到正确的树的可能性比随机选出一棵是正确的树的可能性大多少？的可能性大多少？自举检验自举检验参数检验参数检验 系统发生分析中可能存在的问题系统发生分析中可能存在的问题 序列的选择序列的选择 基因的水平转移基因的水平转移 不同的序列，不同的结果不同的序列，不同的结果全基因组
16、的系统发生分析全基因组的系统发生分析 基于多棵系统发生树的方法基于多棵系统发生树的方法 基于基因内容的方法基于基因内容的方法 基于蛋白质折叠结构的方法基于蛋白质折叠结构的方法基于基因次序的方法基于基因次序的方法 基于连接的直向同源蛋白的方法基于连接的直向同源蛋白的方法基于代谢途径（基于代谢途径（pathwaypathway）的方法）的方法 系统发生分析常用软件系统发生分析常用软件(1)PHYLIP(2)PAUP(3)TREE-PUZZLE(4)MEGA(5)PAML(6)TreeView(7)VOSTORG(8)Fitch programs (9)Phylo_win(10)ARB(11)DAM
17、BE(12)PAL(13)Bionumerics 其它程序见：http:/evolution.genetics.washington.edu/phylip/software.html系统发生分析实例系统发生分析实例4分析的对象 13条来自不同物种的同源蛋白质（1）多重序列比对（2）构建系统发生树4根据序列比对结果计算序列之间的距离，生成距离矩阵。然后分别利用聚类方法和拓扑学方法建立系统发生树。SARSSARS病毒基因组病毒基因组初步分析初步分析SARSSARS病毒基因组与其他冠状病毒的病毒基因组与其他冠状病毒的结构相似。结构相似。主要蛋白质：主要蛋白质：RNARNA聚合酶蛋白（聚合酶聚合酶蛋白（聚合酶1a,1b1a,1b）S S蛋白（蛋白（spike proteinspike protein）E E蛋白（蛋白（membrane proteinmembrane protein）NN蛋白（蛋白（nucleocapsidnucleocapsid protein protein）等。）等。进化关系树如下进化关系树如下 SARS病毒明显不同于同其他三个冠状病毒群，可能归属于新的冠状病毒群。
