（计算机应用技术专业论文）基于代谢网络的系统发生树的构建.pdf

摘要 系统发生学的研究已经有几十年的历史了。目前，大部分的研究都是基于 d n a 或者蛋白质序列进行系统发生分析的，并且针对不同物种演示它们的进化历 史。这些方法最终都将产生一棵系统发生树，树的节点代表物种，而节点间的连 边代表物种间的进化关系。由于基因序列数据的不足，通过分析不同物种的代谢 网络可以更深层次的发现这些物种的进化和类别关系。代谢网络的拓扑结构可以 用酶图来表示，本文提出一种新的酶图间距离的计算方法，用图的顶点间相似度 和图的结构关系来定义图的距离。使用这样的方法，可以比较包含一类网络或一 组网络的不同物种，得到的距离矩阵可以用来构建系统发生树。在不同物种的柠 檬酸代谢网络中应用这种方法，实验得到的系统发生树与真实的结果十分接近， 而且还能显示它们的进化关系。 关键词：系统发生树代谢网络图的比对 a b s t r a c t p h y l o g e n e t i c sh a sb e e ni n v e s t i g a t e df o rs e v e r a ld e c a d e s n o w , m o s to ft h e s e s t u d i e sp e r f o r map h y l o g e n e t i ca n a l y s i so fd n ao rp r o t e i ns e q u e n c e st os t u d yt h e e v o l u t i o n a r yh i s t o r yo fo r g a n i s m sf r o mb a c t e r i at oh u m a n s t h e s em e t h o d sl e a dt oa p h y l o g e n e t i c t r e ei nw h i c ht h en o d e sr e p r e s e n td i f f e r e n ts p e c i e sa n dt h ee d g e s r e p r e s e n te v o l u t i o n a r yr e l a t i o n s h i p s f o rt h ei n s u f f i c i e n td a t ao fg e n es e q u e n c e s ， c o m p a r a t i v ea n a l y s i so fm e t a b o l i cn e t w o r k si nd i f f e r e n tg e n o m e sc a ng i v ei n s i g h t si n t o t h eu n d e r s t a n d i n go fe v o l u t i o n a r ya n do r g a n i z a t i o n a lr e l a t i o n s h i p sa m o n gs p e c i e s t h e t o p o l o g i c a ls t r u c t u r eo fm e t a b o l i cn e t w o r k sc a nb er e p r e s e n t e da se n z y m e - e n z y m e r e l a t i o n a lg r a p h s i tw a sp r e s e n t e dan e wt e c h n i q u et oo b t a i nt h ed i s t a n c eo fd i f f e r e n t g r a p h s ad i s t a n c em e a s u r eb e t w e e ng r 印l l si sd e f i n e du s i n gt h es i m j l 撕t yb e t w e e n n o d e so fg r a p h sa n dt h es t r u c t u r a lr e l a t i o n s h i pb e t w e e nt h e m u s i n gt h i sa p p r o a c h ， n e t w o r k sa n dg r o u po fn e t w o r k so fd i f f e r e n to r g a n i s m sa r ec o m p a r e dt oe a c ho t h e ra n d t h er e s u l t i n gd i s t a n c em a t r i xi su s e dt oo b t a i nap h y l o g e n e t i ct r e e a p p l yt h em e t h o dt o t h ec i t r i ca c i dc y c l em e t a b o l i cn e t w o r k so fd i f f e r e n to r g a n i s m s p h y l o g e n e t i ct r e e s o b t a i n e df o r mt h ee x p e r i m e n t sa r ec l o s et oe x i s t i n g p h y l o g e n i e sa n dr e v e a l e v o l u t i o n a r yr e l a t i o n s h i p sa m o n go r g a n i s m s k e y w o r d s ：p h y l o g e n e t i ct r e e s m e t a b o l i cn e t w o r k s g r a p hc o m p a r i s o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文巾做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：企蠡、步够番殳日期五嘶jr 哆i a 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密在年解密后适用本授权书。 本人签名： 导师签名： 日期娜车闱毋n 日期础 第一章绪论 第一章绪论 1 1 研究背景 系统发生学是进化生物学的一个重要研究领域，系统发生分析早在达尔文时 代就已经开始。从那时起，科学家们就开始寻找物种的源头，分析物种之间的进 化关系，给各个物种分门别类。经典系统发生学研究所涉及的特征主要是生物表 型特征，所谓的表型特征主要指形态学的( 结构的) 特征，如生物体的大小、颜 色、触角个数，也包括某些生理的、生化的以及行为习性的特征。通过表型比较 来推断生物体的基凶型，研究物种之间的进化关系。但是，利用表型特征是有局 限性的。有时候关系很远的物种也能进化出相似的表型，这是由称为趋同进化的 过程造成的。 随着人们对生物的认识从宏观发展到微观，对物种分类的依据也从宏观上的 形态发展到了微观上的分子，并且有了突破性的进展，系统发生分析进入分子层 次。科学家认为，现今世界上存在的核酸和蛋白质分子都是从共同的祖先经过不 断的进化而形成的，作为生物遗传物质的核酸和作为生命机器的蛋白质分子中存 在着关于生物进化的信息，可用于系统发生关系的研究。在分子水平上进行分析 具有许多表型分析所没有的优势，所得到的结果更加科学、可靠。分子系统发生 分析直接利用从核酸序列或蛋白质分子提取的信息，作为物种的特征，通过比较 生物分子序列，分析序列之间的关系，构造系统发生树，进而阐明各个物种的进 化关系。当然，这些分子不仅在序列上保留进化的痕迹，它们的结构也保留着进 化的痕迹。在分子水平上研究生物之间的关系早在2 0 世纪初就开始了。直到2 0 世纪中期，分子数据才开始被广泛应用于系统发生研究。蛋白质电泳使得我们可 以在一些浅层特征上，如分子大小和电荷，来分离和比较相关的蛋白质。2 0 世纪 6 0 年代，蛋白质测序成为可能；2 0 世纪7 0 年代，研究者开始能够获得基因组信 息，特别是d n a 序列。蛋白质序列和d n a 序列为分子系统发生分析提供了可靠 的数据。 随着研究的深入，越来越多的问题呈现在我们面前，也提出了更高的要求。 目前，科学家们已经对基于d n a 或者r n a 序列的系统发生树进行过研究，不过 由于火部分的基因组序列未被破译，现有的少量的数据是无法准确全面地描述整 个物种进化过程的。而代谢网络是所有生物所拥有的复杂的物理和化学过程，包 含物种大量的重要信息，基于代谢网络的系统发生树的研究不论从数据来源还是 2 基于代谢网络的系统发生树的构建 技术上都更具有可实现性和可靠性。基于代谢网络的系统发生树的构建也正是本 文所致力研究的问题。 1 2 构建系统发生树的研究历史和现状 所有的生物都可以追溯到共同的祖先，生物的产生和分化就像树一样地生长、 分叉，以树的形式来表示生物之间的进化关系是非常自然的事。可以用树中的各 个分支点代表一类生物起源的相对时间，两个分支点靠得越近，则对应的两群生 物进化关系越密切。 系统发生分析一般是建立在分子钟( m o l e c u l a rc l o c k ) 基础上的。生物随着时间 的推进而演化，进化的速率被视为进化研究中的基本问题之一。进化速率就是在 某一段时间内的遗传改变量。分子进化速率相关的分子钟的概念源于对蛋白质序 列的研究。在长期的进化过程中，有着相似功能约束的位点的分子进化速率则几 乎完全一致。2 0 世纪6 0 年代最早由e m i l ez u c k e r k a n d l 和l i n u sp a u l i n g 所做的蛋 白质序列的比较研究表明，蛋白质同系物的替换率就算过了千百万年也能保持恒 定，因此他们将氨基酸的变异积累比做分子钟。k i m u r a 进一步提出了具体的分子 进化观点：对于各物种的每个蛋白质，如果用每个位点每年发生的氨基酸替换次 数作为衡量分子进化的速率，则该速率是大致恒定的；功能上次要的分子( 或者 分子部分) 的进化速率比功能重要的分子( 或者分子部分) 进化速率快：对现有 分子结构或者功能破坏小的氨基酸替换比破坏力大的氨基酸替换发生得更加频 繁。 目前，基于d n a 和r n a 序列构建系统发生树主要使用的是r i b o s o m a lr n a 1 6 s 序列组，因为这些序列存在于大部分的生物体内，而且能被比较完整的保留 下来。可是仅仅靠基因序列所包含的信息还是无法判断同一代物种问的类别关系， 甚至错误的比较和物种间不同的进化率还可能导致得到的系统发生树是错误的。 而代谢网络是所有生物所拥有的复杂的物理和化学过程，包含物种大量的重要信 息。这方面的研究成果也很多，主要有： 1 9 9 9 年，f o n t 和s c h u l t e n t l 2 j 提出了基于代谢网络中结合酶序列和潜在网络 的信息来衡量不同物种的相似性，可惜没有给出计算距离的公式。 2 0 0 0 年，t o h s a t o 等人【3 剐又提出了比较基因组和代谢网络的方法，该方法基 于基因序列和酶反应的相似性判断。用酶的e cn u m b e r s 值来计算酶反应的相似 性，并使用动态规划的算法比较不同的代谢网络。 2 0 0 2 年，l i a o 等人f 2 3 1 提出了基于代谢网络比较不同物种的算法，该算法将 生物中存在和不存在的代谢网络用布尔矢量来表示，使用一些常用的距离计算， 通过聚类构建系统发生树，结果所表示的进化关系与基于1 6 sr r n a 的系统发生 第一章绪论 3 分析有所不同。 1 9 8 3 年，s a n f l i u 和f u l 3 5 1 将计算距离的方法划分为两类：一类是基于特征的 距离计算方法，就是从每个图中提取一个特征集合，并用向量表示来计算距离。 另一类是基于成本的距离计算方法，该方法考虑的是将一个图转化为另一个图所 消耗的最小成本。转化的操作有“删除”和“插入”。 1 9 9 9 年，p a p a d o p o u l o s 和m a n o l o p o u l o s 3 l 】用基于特征的距离计算方法构建了 一个特征向量，该方法通过计算顶点的入度和出度来衡量距离的，在实际应用中 存在一些误差。 1 9 9 6 年，s h a s h a 等人1 3 9 用基于成本的距离计算方法构建了一个模型c u a l ( c o n n e c t e du n d i r e c t e da c y c l i cg r a p h sw i t hl a b e l l e dn o d e s ) ，这个模型很好的解决 了误差问题，不过计算距离的算法却是n p 问题，但可以通过具体问题简化模型 来解决实际问题。 1 9 9 8 年，b u n k e 和s h e a r e r t 习基于最大公共子图定义了图的距离距阵，该算法 的主要问题是子图一构是个n p 问题。 2 0 0 2 年，m e l n i k 等人【2 4 】提出了匹配两个图的最好的迭代算法，主要思想是 依据当比较两个图的对应的顶点时，如果这两个顶点周围的顶点十分相似，那么 这两个对应的顶点就是相似的。 2 0 0 2 年，j e h 和w i d o m 1 7 】也提出了顶点相似性的比较方法，不同的是他们所 讨论的是一个图的任意两个顶点，而不是两个图的对应顶点。 一 2 0 0 2 年，b l o n d e l 和v a nd o o r e n l 3 1 定义了有向图之间对应顶点的相似性的概 念，提出了通过迭代方法计算任意顶点间的相似性。 除了以上算法，研究人员还提出了大量应用于实际问题的构建系统发生树的 解决方法。综上所述，构建系统发生树的方法是多种多样，应用广泛的。虽然， 由于问题本身的复杂性导致算法的效率和准确度还不尽人意，但该领域的研究已 经展现出广阔的发展空间和蓬勃的生机。 1 3 本文的主要研究内容和论文结构 为了研究物种间的进化关系，相关研究人员提出了各式各样的方法，采用了 各种数据。有基于d n a 和蛋白质序列的，也有基于代谢网络的，总结问题的关 键就是必须有丰富的可靠数据，合理的算法。由于d n a 和蛋白质序列数据存在 的一些不足的问题，因此本文的研究集中基于代谢网络，在此基础上构建系统发 生树。 目前为止的大多数的图的比较算法都存在一些问题，或者某些算法还不够具 体，本文综合了这些算法的优点，针对代谢网络，构造分析新的模型。顶点间的 4 基于代谢网络的系统发生树的构建 相似性综合了m e l n i k 和b l o n d e l 等人1 2 4 , 3 1 的思想，在计算顶点问距离的时候采用 了m a u r e e nh e y m a n s 和a m b u jk s i n g h t 柏l 的八个公式，而在比较图的距离上，本 文提出了一种新的计算方法，该方法不仅具有更高的效率，而且还避免了传统图 比较中用到的二分图匹配问题。 本文的组织结构如下： 第二章：简要的介绍了系统发生树的定义，以及几种常见的系统发生树的形 式和性质。 第三章：详细介绍了构建系统发生树目前已有的各种方法，根据所用的数据 不同，分为基于距离构建系统发生树和基于特征构建系统发生树。基于距离的构 建方法有非加权分组平均法( u n w e i g h t e dp a i rg r o u pm e t h o dw i t h a r i t h m e t i cm e a n s ) 、 邻近归并法( n e i g h b o rj o i n i n gm e t h o d ) 、f i t c h m a r g o l i a s h 法、最小进化方法 ( m i n i m u me v o l u t i o n ) 等，而基于特征的构建方法有最大简约法( m a x i m u m p a r s i m o n ym e t h o d ) 、最大似然法( m a x i m u ml i k e l i h o o dm e t h o d ) 、进化简约法 ( e v o l u t i o n a r yp a r s i m o n ym e t h o d ) 、相容性方法( c o m p a t i b i l i t y ) 等。最后，介绍 自举检验和参数检验来评价一棵系统发生树的可靠性。 第四章：提出了基于代谢网络构建系统发生树的方法。介绍较复杂的构建系 统发生树算法，分为以下几步：首先从代谢网络中抽取酶图，然后计算图任意两 个顶点间的相似性，接着用二分图匹配方法找出一一对应的顶点，最后计算图的 相似性。而且基于我们提出的改进的图的相似性计算方法，通过大量的仿真实验， 该算法得到的实验数据能很好的反映真实结果。 第五章：总结了本文的主要内容，以及自己在构建系统发生树方面所作的研 究工作，并且明确了以后的研究方向。 本文的研究分别得到国家自然科学基金项目：生物分子网络数据分析中相关 图问题及其算法研究( n o 6 0 5 7 4 0 3 9 ) 的资助。 第二章系统发生树的简介 第二章系统发生树的简介 2 1 系统发生树的定义和分类 5 一般来说，系统发生树是一种二叉树。所谓树，实际上是一个无向非循环图。 系统发生树由一系列节点( n o d e s ) 和分支( b r a n c h e s ) 组成，其中每个节点代表 一个分类单元( 物种或序列) ，而节点之间的连线代表物种之间的进化关系。树的 节点又分为外部节点( t e r m i n a ln o d e ) 和内部节点( i n t e r n a ln o d e ) 。在一般情况下， 外部节点代表实际观察到的分类单元，而内部节点又称为分支点，它代表了进化 事件发生的位置，或代表分类单元进化历程中的祖先。分类单元是一种由研究者 选定的基本单位，在同一项研究中，分类单元一般应当一致。 树幸良 a a ( a ) 图2 1 有根树 c d 图2 2 无根树 系统发生树有许多形式：可能是有根树( r o o t e dt r e e ) 如图2 1 ( a ) ，也可能是 无根树( u n r o o t e dt r e e ) 如图2 2 ( b ) ；可能是一般的树，也可能是- - x 树；可能是 6 基于代谢网络的系统发生树的构建 有权值的树( 或标度树，s c a l e d t r e e ，树巾标明分支的长度) ，也可能是无权值树( 或 非标度树，u n s c a l e dt r e e ) 。在一棵有根树中，有一个唯一的根节点，代表所有其 它节点的共同祖先，这样的树能够反映进化层次，从根节点历经进化到任何其它 节点只有唯一的路径。系统发生分析中一个重要的差别是，有的能由系统发生树 推断出共同祖先和进化方向，而有的却不能。无根树没有层次结构，无根树只说 明了节点之间的关系，没有关于进化发生方向的信息。但是，通过使用外部参考 物种( 那些明确地最早从被研究物种中分化出来的物种) ，可以在无根树中指派根 节点。例如，在研究人类和大猩猩时，可用狒狒作为外部参考物种，树的根节点 可以放在连接狒狒与人和大猩猩共同祖先的分支上。 2 2 系统发生树的性质 二叉树是一种特殊的树，每个节点最多有两个子节点。在有权值的树中，分 支的长度( 或权值) 一般与分类单元之间的变化成正比，它是关于生物进化时间 或者遗传距离的一种度量形式。一般假设存在一个分子钟，进化的速率恒定。 系统发生树具有以下性质： ( 1 ) 如果是一棵有根树，则树根代表在进化历史上是最早的、并且与其它所有分 类单元都有联系的分类单元； ( 2 ) 如果找不到可以作为树根的单元，则系统发生树是无根树； ( 3 ) 从根节点出发，到任何一个节点的路径均指明进化时间或者进化距离。 图2 1 ( a ) 所示的是一棵有根树，而图2 2 ( b ) 显示的是一棵无根树，图中的a 、 b 、c 、d 为所研究的分类单元。 对于给定的分类单元数，有很多棵可能的系统发生树，但是只有一棵树是正 确的，分析的目标就是要寻找这棵正确的树。 基于单个同源基因差异构建的系统发生树称为基因树( g e n et r e e ) ，这比称作 物种树( s p e c i e st r e e ) 更为合理。因为这种树代表的仅仅是单个基因的进化历史， 而不是它所在物种的进化历史。物种树一般最好是通过综合多个基凶数据的分析 结果而产生。基凶树和物种树之问的差异是很重要的，例如，假设只用h l a 的 等位基因来构建物种树，许多人将与大猩猩分在一起，而不是和其他人分在一起。 第三章构建系统发生树的方法 第三章构建系统发生树的方法 3 1 问题描述和分子数据 7 分子系统发生分析主要分成三个步骤：( 1 ) 分子序列或特征数据的分析；( 2 ) 系统发生树的构造；( 3 ) 结果的检验。其中，第一步的作用是通过分析，产生距 离或特征数据，为建立系统发生树提供依据。用于构建系统发生树的分子数据可 以分成两类：一个是距离( d i s t a n c e s ) 数据，常用距离矩阵描述，表示两个数据 集之间所有两两差异；另一个是特征( c h a r a c t e r s ) 数据，表示分子所具有的特征。 根据所处理数据的类型，可以将系统发生树的构建方法大体上分为两大类。 一类是基于距离的构建方法，利用所有物种或分类单元问的进化距离，依据一定 的原则及算法构建系统发生树。基本思路是列出所有可能的序列对，计算序列之 间的遗传距离，选出相似程度比较大或非常相关的序列对，利用遗传距离预测进 化关系。这类方法有非加权分组平均法( u n w e i g h t e dp a i rg r o u pm e t h o dw i t h a r i t h m e t i cm e a n s ) 、邻近归并法( n e i g h b o r j o i n i n gm e t h o d ) 、f i t c h m a r g o l i a s h 法、 最小进化方法( m i n i m u me v o l u t i o n ) 等。另一类方法是基于离散特征的构建方法， 利用的是具有离散特征状态的数据，如d n a 序列中的特定位点的核苷酸。建树 时，着重分析分类单位或序列间每个特征( 如核苷酸位点) 的进化关系等。属于 这一类的方法有最大简约法( m a x i m u mp a r s i m o n ym e t h o d ) 、最大似然法( m a x i m u m l i k e l i h o o dm e t h o d ) 、进化简约法( e v o l u t i o n a r yp a r s i m o n ym e t h o d ) 、相容性方法 ( c o m p a t i b i l i t y ) 等。 对于相似性和距离数据，在重建系统发生树时只能利用距离法。离散特征数 据通过适当的方法可转换成距离数据，因此，对于这类数据在重建系统发生树时， 既可以用距离法，亦可以采用离散特征法。 3 2 基于距离的系统发生树构建算法 建立系统发生树的基本任务是：在给定的条件下( 包括分类单元、分类单元 的特征值、序列或者网络) ，构造一棵最优的系统发生树。 基于距离的系统发生树构建方法的基本思路是：给定一种序列之间距离的度 量，在该距离度量下构建一棵系统发生树，使得该树能够最好地反映已知序列之 问的距离。这种方法采用两两距离，建立一个距离矩阵，根据距离矩阵构造系统 发生树。 基于代谢网络的系统发生树的构建 3 2 1 最小二乘法 在很多情况下，距离矩阵传达了大部分进化信息。运用序列比较程序，可以 计算出序列之间的距离。但是，在进行序列比较时，应根据比较的对象是d n a 序列还是蛋白质序列，正确选用不同的打分矩阵。 为了便于分析，首先定义一种连续加和距离函数，在该函数下，两个分类单 元之间的距离与系统发生树中连接这两个分类单元的分支总长度成正比。这样， 如果分类单元a 和分类单元b 由经过中间节点v 的两条边相连，两条边的长度分 别为丸和以，则它们之间的距离为d 。+ 叱。这样，可以在系统发生树中确定a 和b 的相对位置。进一步，假设三个分类单元之间的距离分别为九、叱、d k ， 如果分类单元a 和分类单元b 由经过中间节点v 的两条边相连，再经过节点u 与 分类单元c 相连，则可以通过求解线性方程计算出系统发生树的各种内部距离。 例，如果有三个分类单元，其两两距离如下： 如= 0 0 8 ；九= 0 4 5 ；丸= 0 4 3 l l a 图3 1 根据方程求解结果构造系统发生树 假设分类单元a 和分类单元b 的分歧起始时间是相同的，根据分子时钟假说， 丸和丸的值应该是相等的，进一步假设节点u 到其它节点的距离相同，则通过 求解方程，得到如图3 1 所示的一棵树。 图3 1 是一个简单的例子，但是，在实际应用中，所要处理的分类单元可能 很多，因而，需要求解的线性方程也很多，难以求解，或者方程组的求解过程存 在着不确定性。因此，需要采用数学逼近的方法。统计学上逼近的方法之一是最 小二乘法。我们的目标是构造一棵树t ，以该树的叶节点代表分类单元，用该树 预测分类单元之间的距离。通过优化，使下式最小化： s s o ( r ) = ( d ，一d ，) 2 ( 3 1 ) 第三章构建系统发生树的方法9 这里，或为分类单元i 和j 的实际观察距离( 或序列之问的计算距离) ，d ，是 分类单元i 和j 在系统发生树t 中的距离，形，是与分类单元i 和j 相关的权值。 s s q ( r ) 是树t 所有预测值与实际观察值偏差的累加和。权值一般为l ，或 1 7d ；o 寻找一棵最小方差树是一个n p 完全问题，需要采用近似的算法。下面介绍 几种计算时间复杂度为多项式的启发式方法，即连锁聚类方法( 1 i n k a g e c l u s t e r i n g ) 、非加权组平均法( u p g m a ) 和邻近归并法( n e i g h b o rj o i n i n g ) 。 3 2 2 连锁聚类方法及t b - d n 权分组平均法 连锁聚类属于一般的聚类分析方法，当用来构建系统发生树时，其假定的前 提条件是：在进化过程中，核苷酸或氨基酸的替换速率是均等且恒定的，在每一 次分歧发生后，从共同祖节点到两个分类单元间的分支长度一样。在构建系统发 生树时，首先用n 个叶节点表示n 个分类单元( 序列) ，每个分类单元自成一类， 然后通过反复的聚类使所有的分类单元都聚为一类，并将进化过程中的祖先赋予 树的内部节点，最终得到一个完整的系统发生树。假设若干条序列是从一个共同 的祖先进化而来，则系统发生树将是一个有根树，并且从根节点出发到所有叶节 点路径的长度相同。 对于给定的序列，通过序列之间的两两比对，计算序列之间的进化距离，然 后根据距离矩阵构造系统发生树。算法的基本思路是首先从距离矩阵中选择距离 最小的一对分类单元( 序列) ，令它们分别为x 和y ，然后将这两个分类单元合二 为一，形成一个新的对象( 代表这两个分类单元的祖先，记为z ) ，并重新计算这 个新的对象与其它分类单元( 或对象，以u 表示) 之间的距离a ( z ，u ) 。不同的实现 方案采用不同的计算公式： 单连锁聚类： a ( z ，“) = m i n ( d ( x ，u ) l a ( y ，”) ) ( 3 - 2 ) 最大连锁聚类： a ( z ，甜) = m a x ( d ( x ，”l d ，” ( 3 - 3 ) 平均连锁聚类： d ( z ，u ) - - p g ，甜) + a ( y ，u ) ) 2 ( 3 - 4 ) 上述公式中z 代表x 和y 的合并，u 代表任意其它对象。每次合并所形成的 新对象实际上是一个聚类，以一个内部节点表示，该节点到x 、y 所在节点的距 离相同，其值等于a ( x ，y ) 的一半，而到其它节点的距离按照上述公式计算。每次 合并后，修改距离矩阵。重复上述过程，直到所有的分类单元都被合并到一类为 止。 连锁聚类算法的执行过程如下： ( 1 ) 初始化：使每个分类单元自成一类，如果有n 个分类单元，则开始时共有 n 个类，每个类的大小为l ，分别用n 个叶节点代表每个类； 1 0 基于代谢网络的系统发生树的构建 ( 2 ) 执行下列循环： 寻找具有最小距离d ( 石，y ) 的两个类x 、y ； 建立一个新的聚类z ，该聚类是类x 和类y 的合并； 在树中建立一个新的内部节点z ，生长两个新的分支，将x 和y 连接到z ，并 使这两个分支到x 、y 中各个叶节点的长度为d b ，y ) 2 ； 按照公式( 3 2 ) 、( 3 3 ) 或( 3 4 ) 计算新的分类到其它类的距离； 在距离矩阵中删除与类x 和类y 相应的行和列，为类z 加入新的行和列，其 值按上述公式计算； 重复循环，直到仅剩一个类为止。 运用连锁聚类算法，得到一棵有根的系统发生树，从树根到任何叶节点的分 支长度全都一样，也就是说，所有物种的突变速率相同，存在一个固定节律的“分 子钟”，各个物种从树根( 代表某个历史起点) 出发，踏着同样的节律，沿不同的 路径，演化成为当前的形式。而任意两个物种之间的距离是连接这两个物种所在 叶节点路径上各分支长度之和。 如果上述过程处理的分类单元是序列的话，则聚类的过程实际上也是一个进 行序列多重比对的过程，将序列多重比对问题转化为序列两两比对问题。 非加权分组平均法( u n w e i g h t e dp a i rg r o u pm e t h o dw i t ha r i t h m e t i cm e a n u p g m a ) 是一种较为常用的聚类分析方法，最早是用来解决分类问题的。使用 该方法的前提条件也是稳定的进化速率。从分类过程来看，该方法与前面介绍的 平均连锁聚类方法相似，但是关于各个分类( 即若干个分类单元形成的集合) 之 间距离的计算公式不一样。在平均连锁聚类过程中，一个新类到其它类之间的距 离就是简单的原距离平均值。这样的计算非常简单，但是，如果各个类中分类单 元个数不一样，原距离矩阵中各个距离值对新距离计算的贡献就不一样，或者说 是经过“加权”的，称这样的聚类为加权分组平均( w e i g h t e dp a i rg r o u pm e t h o dw i t h a r i t h m e t i cm e a n ，w p g m a ) 。 在非加权分组平均法中，在计算新分类到其它分类之间的平均距离时按照各 分类中分类单元的数目进行加权处理。令类i 和类j 所形成的新分类为( f ) ，新分 类到其它类u 的距离按照下述公式计算： 2 【焘卜十【去肛 协5 ， 其中、刀，、协，+ 力，) 分别为i 类、j 类、( f ) 类的元素个数。这样，如果每 个距离对最终结果的贡献一样，即是“非加权”的。 u p g m a 算法的执行过程如下： ( 1 ) 初始化：使每个物种自成一类，如果有n 个物种，则开始时共有n 个类， 第三章构建系统发生树的方法 每个类的大小为l ，分别用n 个叶节点代表每个类； ( 2 ) 执行下列循环： 寻找具有最小距离或的两个类i 、j ：建立一个新的聚类何) 连接i 和j 形成新节点( ) ，生长两个新的分支，将i 和j 连接到谚) ，分支 的长度为d 。2 ： 计算新分类到其它类的距离； 在距离矩阵中删除与类i 和类j 相应的行和列，为类 ) 加入新的行和列： 重复循环，直到仅剩一个类为止。 表3 i 核苷酸序列距离 l2 34 56 7 89 2o 0 6 1 30 0 5 50 0 0 3 40 0 4 80 0 2 20 0 2 5 50 0 5 80 0 6 50 0 6 80 0 5 5 6 0 0 0 90 0 4 20 0 4 50 0 3 9 0 0 6 5 70 0 1 30 0 5 80 0 6 20 0 5 50 0 6 5o 0 1 6 80 0 2 80 0 6 90 0 7 20 0 6 50 0 7 50 0 3 20 0 2 9 9 0 0 9 3 0 1 2 20 1 2 60 1 1 9o 1 3 8 0 0 8 2 0 0 7 9 0 0 9 3 1 00 1 9 20 2 1 80 2 2 30 2 0 50 2 3 l0 1 8 00 1 8 0o 1 8 30 1 8 6 0 l1o 51 o 图3 2 针对表3 1 中距离矩阵用u p g m a 所构造的系统发生树 l 6 7 8 2 3 4 5 9 “ 基于代谢网络的系统发生树的构建 3 2 3 距离变换法 连锁聚类和u p g m a 算法的一个缺陷是假定所有家系的进化速率是相同的， 但是，实际情况并不总是这样。进化速率的变化容易导致连锁聚类和u p g m a 算 法产生错误拓扑结构的树。 有一些基于距离矩阵的方法考虑了不同的家系有不同的进化速率，其中最简 单最早的算法是距离变换法( t r a n s f o r m e dd i s t a n c em e t h o d ) 。这种方法充分利用 t p t - 群或外部参考物种( o u t g r o u p ) ，即先于其它所有被考虑的物种( 称为内群或内 部物种，i n g r o u p ) 从它们的共同祖先中分化出来的那些物种。 距离变换法的优势体现在那些很简单却容易被忽略的方面：内部物种只是在 分化发生后进化分离出来的，所以它们积累的替换数目一定是从那以后才有了差 异。此时，外部参考物种为比较它们替换速率提供了客观参考的框架。 3 2 4 邻近归并法 邻近归并法( n e i g h b o r j o i n i n g ) p 4 1 是另一种快速的聚类方法，该方法是s a i t o u 和n e i 于1 9 8 7 年首次提出的。在构建系统发生树时，该方法取消了非加权分组平 均法所作的假定，不需要关于分子钟的假设，在进化分支上，发生趋异的次数可 以不同。与非加权分组平均法相比，邻近归并法在算法上相对较复杂，它跟踪的 是树上的节点而不是分类单元。这种方法的基本思想是：在进行类的合并时，不 仅要求待合并的类是相近的，同时，还要求待合并的类远离其它的类。 在聚类过程中，根据原始距离矩阵，根据所有节点间的平均趋异程度，对每 两个节点间的距离进行调整，即将每个分类单元的趋异程度标准化，从而形成一 个新的距离矩阵。重建时，将距离最小的两个叶节点连接起来，合并这两个叶节 点所代表的分类，形成一个新的分类。在树中增加一个父节点，并在距离矩阵中 加入新的分类，同时删除原来的两个分类。随后，新增加的父节点被看成为叶节 点，重复上一次循环。在每一次循环过程中，都有两个叶节点被一个新的父节点 所取代，两个类被合成为一个新类。整个循环直到只剩一个类为止。从所得到的系 统发生树来看，对于两个聚在一起的分类单元，其所在的叶节点到父节点的距离 并不一定相同。 在每一次循环中，都要在树中寻找两个分类单元的直接祖先。对于节点i ， 到其它节点的距离u ；按下式进行估算： = 榭呱o 一2 ) ) ( 3 6 ) 这里d 膻是分类i 和分类k 之间的距离，在选择合并节点时选择d i i u ；一1 , 1 ，最 第三章构建系统发生树的方法 1 3 小的一对节点i 和节点j 进行归并。 算法如下： ( 1 ) 初始化： 使每个物种自成一类，如果有n 个物种，则开始时共有n 个类，每个类的大 小为l ，分别用n 个叶节点代表每个类； ( 2 ) 循环： 对于所有的分类单元i ，计算= 捌慨g 一2 ) ) ； 选择一对分类单元i 和j ，使巩一“，一“，最小； 将i 和j 归并为新的类( f ) ，在树中添加一个新的节点，代表新生成的分类， 计算从i 和j 到新节点的分支长度； d l ，国) = 1 2 d , ，+ 1 2 0 ；一甜) ，一，协) = 1 2 d , ，+ l 2 ( u ，一甜，) 计算新类与其它类的距离； d b u = 1 2 婶蚺+ d n d ) 删除聚类i 和j ，添加新类协) ，更新距离矩阵： 如果有两个以上的分类存在，则继续执行循环；合并剩余的两个类，并且连 接这两个类。 表3 26 个分类单元的距离矩阵 abcde b5 c47 d71 0 7 e6965 f81 l898 图3 3 利用邻近归并算法构造的系统发生树 b 1 4 基于代谢网络的系统发生树的构建 3 3 基于特征的系统发生树构建算法 基于特征的系统发生分析要解决的一般问题是：给定n 个分类单元，m 个用 以描述分类单元的特征，以及每个分类单元所对应的特征值，构建一棵系统发生 树，使得某个目标函数最大。输入一般为一个，l m 的矩阵m ，其中，m 。代表第 i 个分类单元之第j 个特征的取值。在构建系统发生树时，假设特征是相互独立的， 即一个特征的变化不影响另一个特征。另外，还假设在进化过程中，两个物种分 叉后独立进化，互不影响。 3 3 1 最大简约法 最大简约法( m a x i m u mp a r s i m o n y ) 最早是基于形态特征分类的需要而发展起 来的，具体的算法有许多版本，其中有些已被广泛地用于分子进化研究中，根据 离散特征数据构建系统发生树。 最大简约法的目标是构造一棵反映分类单元之间最小变化的系统发生树。最 大简约法利用的只是对简约分析能提供信息的特征，如在d n a 序列数据中，利 用的只是存在于核苷酸序列差异( 至少有两种不同类型的核苷酸) 的位点，这些 位点称为简约信息位点( p a r s i m o n yi n f o r m a t i v es i t e ) 。具体来说，信息位点就是指 能由位点产生的突变数目把一棵树与其它树区分开来的位点。如果对于某个位点， 所有序列都有同样的字符，则这个位点称为不变位点( i n v a r i a n t ) 。显然不变位点是 非信息位点( u n i n f o r m a t i v es i t e ) 。如果一个位点是信息位点，那么它至少有两种 不同的核苷酸，并且这些核苷酸至少出现两次。所有的简约法程序在开始时都将 这条简单的规则应用于输入数据集。 对于系统发生树最直观的代价计算就是沿着各个分支累加特征变化的数目， 而所谓简约就是使代价最小。利用最大简约方法构建系统发生树，实际上是一个 对给定分类单元所有可能的树进行比较的过程。针对某一个可能的树，首先对每 个位点祖先序列的核苷酸组成做出推断，然后统计每个位点用米阐明差异的核苷 酸最小替换数目。在整个树中，所有简约信息位点最小核苷酸替换数的总和称为 树的长度或树的代价。通过比较所有可能的树，选择其中长度最小、代价最小的 树作为最终的系统发生树，即最大简约树( m a x i m u mp a r s i m o n yt r e e ) 。 最大简约法的处理过程如下： ( 1 ) 针对待比较的物种，选择核酸或蛋白质序列。有些分子比其它分子的变化速 率稳定，适合于进行进化分析，例如哺乳类的线粒体d n a 、管家蛋白质等； ( 2 ) 比较各个序列，产生序列的多重比对，确定各个序列字符的相对位置； 第三章构建系统发生树的方法 1 5 ( 3 ) 根据每个序列比对的位置( 即多重序列比对的每一列) ，确定相应的系统发 生树，该树用最少的进化动作产生序列的差异，最终生成完整的树。 对于一棵系统发生树t ，假设树中的节点集合用矿仃) 表示，树中边的集合 用e 仃) 表示，以甜，、1 ，分别表示节点u 和v 的第j 个特征，则树t 的代价为： s 仃) = 阱，材，j ( 3 - 7 ) 给定一棵有根的系统发生树，我们所关心的是：如何计算该树的最小变化? 如何标定树的内部节点7 假设以，代表v 节点特征c 的值，单特征( 即每个分类单元所对应的序列仅 含一个字符，作为单个特征的值) 。f i t c h 算法如下：首先，对于每个待分析的分 类单元，分配一个叶节点v ，其值，。取对应分类单元的特征值。然后执行下面两 步： ( 1 ) 给每个节点v 赋予一个集合s ，：如果v 是叶节点，则s 。= ，。 ；如果 v 是内部节点，并且u 、w 是其子节点，如果瓯ns 。口，则s ，= s 。ns ，；否则 s ( v ) = 墨u s 。这个过程是从叶节点开始，直至处理到根节点。如果用递归算法， 则应该按后序遍历方式处理每个节点。 ( 2 ) 给定集合s ，为每个内部节点v 的特征c 赋予值v 。如果v 有一个父 节点u 满足u ，s 则将u 。赋予，。，否则任取一个t s ，赋予，。这个过程的执行 方向刚好与上一个过程相反，即从树根出发，直至叶节点为止，最后得到完全标 定的树。应按前序遍历方式依次处理每个节点。 上述算法对特征值之间变换的代价进行统一处理，不考虑其中的差别。其实， 各种特征值之间变换的代价是不一样的，比如，d n a 序列中碱基转换比颠换的可 能性大，碱基的插入和删除比替换的可能性小，长插入和删除比短插入和删除少 见。如果能给各种突变赋予相对概率值，则在简约算法中可将这些值转化为权值。 不幸的是，我们不可能得到一组适用于所有( 或大部分) 数据集的基于概率的权 值。确定一组普遍适用的相对概率的有许多困难，例如，一些序列( 象非编码序 列，特别是包含连续短重复片段的序列) 比其它序列更容易插入和删除，不同的 基因和物种有不同的