《生物信息学》课程教学资源（电子讲义）第八章 系统发育分析

基于单个同源基因差异构建的系统发生树称为基因树( gene tree,这比称作物种树 ( species tree)更为合理。因为这种树代表的仅仅是单个基因的进化历史,而不是它所在物 种的进化历史。物种树一般最好是通过综合多个基因数据的分析结果而产生。基因树和物种 树之间的差异是很重要的,例如,假设只用HLA的等位基因来构建物种树,许多人将与大 猩猩分在一起,而不是和其他人分在一起。 813距高和特征 用于构建系统发生树的分子数据分成两类:(1)距离( distances)数据,常用距离矩 阵描述,表示两个数据集之间所有两两差异:(2)特征( characters数据,表示分子所具有 的特征 分子系统发生分析的目的是探讨物种之间的进化关系,其分析的对象往往是一组同源的 序列。这些序列取自于不同生物基因组的共同位点。序列比对是进行同源分析的一种基本手 段,是进行系统发生分析的基础,一般采用基于两两比对渐进的多重序列比对方法,如 Clustalw程序。通过序列的比对,可以分析序列之间的差异,计算序列之间的距离。 无论是DNA序列,还是蛋白质序列,都是由特定字母表中的字符组成的。计算序列之 间距离的一个前提条件是要有一个字符替换模型,替换模型影响序列多重比对的结果,影响 系统发生树的构造结果。在具体的分析过程中,需要选择一个合理的字符替换模型,参见第 3章的各种打分模型或代价、距离模型 距离(或者相似度)是反映序列之间关系的一种度量,是建立系统发生树时所常用的 类数据。在计算距离之前,首先进行序列比对,然后累加每个比对位置的得分。可以应用第 3章介绍的关于序列比较方法,直接计算序列之间的距离。如果在进行序列比较时使用的是 打分函数或相似性度量函数,则需要将相似度(或者得分)转换成距离。令S(ij是序列 和序列j各个比对位置得分的加权和,一种归一化的距离计算公式为 d(,)=1-、(a,0-s,(3 (6-1) Sa(2,-S,(

基于单个同源基因差异构建的系统发生树称为基因树（gene tree），这比称作物种树 （species tree）更为合理。因为这种树代表的仅仅是单个基因的进化历史，而不是它所在物 种的进化历史。物种树一般最好是通过综合多个基因数据的分析结果而产生。基因树和物种 树之间的差异是很重要的，例如，假设只用 HLA 的等位基因来构建物种树，许多人将与大 猩猩分在一起，而不是和其他人分在一起。 8.1.3 距离和特征 用于构建系统发生树的分子数据分成两类：（1）距离（distances）数据，常用距离矩 阵描述，表示两个数据集之间所有两两差异；（2）特征(characters)数据，表示分子所具有 的特征。 分子系统发生分析的目的是探讨物种之间的进化关系，其分析的对象往往是一组同源的 序列。这些序列取自于不同生物基因组的共同位点。序列比对是进行同源分析的一种基本手 段，是进行系统发生分析的基础，一般采用基于两两比对渐进的多重序列比对方法，如 ClustalW 程序。通过序列的比对，可以分析序列之间的差异，计算序列之间的距离。 无论是 DNA 序列，还是蛋白质序列，都是由特定字母表中的字符组成的。计算序列之 间距离的一个前提条件是要有一个字符替换模型，替换模型影响序列多重比对的结果，影响 系统发生树的构造结果。在具体的分析过程中，需要选择一个合理的字符替换模型，参见第 3 章的各种打分模型或代价、距离模型。 距离（或者相似度）是反映序列之间关系的一种度量，是建立系统发生树时所常用的一 类数据。在计算距离之前，首先进行序列比对，然后累加每个比对位置的得分。可以应用第 3 章介绍的关于序列比较方法，直接计算序列之间的距离。如果在进行序列比较时使用的是 打分函数或相似性度量函数，则需要将相似度（或者得分）转换成距离。令 S(i,j)是序列 i 和序列 j 各个比对位置得分的加权和，一种归一化的距离计算公式为：

其中,S(ij)是序列i和j随机化之后的比对得分的加权和,Sm()是两条序列所有可能的比 对的最大值(当两条序列相同时,取最大值)。两个序列归一化距离的值处于0和1之间, 当两个序列完全一致时,距离为0:当两个序列差异很大时,距离接近于1。如果在上式中 令Sj)=0,则计算公式变为 d(,j)=1 S(,) (6-2) (2, 为了适合于处理相似性较小的序列,可以进一步修改距离计算公式 d6,=-n, (6-3) 序列比对得分的加权和可以根据常用的打分矩阵获得,如果待处理的序列是蛋白质,则用 PAM矩阵、 BLOSUM矩阵等;如果待处理的序列是DNA或者RNA,则用等价矩阵、核苷 酸转换-颠换矩阵或者其它具有非对称置换频率的矩阵 距离是系统发生分析时所使用的一类数据,另一类数据就是所谓的离散特征数据。离散 特征数据可分为二态特征与多态特征。二态的离散特征只有2种可能的状况,即具有与不具 有某种特征,通常用“0”或“1”表示。例如,DNA序列上的某个位置如果是剪切位点,其特 征值为1,否则为0。多态离散特征具有两种以上可能的状态,如核酸的序列信息,对序列 中某一位置来说,其可能的碱基有A、T、G、C共4种。可以将特征数据转换为距离数据 如果建立所有可能状态之间相似性的度量,特征数据就很容易被转换成距离数据。 814分子系统发生分析过程 分子系统发生分析主要分成三个步骤:(1)分子序列或特征数据的分析:(2)系统发 生树的构造:(3)结果的检验。其中,第一步的作用是通过分析,产生距离或特征数据, 为建立系统发生树提供依据 系统发生树的构建方法很多种。根据所处理数据的类型,可以将系统发生树的构建方法 大体上分为两大类。一类是基于距离的构建方法,利用所有物种或分类单元间的进化距离 依据一定的原则及算法构建系统发生树。基本思路是列出所有可能的序列对,计算序列之间

其中，Sr(i,j)是序列 i 和 j 随机化之后的比对得分的加权和，Smax(i,j)是两条序列所有可能的比 对的最大值（当两条序列相同时，取最大值）。两个序列归一化距离的值处于 0 和 1 之间， 当两个序列完全一致时，距离为 0；当两个序列差异很大时，距离接近于 1。如果在上式中 令 Sr(i,j)=0，则计算公式变为： 为了适合于处理相似性较小的序列，可以进一步修改距离计算公式： 序列比对得分的加权和可以根据常用的打分矩阵获得，如果待处理的序列是蛋白质，则用 PAM 矩阵、BLOSUM 矩阵等；如果待处理的序列是 DNA 或者 RNA，则用等价矩阵、核苷 酸转换-颠换矩阵或者其它具有非对称置换频率的矩阵。 距离是系统发生分析时所使用的一类数据，另一类数据就是所谓的离散特征数据。离散 特征数据可分为二态特征与多态特征。二态的离散特征只有 2 种可能的状况，即具有与不具 有某种特征，通常用“0”或“1”表示。例如，DNA 序列上的某个位置如果是剪切位点，其特 征值为 1，否则为 0。多态离散特征具有两种以上可能的状态，如核酸的序列信息，对序列 中某一位置来说，其可能的碱基有Ａ、Ｔ、Ｇ、Ｃ共 4 种。可以将特征数据转换为距离数据。 如果建立所有可能状态之间相似性的度量，特征数据就很容易被转换成距离数据。 8.1.4 分子系统发生分析过程 分子系统发生分析主要分成三个步骤：（1）分子序列或特征数据的分析；（2）系统发 生树的构造；（3）结果的检验。其中，第一步的作用是通过分析，产生距离或特征数据， 为建立系统发生树提供依据。 系统发生树的构建方法很多种。根据所处理数据的类型，可以将系统发生树的构建方法 大体上分为两大类。一类是基于距离的构建方法，利用所有物种或分类单元间的进化距离， 依据一定的原则及算法构建系统发生树。基本思路是列出所有可能的序列对，计算序列之间

的遗传距离,选出相似程度比较大或非常相关的序列对,利用遗传距离预测进化关系。这类 方法有非加权分组平均法( unweighted pair group method with arithmetic means)、邻近归并 法( neighbor joining method)、 Fitch- Margoliash法、最小进化方法( minimum evolution)等 另一类方法是基于离散特征的构建方法,利用的是具有离散特征状态的数据,如DNA序列 中的特定位点的核苷酸。建树时,着重分析分类单位或序列间每个特征(如核苷酸位点) 进化关系等。属于这一类的方法有最大简约法( maximum parsimony method)、最大似然法 ( maximum likelihood method)、进化简约法( evolutionary parsimony method)、相容性方 法( compatibility)等。对相似性和距离数据,在重建系统发生树时只能利用距离法。离散 特征数据通过适当的方法可转换成距离数据,因此,对于这类数据在重建系统发生树时,既 可以用距离法,亦可以采用离散特征法。 根据建树算法在执行过程中采用的搜索方式,系统发生树的构建方法也可以分为三类。 第一类是穷尽搜索方法,即产生所有可能的树,然后根据评价标准选择一棵最优的树。需要 注意的是,系统发生树可能的个数随序列的个数急剧增加。假设要为n个分类单元建立系统 发生树,则可能的有根树个数(Ng)和无根系统发生树个数(Nu)可用下面的算式计算得 (64) 22(x-2 可以看到,随着n的增加,可能的有根系统发生树和无根系统发生树的数目迅速增加。表 61中列出了一些n值,以及对应的有根树和无根树的数目。当n大于等于15时,可能的系 统发生树数目变得非常惊人,但是只有其中的一棵树代表了待分析的基因或者物种之间的真 实进化关系,我们的目的就是找出这棵反映真实进化关系的树。 表6.1对不同的n,可能的有根树和无根树数目 数据数目 有根树数目 无根树数目 15 15

的遗传距离，选出相似程度比较大或非常相关的序列对，利用遗传距离预测进化关系。这类 方法有非加权分组平均法（unweighted pair group method with arithmetic means）、邻近归并 法（neighbor joining method）、Fitch-Margoliash 法、最小进化方法（minimum evolution）等。 另一类方法是基于离散特征的构建方法，利用的是具有离散特征状态的数据，如 DNA 序列 中的特定位点的核苷酸。建树时，着重分析分类单位或序列间每个特征（如核苷酸位点）的 进化关系等。属于这一类的方法有最大简约法（maximum parsimony method）、最大似然法 （maximum likelihood method）、进化简约法（evolutionary parsimony method）、相容性方 法（compatibility）等。对相似性和距离数据，在重建系统发生树时只能利用距离法。离散 特征数据通过适当的方法可转换成距离数据，因此，对于这类数据在重建系统发生树时，既 可以用距离法，亦可以采用离散特征法。 根据建树算法在执行过程中采用的搜索方式，系统发生树的构建方法也可以分为三类。 第一类是穷尽搜索方法，即产生所有可能的树，然后根据评价标准选择一棵最优的树。需要 注意的是，系统发生树可能的个数随序列的个数急剧增加。假设要为 n 个分类单元建立系统 发生树，则可能的有根树个数（NR）和无根系统发生树个数（NU）可用下面的算式计算得 到： 可以看到，随着 n 的增加，可能的有根系统发生树和无根系统发生树的数目迅速增加。表 6.1 中列出了一些 n 值，以及对应的有根树和无根树的数目。当 n 大于等于 15 时，可能的系 统发生树数目变得非常惊人，但是只有其中的一棵树代表了待分析的基因或者物种之间的真 实进化关系，我们的目的就是找出这棵反映真实进化关系的树。 表 6.1 对不同的 n，可能的有根树和无根树数目 数据数目 有根树数目 无根树数目 2 1 1 3 3 1 4 15 3 5 105 15

050 34.459425 2.207.025 213,458,046,767,875 7,905,853,580,625 8,200,794,532,637,891,559,375221,643,095476,699,771,875 从计算量来看,穷尽搜索方法只能处理很少的分类单元。当分类单元个数n大于一定值 (如15),几乎不可能采用穷尽搜索的方式来求取最优树 第二类方法是分支约束方法,即根据一定的约束条件将搜索空间限制在一定范围内,产 生可能的树,然后择优。这是人工智能技术中的一种空间搜索策略,这种搜索方式不需要搜 索整个树空间,可大大提高搜索效率。第三类是启发式或经验性方法,即根据先验知识或一 定的指导性规则压缩搜索空间,提高计算速度。这种方法能够处理大量的分类单元,虽然不 能保证所构建的树是最优的,但实际结果往往接近于最优解。当待分析的对象个数比较多时, 必须采用分支约束方法或者启发式的方法。 在构造系统发生树时需要考虑进化假设和进化模型。系统发生树的类型可能是有根树, 这意味着其中的一个序列代表其他所有序列共同的祖先。另一方面,系统发生树可能是无根 树,意味着没有共同的祖先。一般认为序列是随机进化的,序列中的所有位点的进化也是随 机的而且是独立的。在进行具体的系统发生分析时,一般还要作一些假设:序列必须是正确 无误的,待分析的序列是同源的,所有的序列都起源于同一个祖先序列,并且它们不是共生 同源(或平行进化)序列,在序列比对中,不同序列的同一个位点都是同源 个物种在系统发生树上分化后,各自独立进化发展。对系统发生分析的样本也有一定的要求, 要求样本足以反映感兴趣的问题,样本序列之间的差异包含了足以解决感兴趣的问题的系统 发生信息。 通过某种算法构造好一棵系统发生树之后,需要对树的合理性和可靠性进行分析。对于 若干条序列,如果利用多种不同的分析方法进行系统发生分析,并且得到相似的进化关系 那么分析结果具有较高的可信度。 82基于距高的系统发生树构建方法 建立系统发生树的基本任务是:在给定的条件下(包括分类单元、分类单元的特征值或 者序列),构造一棵最优的系统发生树。这里重点讨论针对DNA序列或者蛋白质序列构建 系统发生树

10 34,459,425 2,207,025 15 213,458,046,767,875 7,905,853,580,625 20 8,200,794,532,637,891,559,375 221,643,095,476,699,771,875 从计算量来看，穷尽搜索方法只能处理很少的分类单元。当分类单元个数 n 大于一定值 （如 15），几乎不可能采用穷尽搜索的方式来求取最优树。 第二类方法是分支约束方法，即根据一定的约束条件将搜索空间限制在一定范围内，产 生可能的树，然后择优。这是人工智能技术中的一种空间搜索策略，这种搜索方式不需要搜 索整个树空间，可大大提高搜索效率。第三类是启发式或经验性方法，即根据先验知识或一 定的指导性规则压缩搜索空间，提高计算速度。这种方法能够处理大量的分类单元，虽然不 能保证所构建的树是最优的，但实际结果往往接近于最优解。当待分析的对象个数比较多时， 必须采用分支约束方法或者启发式的方法。 在构造系统发生树时需要考虑进化假设和进化模型。系统发生树的类型可能是有根树， 这意味着其中的一个序列代表其他所有序列共同的祖先。另一方面，系统发生树可能是无根 树，意味着没有共同的祖先。一般认为序列是随机进化的，序列中的所有位点的进化也是随 机的而且是独立的。在进行具体的系统发生分析时，一般还要作一些假设：序列必须是正确 无误的，待分析的序列是同源的，所有的序列都起源于同一个祖先序列，并且它们不是共生 同源（或平行进化）序列，在序列比对中，不同序列的同一个位点都是同源的。另外，当两 个物种在系统发生树上分化后，各自独立进化发展。对系统发生分析的样本也有一定的要求， 要求样本足以反映感兴趣的问题，样本序列之间的差异包含了足以解决感兴趣的问题的系统 发生信息。 通过某种算法构造好一棵系统发生树之后，需要对树的合理性和可靠性进行分析。对于 若干条序列，如果利用多种不同的分析方法进行系统发生分析，并且得到相似的进化关系， 那么分析结果具有较高的可信度。 8.2 基于距离的系统发生树构建方法 建立系统发生树的基本任务是：在给定的条件下（包括分类单元、分类单元的特征值或 者序列），构造一棵最优的系统发生树。这里重点讨论针对 DNA 序列或者蛋白质序列构建 系统发生树

基于距离的系统发生树构建方法的基本思路是:给定一种序列之间距离的度量,在该距 离度量下构建一棵系统发生树,使得该树能够最好地反映已知序列之间的距离。这种方法采 用两两距离,建立一个距离矩阵,如表72所示,根据距离矩阵构造系统发生树。 表6210条核酸序列的距离矩阵 2 6 8 2|00516 055000031 004830.02210.0253 005820.06510.06850.0549 600094004160.0450003840.0549 7|001250.058400619005510.06100157 0.02840.06870.07220.065400754 0.03170.0285 009250.12210.12590.11850.13700.0820007860.0927 100.19210.21830.2228020540.23090.17980.17950.18330.1860 这里的距离代表两条序列之间各位点核苷酸替换数的估计值 821最小二乘法 在很多情况下,这种距离矩阵传达了大部分进化信息。运用前面介绍的序列比较程序, 可以计算出序列之间的距离。但是,在进行序列比较时,应根据比较的对象是DNA序列还 是蛋白质序列,正确选用不同的打分矩阵。 为了便于分析,首先定义一种连续加和距离函数,在该函数下,两个分类单元之间的距 离与系统发生树中连接这两个分类单元的分支总长度成正比。这样,如果分类单元a和分类 单元b由经过中间节点v的两条边相连,两条边的长度分别为da和d,则它们之间的距离 为dn+dh。这样,可以在系统发生树中确定a和b的相对位置。进一步,假设三个分类单 元之间的距离分别为d、d、de,如果分类单元a和分类单元b由经过中间节点v的两条边 相连,再经过节点u与分类单元c相连,则可以通过求解线性方程计算出系统发生树的各种 内部距离 例,如果有三个分类单元,其两两距离如下 dh=05 dx=09

基于距离的系统发生树构建方法的基本思路是：给定一种序列之间距离的度量，在该距 离度量下构建一棵系统发生树，使得该树能够最好地反映已知序列之间的距离。这种方法采 用两两距离，建立一个距离矩阵，如表 7.2 所示，根据距离矩阵构造系统发生树。 表 6.2 10 条核酸序列的距离矩阵。 1 2 3 4 5 6 7 8 9 2 0.0516 3 0.0550 0.0031 4 0.0483 0.0221 0.0253 5 0.0582 0.0651 0.0685 0.0549 6 0.0094 0.0416 0.0450 0.0384 0.0549 7 0.0125 0.0584 0.0619 0.0551 0.0651 0.0157 8 0.0284 0.0687 0.0722 0.0654 0.0754 0.0317 0.0285 9 0.0925 0.1221 0.1259 0.1185 0.1370 0.0820 0.0786 0.0927 10 0.1921 0.2183 0.2228 0.2054 0.2309 0.1798 0.1795 0.1833 0.1860 这里的距离代表两条序列之间各位点核苷酸替换数的估计值。 8.2.1 最小二乘法 在很多情况下，这种距离矩阵传达了大部分进化信息。运用前面介绍的序列比较程序， 可以计算出序列之间的距离。但是，在进行序列比较时，应根据比较的对象是 DNA 序列还 是蛋白质序列，正确选用不同的打分矩阵。 为了便于分析，首先定义一种连续加和距离函数，在该函数下，两个分类单元之间的距 离与系统发生树中连接这两个分类单元的分支总长度成正比。这样，如果分类单元 a 和分类 单元 b 由经过中间节点 v 的两条边相连，两条边的长度分别为 dav 和 dbv，则它们之间的距离 为 dav+ dbv。这样，可以在系统发生树中确定 a 和 b 的相对位置。进一步，假设三个分类单 元之间的距离分别为 dab、dac、dbc,如果分类单元 a 和分类单元 b 由经过中间节点 v 的两条边 相连，再经过节点 u 与分类单元 c 相连,则可以通过求解线性方程计算出系统发生树的各种 内部距离。 例，如果有三个分类单元，其两两距离如下： dab = 0.5; dac = 0.9;