基于距离矩阵的进化树构建方法研究

基于距离矩阵的进化树构建方法研究 学校代号:10532 学 号:(107100001 密 级:普通 湖南大学硕士学位论文 基于距离矩阵的进化树构建方法研究 学位申请人姓名: 筮曩 导师姓名及职称: 奎仨发 教握 培养单位: 湖直太堂让簋扭生通信堂瞳 专业名称: 让簋扭型堂皇撞苤 论文提交日期: 2Q!Q生!!月墨旦 论文答辩日期: 2QlQ生!!旦2鱼旦 答辩委员会主席: 骆塞佳熬援 TheResearchonconstructionof phylogenetic distancematrix By 阢nZhu Ocean B(E( GuangdongUniversity 2000 Athesissubmittedin satisfactionofthe partial forthe of Requirementsdegree Masterof Engineering ln Scienceand Computer Technology inthe GraduateSchool of Hunan University Supervisor ProfessorLiRenfa 0ctober,2010 湖南大学 ( 学位论文原创性声明 本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名: 霖重 日期:?ot-年，1月莎日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1、保密口，在 年解密后适用本授权书。 2、不保密团。 请在以上相应方框内打“?” 作者签名: 瘤 日期:莎-，o年f1月g日 , 日期妒，o年，f月矿日 硕L学位论文 摘要 系统发育分析是生物信息学中的重要研究领域，它的主要研究手段是从一组 同源的DNA或蛋白质序列出发，计算各个序列之间的进化距离，从而得到反映 物种进化关系的进化树。进化树通常是一棵二叉树，树的叶节点，代表了某个具 体序列;树的拓扑结构表示了各物种之间的亲缘关系远近;树的分支长度刻画了 进化距离的大小。构建进化树的方法主要分为两大类:基于距离矩阵法和基于特 征法。其中，距离矩阵法以结构简单，具有良好的理论基础等特点获得广泛应用。 基于距离矩阵法是构建进化树方法中比较常用的一类方法，但是传统的基于 距离矩阵法是建立在序列比对基础上的。所以本文为了解决这个问题，提出了两 种新的方法，这两种都是不需序列比对，而且比较直观，计算量小，通俗易懂。 两种新方法是:基于改进的模糊聚类传递闭包的距离矩阵法和基于改进的k近邻 距离矩阵法。 基于改进的模糊聚类传递闭包的距离矩阵法是在原始的非相似距离矩阵上通 过改进，得到一个新的相似距离矩阵，这个新的相似距离矩阵是反映物种之间相 似度高的矩阵，然后在新的相似距离矩阵基础上利用了模糊聚类中的传递闭包法 构建进化树。 基于改进的k近邻距离矩阵法是建立在k近邻法和图论的基础上提出来的。这 种方法是在原始的距离矩阵基础上找出每一行的k个最相似的分类群，然后用线连 接起来，如果出现同路，则删除回路中距离最大的那条边，通过构建的一个最小 连通图，利用聚类的思想构建物种之间的进化树。这种算法主要是k的选择问题。 如果k过小，那么该图就不是一个最小连通图，而且存在孤立的边;如果k过大， 那么该图会变得复杂化，计算量会增加，相应地，时间复杂度和空间复杂度都会 增加。 程序来评估的，通过做实验来验证算法的可行性。 关键词:构建进化树: 距离矩阵; 传递闭包; K近邻 U 基于距离矩阵的进化树构建方法研究 Abstract Molecular isoneofthemost fieldsof phylogeneticanalysis important main which bioinformatics，thetaskof istorccoustructa treefroma phylogenetic of DNAor theevolutionar grouphomologousprotein sequences，showingrelationship betweenthe ofthose treeisa tree， species sequences(Usually，aphylogeneticbinary inwhichtheleafnodesstandfor orthe the tree species organisms，thetopology indicatesthe the ofbranchesoutthe relationship，and phylogenetic length figure distancebetweenthe andtheircommonancestor(Therearctwo evolutionary species main ofmethodstoreconstruct trees:basedondistancematrix types phylogenetic method，andbasedonfeaturemethod(Distancematrixmethodhaswide applications becauseofits andsolid simplicity theory( Basedondistancematrixmethoda is methodin commonly constructing thetraditionaldistancematrixmethodisbuilttobaseon trees，but phylogenetic ordertosolvethis twonew sequencealignment(Therefore，inproblem，wepropose are ofwhichwithout methods，both intuitive，less sequencealignment，andrelatively tounderstand(Thesemethodsarebasedonthedistancemarix calculation，easy methodinthe transitiveclosureof andbasedonthe improved fuzzyclustering distancemarixmethodinthe k-nearest inproved neighbor( Basedonthedistancemarixmethodinthe transitiveclosureof improved fuzzy isbasedonthe distancematrix clustering originaldissimilarity byinproving， andget anew distance isadirectreflectiononthe similaritymatrix，which highsimilarity matrix then thetransitiveclosuremethodofthe between species，and using fuzzy toconstructthe trees( clustering phylogenetic the in Basedon distancemarixmethodthe k-nearest is inproved neighbor for ontheknearest methodand is proposedbasing neighbor graphtheory， which basedonthe distancematrixto kmostsimilartaxaofeach original identify line，and thenlink withthe thereis removethe sideofthe up line，if loop，we largest loop，at aminimum on last，we connected the treesconstructed get graph，whichphylogenetic based(This is thechoiceof isnottoo mainly K，k algorithm makethe becameaminimalconnected theexistenceofisolated map graph，even isnottoo makethe more the edges;k large，otherwise，whichmap complicated，even calculationwill time and incease，correspondingly，the complexity complexityspace Will increase( III 硕 二学f移沦文 themethod Inordertoassess of the trees， feasibilityconstructingphylogenetic weoftenuse ofPHYLIPsoftwareto the program assess，we Neighbor(exe verify methodfeasibil the ityby experiment( trees;distancematrix;transitiveclosure; KeyWords:constructingphylogentic k-nearest neighbor IV 基丁(距离矩阵的进化树构建办法研究 目 录 学位论文原创性声明和学位论文版权使用授权 书„„„„„„„„„„„„„„„„„I 摘 要„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„II Abstract((((((((((((((((((((((((((((((((((((((((((((((((((((((((( ((((((((((((((((((((((((((((((((((((((((((((((((((((((((III 插图索 引„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„VI 附表索 引„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„VII 第l章绪论„„„„„„„„„„„„„„„„„„„„„„„„„„„l 1(1研究背景和意 义„„„„„„„„„„„„„„„„„„„„„„„„„„„„一l 1(2国内外研究现 状„„„„„„„„„„„„„„„„„„„„„„„„„2 1(2(1距离度量标 准„„„„„„„„„„„„„„„„„„„„„„„„3 1(2(2基于距离建树法„„„„„„„„„„„„„„„„„„„„„一3 1(2(3基于特征建树法„„„„„„„„„„„„„„„„„„„„„„„„„„„5 1(2(4传统建树方法比较„„„„„„„„„„„„„„„„„„„„„„(7 1(2(5其他构建进化树方法„„„„„„„„„„„„„„„„„„„一8 1(2(6构建系统进化树的主要过程及相关软件„„„„„„„„„„„„(9 1(3本文的主要研究工 作„„„„„„„„„„„„„„„„„„„„„10 0 1(4本文的章节安 排„„„„„„„„„„„„„„„„„„„„„„„„„„„(1 第2章基于图形表示的相似距离矩阵计 算„„„„„„„„„„„„„„(12 2(1DNA序列的图形表 示„„„„„„„„„„„„„„„„„„„„„„(12 2(2基于图形的序列相似性分 析„„„„„„„„„„„„„„„„„„14 6 2(3构建相似距离矩 阵„„„„„„„„„„„„„„„„„„„„„„一l 8 2(4„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„l 第3章基于改进的模糊聚类传递闭包建树法„„„„„„„„„„„„„19 3(1模糊聚类的传递闭 包„„„„„„„„„„„„„„„„„„„„„„(19 3(2新方法的基本思 想„„„„„„„„„„„„„„„„„„„„„„„19 3(3新算法步 骤„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„20 3(4实验及结果分 析„„„„„„„„„„„„„„„„„„„„„„„„„20 3(5小结„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„25 第4章基于改进的k近邻距离矩阵建树法„„„„„„„„„„„„„„„一26 4(1k近邻法概 述„„„„„„„„„„„„„„„„„„„„„„„„„„26 4(2新方法的基本思 想„„„„„„„„„„„„„„„„„„„„„„„„„„„28 4(3新算法的具体步 骤„„„„„„„„„„„„„„„„„„„„„„„(28 4(4测试实例和结果分析„„„„„„„„„„„„„„„„„„„„一29 V 硕士学位论文 4(5小结„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„ „„„32 结 论„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„(33 参考文 献„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„35 致 谢„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„(40 附录A攻读学位期间所发表的学术论文和参加的项目与获得的奖励„„„„„(4l Vl 硕十学位论文 插图索引 图1(1NJ树的状态变 化„„„„„„„(j„„„„„„„„„„„„„„„„„„„(4 图1(2MP法中三种可能拓扑的最小替换数计算„„„„„„„„„„„„6 图2(1二维图形的三种坐 标„„„„„„„„„„„„„„„„„„„„„„„一13 图3(1方法1构建的11物种进化树„„„„„„„„„„„„„„„„„24 图3(2利用DRAWGRAM程序构建的11物种进化树„„„„„„„„„„25 图4(1使用方法2构造的二叉 树„„„„„„„„„„„„„„„„„„((29 图4(2方法2构建的8物种进化树„„„„„„„„„„„„„„„„„30 图4(3文献[73]中构建的8物种进化树„„„„„„„„„„„„„„(3l l 图4(4利用DRAWGRAM程序构建的8物种进化树„„„„„„„„„„„3 ? 基于距离矩阵的进化树构建方法研究 附表索引 表3(1方法1中编码序列的不相似矩阵„„„„„„„„„„„„„„(21 表4(1方法2中编码序列的不相似矩阵„„„„„„„„„„„„„„29 ? 硕l:学位论文 第1章绪论 系统发育学是进化生物学的一个重要研究领域，主要研究物种之间的进化关 系。换句话说，就是研究物种之间的特征，并认为在遗传学上特征越相似的物种 祖先越接近。系统发育研究的结果是以系统进化树来表示，用它来描述物种间的 进化历史。本章首先阐述构建进化树的研究背景和意义以及国内外研究现状;然 后简述一下本文的主要工作内容;最后简述一下本文各章节的主要内容。 1(1研究背景和意义 系统发育分析早在达尔文时代就已经开始了，从那时候开始，科学家们就开 始分析物种间的进化历史，以及给各个物种分门别类。经典系统发育分析研究的 特征主要是生物表型特征，但是利用表型特征是有局限的;会造成关系很远的物 种之间能进化出相似的表型„。在系统发育学的研究中，结果通常是通过系统进 化树来表示的，用来描述物种之间的进化关系。进化树是由一系列节点和分支组 成，其中每个节点代表一个生命个体，物种或者类属;而节点之间的连线代表物 种之间的进化关系。通过分析物种之间的特征，从而得到它们之间的进化历史是 系统发育学的主要目标。 随着人们对生物的认识从宏观发展到微观，科学家们对物种进化历史的依据 也从宏观上的形态发展到了微观上的分子，使系统发育分析研究进入了分子层次 研究，在分子水平上进行分析具有许多表型分析所没有的优势，所得到的结 果更 加科学，更加可靠。分子系统发育分析直接利用从核酸序列或者蛋白质分子序列 提取信息，作为物种的特征，通过研究物种分子序列，分析之间的关系，构建系 统进化树【11。 构建进化树是系统发育分析研究的主要目的之一，主要有以下四个步骤: ??建立序列比对模型 ?决定替代模型 ?构建进化树 ??进化树可靠性的评估 构建进化树的目的就是为了清楚明了的展现物种之间的系统发育历 史，一般 来说，进化树是一种二叉树【2】。所谓树，实际上就是一个无向非循环图。树的节 点代表物种:树的拓扑结构表现了各物种之间的进化关系;数的分支长度描述了 进化距离的时间。进化树有许多形式，一般的形式有:有根树和无根树;有根树 基于距离矩阵的进化树构建方法研究 就是有一个唯一的根节点，代表所有其他节点的共同祖先。它能够反映树的进化 层次，从根节点历经进化到任何其他节点只有唯一途径。而无根树是没有层次结 构的，它只说明节点之间的关系，没有关于进化发生方向的信息。 构建进化树是生物信息学研究中的一个重要领域，我们可以根据进化树 的拓 扑结构可以研究细菌、病毒和大型线粒体动物等各种物种以及各种物种的蛋白质 分子之间的进化历史。对构建进化树研究具有重要的意义，主要分为理论意义和 实际应用意义两个方面。从理论意义上来看，构建进化树有助于了解物种进化关 系，从分子水平角度为物种分类提供了可靠的证据。例如在探讨人类的起源，HIV 病毒的来源于进化关系等问题上都有许多成功的应用【31;从实际意义来看，预测 蛋白质，DNA分子的高级结构，以及基因表达过程，预测配体结构，辅助药物设计， 构建多序列比对先导树等方面构建进化树的工作起到了重要的作用。 在分子系统发育方法被发展出来以前，对于系统树的重建工作主要是通过研 究化石来进行的【4】。但是化石是如此的零散且不完整，只是大多数研究者转向形 态比较学和比较生理学的方法。通过后两种途径，进化学家已经得到有机体进化 关系的主要框架。然而形态和生理形状的进化与比较是非常复杂并且容易受到主 观判断影响的，以至于无法用以产生一幅进化历史的清晰图像。不同学者在构建 进化树的细节上几乎总是存在争议。而分子系统发育分析的进展大大改变了这种 局面，不论是细菌、植物还是各种动物，其DNA分子均由腺嘌呤 A 、胸腺嘧啶 T 、 胞嘧啶 C 、鸟嘌呤 G 这四种碱基组成，RNA分子与蛋白质分子也具有类似 性质。 因此通过分子系统发生学的方法可以 中是不可能做到的【5】。 然而从构建进化树算法来看，第 和空间复杂度过高的问题。因此，通 杂度尽量减少，这个问题依然是一个 1(2国内外研究现状 构建进化树的常用方法主要分为 于距离法首先需要得到一个反映序列 过建立在不同的优化原则和假设基础 于特征法，是并不需要规定距离度量 的碱基或者氨基酸顺序来构建进化树 所以基于特征法计算量要比基于距离 分析而言基于距离法是比较常用的方 硕t:学位论文 1(2(1距离度量 计算距离矩阵最简单的距离度量是P距离:除去两个序列的插入和删除的碱基 之后，单位长度上的碱基或者氨基酸差异率。但是由于p距离没有想到多种突变因 素，所以随着序列的长度增加，序列间的差异被低估的趋势，特别是在利用DNA 序列构建进化树这一方面【3l。因此，在DNA序列方面，由于只有四种碱基，只要 选择合适的核苷酸替代模型就可以得到更好的结果，一般的替换模型有: 的是PC距离 泊松校正距离 或T距离可以获得更准确的序列差异率。 随着近年的非比对序列分析的发展，引入了一些新的距离度量【13,141，如基于 欧式距离，马氏距离，Jaccard距离等等，这些是比较常用序列度量模型;以及 有序列所具有的根本属性之一，所以这种方法具有一定的普适性。基于非比对的 序列比对的基本思想是将分子序列转换成可以为现有的线性代数、概率统计、信 息论等数学工具可以处理和分析的对象，定义序列之间的距离定义。 编辑距离作为一种常用的度量方法，其基本思想已经在文本序列或生物序列 的分析中被广泛使用[18―20】。在某些应用中，需要对其进行归一化，目前 常用的归 一化方法有两种【211，一种是基于编辑路径长度，另一种是基于序列的长度。但是， 这两种定义方式均不能满足距离度量的三角不等性，文献【2l】定义了一种满足三角 不等式的归一化编辑距离，进一步发展了编辑距离理论。 1(2(2基于距离建树法 传统的全部基于距离法都是首先需要进行多序列比对，并选取适合的进化距 离度量模型，通过两两相似分析，得到了一个距离矩阵。得到距离矩阵以后，可 以利用基于距离法构建进化树。通常基于距离法有:不加权组对算术平均数的方 MethodArithmetic 法方法 Unweighted Pair―Groupusing Evolution 小进化法 Minimal Method ，邻接法 Neighbor―JoiningMethod，NJ 和 Fitch(Margoliash方法等122J。 ( 【231，用来解决分类问题的。使用该方法的前提条件是各分类群具有稳定且均等的 进化速率，在每一次分歧发生后，从共同祖先节点到两个分类单元间的分支长度 一样。利用UPGMA构建进化树时，首先用n个叶节点表示n个分类单元 序列 ， 每个分类单元自成一类，然后从距离矩阵中选择距离最小的一对分类单元聚为一 类，形成一个新的分类群，并计算这个新的分类群与其他分类单元之间的距离， 得到一个新的距离矩阵，重复上述过程，最终会得到一个以所有分类单元为叶节 点的系统进化树。 基(丁:距离矩融:的进化树构建方法研究 UPGMA算法的一个缺陷是假定所有分类群的进化速率是相同的，但是，实 际情况并不总是这样的，进化速率的变化容易导致UPGMA算法产生错误拓扑结 和Margolish承认了这种方法所得到的拓扑结构树有可能是不正确的，并重新考虑 其他构建进化树方法1241。 最小进化树 ME 是另一种基于距离的构建进化树方法，使用这种方法的基 本假设是在所有可能的拓扑结构中，树所对应的进化过程所需的插入，删除或者 替代次数最少，也就是说，系统进化树的分支之和最小。这种方法具有优良的统 计功能，但是由于该方法需要处理所有可能的拓扑结构，因此当物种数量足够多 的时候该方法处理起来就比较麻烦，计算量也比较大，并不太实用1251。 法【221，这种方法是一种快速的聚类方法，其基本思想是:在进行分类群合并时， 不仅要求待合并的分类群是相近的，而且要求待合并的分类群远离其他的分类群。 基于给定的距离矩阵，首先对每两个节点间的距离进行调整，即将每个分类群标 准化，从而形成一个新的距离矩阵;然后将距离最小的两个叶节点聚类一类，形 成一个新的分类;在树中增加一个父节点，并在新的距离矩阵中加入这个新的分 类，同时删除两个叶节点的分类。最后，新增加的父节点被看成为叶节点，重复 上面的过程，直到只剩下一个类为止。从利用邻接法得到的系统进化树来看，对 于两个聚在一起的叶节点，它们到父节点的距离并不一定相等。 假定X为所有分类群的共同祖先，如图1(1所示，可计算出星形树的分支长度 总和:SO 8 8 2 6 6 3 2 4 4 图1(1NJ树的状态变化 假设已将分类群单元l，2合并为一对邻居 图1(1右 ，则可以得到 S12。由于 任取两个分类群都有可能成为一对邻居，故此算法检查所有可能的组合并以 S值最 小的拓扑为起始状态进行下一轮的算法。这样直到所有分类群结合完毕。由 于建 树过程中仅仅关注拓扑结构，所以最后需要使用最小二乘法进行分支长度的 估计 【141 o 邻接法几乎优于其他传统的距离矩阵法，但是序列的表面差异并不能准确反 4 硕 :学位沦文 映进化距离，这是邻接法无法克服的缺陷，而邻接法仍然是当今被广泛使用的方 法之一。 1(2(3基于特征建树法 基于特征建树法一般有两种方法:最大简约法和极大似然法。这两种方法并 不需要利用距离度量建立距离矩阵，而是直接通过各物种序列的结构来构建 进化 树的。 最大简约法 imum 起来的，已广泛用于分子进化研究中对离散特征数据的系统进化树的构建。利用 最大简约方法构建进化树，实际上是对所有可能的拓扑结构树进行比较的过程。 对于某一个可能的树，首先对每个位点的核苷酸组成作出推断，然后统计每一个 位点的核苷酸最小替换数目。在整个树中，使得全部位点的最小核苷酸替代树之 和最小，这就是最大简约树。它与基于距离的最小进化法很相似，但是该方法并 没有使用距离测度来描述序列间的差异，而是对每个位点进行检查，从各种 可能 的拓扑中找到替换次数最小的那些结果。 在该位点上，不同的可能拓扑以及不同的祖先序列推断将产生不同的最小替 代数的记数。最大简约法对所有拓扑的在每一位点的情况进行计算，找到各位点 替代树总和最小的拓扑作为最优树。通常最大简约方法会产生一些具有不同拓扑 的等价结果，由于祖先序列信息的缺失，每一种拓扑都有可能是真实树，因此需 要通过严格一致树，多数一致树，自展一致树等方法来确保结果的唯一性【”1。 k k T A A G T G 基丁(距离矩阼的进化树构建方i !:研究 k T G A 图1(2MP法中三种可能拓扑的最小替换数计算 当分类群较少时，使用最大简约方法可以找到全局最优树;但是当分类 群增 多时，与最小进化树法等需要搜索所有拓扑的方法一样最大简约方法会遇到 性能 问题，因而通常采用分支限界、启发式搜索等搜索策略来找到局部最优解。 最大简约法较少涉及遗传假设，它通过寻求物种间最小的变更数来完成的; 而最大似然法对于假设的模型有巨大依赖性，计算量较大，但为统计推断提供了 基础。用最大简约方法搜索进化树的原理是要求用最小的改变来解释所要研究的 分类群之间的观察到的差异。 最大简约算法是通过比较很多进化树来选择最优树，其计算量相当大，而且 最大简约法是依据序列中的信息位点来获得进化距离信息，致使有些时候无法得 到好的推断结果i2引。 Likelihoodmethod [29】， 1981年，Felsenstein提出了极大似然法 imum 这种方法是基于统计学理论的进化分析算法，受到好多人的好评。基本思想是: 首先会产生具有极大似然率的拓扑结构树，然后对这些拓扑结构树进行比较，选 择出一个最好的拓扑结构树。只要构建进化树的替代模型是合理，正确的，那么 这种算法就一定能找到一个很好的进化树。极大似然法开始的时候只是针对DNA 序列的，后来通过改进也可以适用于蛋白质序列了。 最大似然法的基本假设包括:1(不同的性状进化是独立的;2(物种发生分歧后 进化独立，即不存在种间交流等因素的影响。位点的似然值是通过计算特定 的核 苷酸替代模型中某个位点每种可能被取代的概率之和得到的，因为前述的假设， 各位点的进化过程并无关联，故此将所有位点似然值相乘就得到系统树的似然值 【30】 o 以Felsentein替代模型为例计算位点的核苷酸替代概率，假定某位点的核苷酸 为i，分枝m上的核苷酸替代数为Vm时，核苷酸i在整个序列中的相对频率为gi， 该位点变为核苷酸j的概率为: 6 硕十学位论文 啪，《?二葚 最小进化树法对最优树的搜索有两种策略:一是对所有可能树的似然值对比， 找出最大值;二是对树的似然函数最大化，估算分枝长度，核苷酸频率，替代速率 等未知参数，从而确定树的拓扑结构131】。 最大简约法和极大似然法都是需要进行物种序列比对的，最大简约法主要考 察的是物种序列的多重比对结果，优化的进化树能够利用最少的离散步骤去解释 多重比对中的碱基差异;极大似然法需要考察的是所有物种序列的两两比对结果， 通过两两比对的差异决定进化树的拓扑结构和树的分支长度【321。 1(2(4传统建树方法比较 对近缘大种系进行系统发生分析时，本文所述的各种方法所构建的系统树往 往具有相似的拓扑结构。但在通常应用这些方法所构建的系统树会存在局部的拓 扑差异。UPGMA法在不同种系间进化速率有较大差异时往往会得出错误的拓扑 结构，而且当序列的差异较小时，由于距离矩阵中最小元素不唯一，产生的系统 树拓扑会随序列输入顺序变化而变化。NJ法的运算速度最快，但该算法在每次迭 代中仅搜索最近邻居配对，对其他可能的配对不加考虑，最终只生成单一的最优 树，可能会遗漏一些拓扑结构更合理的次优树【331。同时也有可能出现不 唯一的系 统树结果。通常的解决办法是在查找最优树时，使用NJ法预先生成一棵树，并以 此为基础查找相似的拓扑结构，以期待获得比NJ树更符合最小进化则的系统树。 ME法从所有可能的进化树中挑选树长最短的作为最优树，是基于距离的建树 方法中相对较好的方法。关于UPGMA与NJ法的结果不唯一的问题，可以通过类 似于MP法中一致树的多叉树形式来解决【341。不同的是，一致树的多叉树形式是 在建树过程中根据指定阈值一次结合多个分类群获得的。应当指出，距离法在从 序列数据生成距离矩阵时会丢失一些进化信息，事实上各种DNA替换模型以及距离 度量的改进都在试图将更多的生物学的背景信息加入到距离矩阵中。 而简约法是一种不依赖任何进化模型的统计方法。但简约树的分支完全决定 于所有重建祖先序列中的最小突变数，而突变是否按照事先约定的核苷酸最少替 代的途径进行是不得而知的，单一的突变图谱可能会得出不合理的错误结论。因 此，当序列在单位位点上核苷酸替代数相对较大，即是分类群序列间的亲缘较远 时，MP法则极可能得出具有错误拓扑的系统树。 最大似然法是一种能够完全利用序列数据的系统发生信息的建树方法，考虑 了所有可能的突变概率。但是最大似然法构建的系统树高度依赖于核苷酸替代模 7 基于距离矩阵的进化树构建办法研究 型的选取【351。不同的位点核苷酸替代速率不一致，在核苷酸替代一般模型中包含 了反映进化过程的参数。但并非替代模型越复杂，结果就越理想。拓扑的正确性 和支长的估计精确程度似乎无法同时被满足。此外在分类群较多时，最大似然法 的性能是所有方法中最差的。 1(2(5其他构建进化树方法 基于上述的构建进化树方法，包括传统的距离矩阵法和特征法，都是要建立 在序列比对的基础之上的，这就增加了算法的时间和空间的复杂度，为了解 决这 个问题，因此近几年来，一些研究者提出了不需序列比对，计算比较简单的方法。 由于基于特征法计算量要比基于距离法大很多，因此一般研究都是针对基于距离 61，这种方法是在模 矩阵法。例如，BoLiao等提出的模糊聚类进化树构建方法【3 糊数学理论的基础上提出来的。在使用模糊聚类法构建进化树之前，首先要得到 一个模糊相似矩阵，通常模糊相似矩阵中的各个值都是0到l之间的值。构造模糊 等。 模糊聚类法还可以分为传递闭包法，布尔矩阵法，直接聚类法，最大树 法等 等【3‘71。下面我们进行一一介绍。 传递闭包法的思想是:满足自反性和对称性的模糊相似矩阵R，首先R和R 自身合成，直到R变成了一个模糊等价矩阵R’，然后对R’中的值进行排序，重复 的值保留一个就可以了，然后逐个取尺’中排好序的值，用九代替，尺’中的值?A， 则把尺’得值改为1，其他改为0;这时，尺’中一行代表一类，重复如此，直到尺’中 排好序的值取完。这就可以构建一个进化树了。 传递闭包法对于物种小种系而言，是一个非常好的方法。但是在被聚类的物 种数目比较多时，所建立的模糊相似关系改造成模糊等价关系是相当麻烦 的，计 算量也是相当大的。 布尔矩阵法的基本思想是:满足自反性和对称性的模糊相似矩阵R，若要得 到每个物种在九水平上的分类，则可直接由相似矩阵R作其九(截矩阵m。显然m 为布尔矩阵。若m为等价矩阵，那么R也为等价矩阵，当然也可以分类;若m不 是等价矩阵，则凡在某一排列下含有上述形式的特殊子矩阵，此时只要将凡中上 述形式的特殊子矩阵的“0’’一律改为“l"，直到不再产生上述形式的特殊子矩阵 为止即可，则将m改造成一个等价的布尔矩阵，然后再分类。分类的思想跟传递 闭包分类的思想相同，得到的进化树也是一样的。 布尔矩阵法是在传递闭包法的基础稍微改进了一下，减少了一定的计算量， 从而构建进化树的速度也增快一些。 所谓直接聚类法，是指在建立模糊相似矩阵以后，不再去求传递闭包，也不 硕十学化论文 用布尔矩阵法，而是直接从模糊相似矩阵出发得到进化树，其基本思想如下:取 似类与等价类的不同之处就在于不同的相似类存在公共元素，只要将有公共元素 的相似类合并，即可得到允， l水平上的等价分类。取允:为矩阵中次大值，从R 中直接找出相似程度为A:的元素对将对应于A- l的等价分类所在的类合 并，将 所有这些情况合并后，得到Az的等价分类。依次类推，直到合并到成为一类为止。 直接聚类法与传递闭包法，布尔矩阵法所得的结果是一样的，而且直接聚类 法简便很多。 最大树法是为了解决在被聚类的物种数目比较多时，要把所建立的模糊相似 关系改造成模糊等价关系式相当麻烦的问题而提出来的。其基本思想如下:画出 以被分类元素为顶点，以相似矩阵R的元素dij为权重的一棵最大的树，取定允?【0， 1】，砍断权重低于允的枝，得到一个不连通的图，各个连通的分支便构成了A水 平上的分类。常用的最大树法有两种:Kruskal算法和Prim算法。 利用Kruskal算法进行模糊聚类分析的基本思想是:对于一个模糊相似矩阵R， 首先对R中所有的元素dij由大到小的顺序依次把这些元素用直线连起来，并标上 d“的数值。如果某一步使图中出现回路，就不画这一步，然后判断下一步，直到 所有元素连通为止。这样就得到了一棵所谓的最大树 最大树不是唯一的，但不影 响分类的结果 。然后，取定A值 O?A?1 ，把dij 允的连接去掉，互相连通的 元素归为一类，即可将元素分类。 Prim算法也是构成最小生成树的一种方法，是图论中的重要算法，把prim算 法应用到构建进化树是可行的。利用prim算法进行模糊聚类分析的基本思想是: 对于一个模糊相似矩阵R，先画出所有的顶点xi i l，2，„，n ，首先从任意 的顶点xi出发，寻找xi与它相邻的顶点xi距离最小，然后用直线把他们连起来，上 面标注它们的权值;然后寻找一个顶点与前已走过的顶点距离最小，然后用直线 把它们连起来，上面标注它们的权值，一直走下去，直到所有元素连通为止。这 样就得到了一棵所谓的最大树。然后，取定九值 O?A?1 ，把dij 九的连接去掉， 互相连通的元素归为一类，即可将元素分类。 最大树法所得到的结果与布尔矩阵法分类结果是一致的。最大树法比较直观， 也便于操作，适合推广应用。 1(2(6构建系统进化树的主要过程及相关软件 传统方法构建系统进化树的主要步骤如下: 1 建立序列比对模型; 2 决定替代模型; 9 基于距离矩阵的进化树构建方法研究 3 提出构建进化树方法; 4 系统进化树评估。 近几年来，构建系统进化树的步骤发生了相应的改变，具体步骤如下: 1 建立序列转换成数字特征模型; 2 提出构建进化树方法; 3 系统进化树评估。 从目前的构建进化树主要过程可以看出，现在构建系统进化树都是不需要进 行序列比对的了，这就大大降低了时间和空间的复杂度。 分子进化研究常用的一些统计分析方法，如系统进化树可靠性检验等，目前 已有的相关软件如下: Inference PHYLIP PHYLogenyPackage ，是I主I 统发生推断软件包，目前已经广泛应用于系统发育方向的研究。PHYLIP是一个免 费的软件，并且软件以源程序形式提供，可以在很多平台上进行运行。PHYLIP包 含了大约30个程序的软件包，有极大似然法，最大简约法，基于距离矩阵法和其 他一些非常有用的程序，这些程序基本上包括了系统发育的所有方面。 建的进化树进行可靠性检验和评估。 81。 和MEGA等13 1(3本文的主要研究工作 从上一节我们可以知道构建进化树的方法主要分为两大类:基于距离矩阵法 和基于特征法。其中，基于距离矩阵法以结构简单，良好的理论基础等特点得到 了广泛的应用。但是研究指出一些基于距离矩阵的构建进化树方法在某些情况下 会产生拓扑结构不唯一的进化树结果，而且是建立的序列比对的基础上，时间和 空间复杂度都是非常高的，所以，针对以上问题，本文提出了两种基于距离矩阵 构建进化树方法，这两种方法都是不需要进行序列比对，时间和空间复杂度大大 降低了，而且这两种方法比较直观，便于操作，计算量很少，非常实用。 本文提出的第一种基于距离矩阵的构建进化树法是在模糊聚类的传递闭包法 基础之上进行改进的，第二种基于距离矩阵的构建进化树法是在经典的k近邻算法 基础之上进行改进的。 1(4本文的章节安排 论文的章节安排如下: lO 硕1j学位沦文 第一章简要介绍了分子系统发生学与系统发育分析的背景，系统进化树的构 成以及构建进化树的理论意义和实际应用意义。然后介绍了在过国内外一些已有 的构建进化树方法的研究现状，并对各方法的缺点和优点做出来简要的分析;还 介绍了评估系统进化树的可靠性分析软件;最后讲述了本课题所完成的工作内容。 第二章介绍基于图形表示的相似距离矩阵计算。 第三章提出一种改进的基于模糊聚类的传递闭包距离矩阵法构建进化树方 法，详细描述算法的思想以及具体步骤;并通过实验数据验证方法的可行性。 第四章提出了一种改进的基于k近邻距离矩阵法构建进化树方法，并详细描 述算法的思想和具体过程;最后通过实验数据验证这种方法的可行性。 结论最后总结本文并展望未来，并对计算分子生物学的发展趋势进行分析和 预测。 基丁(距离矩阵的进化树构建厅法研究 第2章基于图形表示的相似距离矩阵计算 在第一章中提到基于距离矩阵法是一种比较常用的一类方法。但是传统的基 于距离矩阵法是建立在序列比对的基础上的。这一章会讨论了基于本文采用的不 需要序列比对的图形表示的相似距离矩阵计算，它主要包括:DNA序列的图形表 示，基于图形的序列相似性分析，和构建相似距离矩阵。 2(1DNA序列的图形表示 用四种字母表达的DNA序列，是DNA序列的传统形式，它在存储和提供计算 机进行快速分析等方面具有不容争议的优点，因此得到了广泛应用。但它也存在 严重的缺陷。图形表示的研究正是从克服它的缺陷开始的。它的缺陷之一是忽视 了人脑在模式识别方面的强大能力。那么利用图形来表示生物的原始序列可以使 我们更加直观的观察生物序列。他们使用图形表示的基本思想是:先将序列转化 为图形表示，然后根据图形表示构造矩阵，利用与矩阵相关的不变量来分析生物 序列的相似性等问题，下面我们就介绍几种典型的DNA序列的图形表示方法。 1 示为一条平面或者空间中的曲线一G曲线和H曲线。G曲线是一种5维空间表示， 其中4个坐标方向分别为四种核苷酸，剩下的一个方向表示DNA序列核苷酸的位 置，但是这一方法不能实现可视化【391。改用两个坐标轴的四个方向表示四种核苷 酸似一?形;G一(距;C一?E;丁一S聊，另一个方向表示核苷酸的位置，这时，曲 线变成3维空间曲线，这就是H曲线。 Game Jeffrey于1990年提出的CGR Chaos 图形表示和数学表达相结合的方法。这种方法基于混沌理论，将序列对应于一张 揭示其固有分形结构的图，不同的DNA序列在图中显示出不同的外形 如山、云、 珊瑚等等 ，它在几何上得到了应用，还在处理基因组分析问题上显示了很好的结 果„。 +x轴方向单位向量为C，(x轴方向单位向量为G，+y轴方向单位向量为T，(y轴方 向单位向量为A。 2 l 2J:+x 轴方向单位向 994年A(Nandy给出的二维图形表示为【4 量为G，(x轴方向单位向量为A，+y轴方向单位向量为C，(y轴方向单位向量为T。 3 l 向单位向量为A，(x轴方向单位向量为C，+y轴方向单位向量为T，一y轴方向单位 12 硕十学位论文 向量为G。 这三种表示法均以原点为初始点，每增加一个碱基就按照所给出的方向增加 一个单位向量。三种方法都可能出现图形上的交叠现象 退化 ，例如在 Gates GA，GAG，GAGA，GGAGA的图形将很难区分。 y 。 y I ? C X 0 G ― X 1r A ? ??T y - T?? O A ―- X I 一 G ? ’C 图2(1二维图形的三种坐标 为了避免上面出现的图形退化现象，郭晓峰【44】和刘亚春【45J改进了上面的坐标 种核苷酸用二进制数表示:A 00，G 01，C l0，T 11，这样可以得到一个DNA 地图【461。廖波也提出了几种二维图形表示【47,48】，很好地解决了退化问题。 我国著名理论物理专家张春霆院士也提出了一种DNA几何图形表示一Z曲 线，Z曲线是表示DNA序列的一个等价三维空间曲线。通过对Z曲线的研究来对基 因组序列进行研究是一种几何学的途径。利用z曲线研究了真核和原核基因组中 若干重要问题，这样的思路是可行的H91。 考虑长度为N的单链DNA序列，该序列的z曲线包含一系列的点P。肼p:„p?， 基丁(距离矩阵的进化树构建方法研究 相应的坐标 矗，只，z。 ，n 0，1，2，(((N， I矗 4+q 一 e+丁。 2(1 只 以+C 一 q+丁。 矗，,，Zn?【-N，N】，n 0，l，2，((('N I乙 4l+乙 一 q+c((， 从lNn这个子序列中四种碱基各自出现的次数分别用4，q，e，,表示。 碱基沿序列的分布。当嘌呤碱基的数目多于嘧啶碱基时，瓦 O;否则，‘ 0; 两者相等时，矗 O。 示强氢键 A+T ,弱氢键 G+C 碱基沿序列的分布。当序列中弱氢键碱基多于强氢键 碱基时，z。 0;当序列中弱氢键碱基少于强氢键碱基时，z。 0;当序列中弱 氢键碱基等于强氢键碱基时，z。 0。 一彳， O，l，0 一C， 0，0，1 一G， 1，1，1 一r。廖波等对四种碱基赋予 J。 不同的向量坐标提出了一系列三维图形表示【53~57 另外廖波教授在后来的研究中，于2006年又提出了一种高维的表示【5引。所有 的DNA序列的高维表示都具有类似的特征，即从几何角度出发，找到一个适当的 对应法则把DNA的四种碱基对应到高维空间中。 原则上说，生物信息方面的许多问题都可以通过图形表示来解决，这种 别开 生面的研究思路已经得到了国内外一致的好评和认可。可以预期，用图形表示方 法的研究有一个广阔的发展空间。 2(2基于图形的序列相似性分析 基于图形表示的矩阵不变量方法被用于DNA序列的相似性分析。其思想是把 DNA序列转化成图形表示，利用图形构造矩阵，再利用矩阵不变量 如最大特征 值，最大行和，矩阵的迹等 来比较生物序列的相似性。 利用不变量来刻画和比较生物序列的优势在于不变量的刻画和比较非常简 单，物种序列之间的比较被转换成了生物序列对应的数学描述的序列比较。然而 已有的方法在用不变量来刻画和比较生物序列时同时会伴随某些结构方面的信息 丢失。所以如果能找到合适的图形表示以及具有生物意义的更好的不变量来比较 生物序列是一个值得进一步研究的课题。 矩阵来表示一个序列，这样序列之间的比较就转化为矩阵之间的比较，而且如果 14 硕上学位论文 矩阵是数值矩阵，就可以选择一个适当的不变量进而把矩阵之间的比较转化为这 些不变量之间的比较，这样就把复杂的问题简单化了【61】。 矩阵，压缩矩阵。下面简单介绍下这几种矩阵的构造:这里我们以二维图形 为例， 第i点和第j点的坐标为 薯，乃 和 x，，y， 。 1(E矩阵:其元素是曲线上两个碱基对应点的欧式距离。 e f，J ? 薯一号 2+ ”一乃 2 2(2 2(M,M矩阵:其元素是曲线上两个碱基对应点的欧式距离与它们之间 存在的 单位线段的比。 聊 f'舻迎i粤 丛 2(3 I J―j 3(L,L矩阵 也叫D,D矩阵 :其元素是曲线上两个碱基对应点的欧 式距离与 它们之间的图论距离 曲线上两点之间的线段长度之和 的比。L,L矩阵的主对角 线元素为0，所有元素小于或等于l。 砸，舻迎署生生丛 2(4 ?P 后，后+1 4(高阶矩阵:‘L,‘,是L,L矩阵的每个元素取k次幂得到的矩阵。 不变量来刻画序列。因为随着序列长度的增长，矩阵的维数会相应的增加，而最 大特征值的计算复杂度也会有相应增加。因此，一些学者在提出新的DNA序列的 图形表示方法的同时也对矩阵不变量做了进一步研究。 郑文新‘651在z曲线上计算图形的中心点 一x,一y，; 来刻画序列的曲线分布， ; 专喜,，歹 专喜见， 三 专喜乙 c2匀 然后构造一个三维协方差矩阵2(6，计算协方差矩阵的特征值，特征 向量，用 它们来度量序列的相似程度。 o H n 6碍6 ? o体。仃0乒 仃胛 ，P，q x，y，z 2(6 oa o珂。口 廖波和王天明等给出了一些图形表示方法[47,53-57,66】，将生物序列 转化成图 形，然后利用图形构造矩阵，再利用矩阵不变量一最大特征值，来比较生物 序列 的相似性。 基f距离辩i阵的进化树构建厅法研究 李春首先从数学角度分析矩阵的最大特征值九的取值范围， M 2(7 三四峪九?、,堕II IIF lI M M 2(8 ll耐 ?i,1嘞，II llF ??“I,12 然后给出一个ALE(index作为矩阵的不变量来刻画序列，此不变量的计算复杂 度明显小于九[671。 z吲咖卉1Z刀 疗 2(9 1四Ilm，+?导四, Y 张玉森‘681考虑矩阵元素的行平均值，在2DD曲线上定义了一个新的矩阵不变 量一inv。他的不变量在计算复杂度方面上优于李春的ALE(index。 2(3构建相似距离矩阵 在本文构建相似距离矩阵实际上是构建模糊相似矩阵。模糊聚类分析的方法 很多，其中用的较多的有传递闭包法，最大树法和动态直接聚类法等。这些聚类 法有个共同点，这是聚类依据是由原始数据所构造的模糊相似矩阵。聚类正确与 否，完全取决于模糊相似矩阵。尽管模糊相似矩阵在模糊聚类分析中起决定性作 用，但遗憾的是，模糊相似矩阵的构造方法不唯一。据不完全统计，构造模糊相 似矩阵的方法有13种之多。如:海明距离法;欧式距离法;切比雪夫距离法:绝 对值倒数法;绝对值指数法;指数相似系数法:兰氏距离法;数量积法;夹角余 弦法;相关系数法;最大最小法;算术平均最小法;几何平均最小法【691。我们以 i和(j分别代表两个物种，k代表物种的第k个特征，c为一个常数为例， 对上述方法 详细介绍一下: 海明距离法:吩 l―c?l靠一?I 2(11 ―?―――一 欧式距离法:吩 l―c、,? ?-4 2 2(12 切比雪夫距离法:吩5l-c纠m„ax。Ix;I一?l 2??13 鲥酬燃中 南毫件 (E 2(14 16 硕‘L学位论文 绝对值指数法:, exp -c -'I嘞-xj,I 2(15 上 l 指数枞系数法:勺 去扣卜言 等 2】 2(16 。其中文 t丽 x,k-xk 2，主 三n羔i l靠 2(17 兰氏距离法: 2(18 iI 吩 l,管II?xfk+-啄xjk c l j， 数量积法: 勺 2(19 ? 1?J; ，??????』、???【 。?蹦 ??? ’ 2(20 J m rtl 夹角余弦法:, 1―尘皇―一 ? ??2 ??2 ? ?一一xi xj。一i 七 l 相关系数法:勺 2(21 其中i 去善?，i 去善? 2(22 ?min xik，? 最大最小法:吩 专L――一 2(23 ? xj:k，xjk ?min xfk，xjk 算术平均最小法:勺 寺b―――一 2(24 去? ?+? ?min xd,，? 几何平均最小法: 铲专鬲 2(25 各方法都有优缺点，比较常用的方法有两种是欧式距离法和夹角余弦法;欧 氏距离法事计算两个物种的欧式距离，如果两个物种的欧式距离较小就认为这两 17 基丁|距离矩阵的进化树构建疗法研究 个物种比较相似;夹角余弦法，计算物种之间夹角所对应的余弦值，如果两个物 种的余弦值较大就认为这两个物种比较相似。 2(4，J、结 本章主要介绍了基于图形表示的相似距离矩阵计算，主要包括:DNA序列的 图形表示，基于图形的序列相似性分析，和构建相似距离矩阵。详细介绍了 DNA 序列的图形表示的主要常见的几种图形表示，利用图形来表示生物的原始序列可 以使我们更加直观的观察生物序列;用图形表示方法的研究有一个广阔的发展空 间。详细介绍了基于图形的序列相似性分析研究现状和研究成果，找到合适的图 形表示以及具有生物意义的更好的不变量来比较生物序列是一个值得进一步研究 的课题。最后详细介绍了构建相似距离矩阵的13种距离度量。 18 硕十学位论文 第3章基于改进的模糊聚类传递闭包建树法 本章介绍一种基于改进的模糊聚类的传递闭包距离矩阵法。该方法是建立在 不需要序列比对的基础上提出的。该方法比较直观，便于操作，计算量很少，非 常实用。本章首先阐述了模糊聚类的传递闭包法，然后详细阐述改进的模糊聚类 的传递闭包法的基本思想以及具体步骤。最后给出了一个距离矩阵，根据这个距 离矩阵做实验，用实验结果来检验构建进化树的可行性。 3(1模糊聚类的传递闭包 模糊聚类法是在模糊数学理论的基础上提出来的【7们。利用相似分析构建的距 离矩阵R一般只满足自反性和对称性，I!IJR是相似矩阵，需要将它改造成模糊等价 矩阵。 所谓模糊等价关系: 设R?F UxU ，如果满足: 1 自反性R_DI或R u，u l; 2 对称性RT R或R u，v R v，u ; 3 传递性R三R2或R u，V ?九，R v，W ?九jR u，w ?九 则称R为U上的模糊等价关系。 根据模糊矩阵，只是一个模糊相似矩阵尺’，不一定具有传递性，即尺’不一定 是模糊等价矩阵，为了进行分类，还需要将R’改造成模糊等价矩阵。为此，采用 平方法求出尺’的传递闭包t R ，R t R 为模糊等价矩阵，然后对模糊等价矩阵中 的值进行排序，重复的值保留一个就可以了，然后逐个取R中排好序的值， 用允代 替，R中的值?A，则把R得值改为l，其他改为0;这时，R中一行代表一类， 重复如此，直到R中排好序的值取完，这样的聚类方法，称为传递闭包法。 3(2新方法的基本思想 通过上一节中传递闭包法的介绍我们可以看出，传递闭包法是在原有的相似 矩阵上进行传递闭包，然后进行聚类。一般距离法构建进化树中的相似矩阵描述 的是物种间的距离值越小，相似程度就越高，为了能够在矩阵中体现距离值越大， 相似程度高，提出了一种新的方法，这种方法就是在原始的非相似矩阵的基础上 变换成一个可以反映物种之间相似程度高的相似矩阵，如果两物种的距离越 大， 相似程度就越高;然后在这个新的相似矩阵上进行传递闭包，构建进化树。 19 基于距离矩阵的进化树构建方法研究 3(3新算法步骤 新算法的步骤如下: 1 给定一个非相似矩阵R，按照下面两个小步骤对R进行处理，使R变成一个 相似度高的相似矩阵R’; 1 原始矩阵中距离d。利用下列的公式转换成新的相似距离d:;; 他 Iifi j 3(1 其中i，j，k分别代表各物种，d砖A d# mined琅，办 ，“vd# d膳，九 。 2 把新的相似距离d;利用下面公式转换成相似度更高的相似矩阵R’，相似 距离用勺表示; ?? ( 铲娶螋 1 2(3 。i乙产n。【d:t+dlt] 2 R’是一个相似距离矩阵，然后利用传递闭包法求出R，即利用两两合成， 平方法求出R，这时R就是模糊等价矩阵。 3 从R中选出值，对这些值进行排序，得到了分区序列:冗a1，兀a2，„，兀a七 利用分区序列，对物种进行聚类; 4 直到分区序列值取完，一棵进化树构成了。 3(4实验及结果分析 本章用到的实验数据是廖波提出的一种基于DNA序列的3D图形表的的一种 不相似距离矩阵的论文中【571采用的数据，见表3(1。 硕一卜学位论文 ! 苎皇苎詈皇霉暑詈詈!詈暑摹(, ii詈詈鲁詈 !詈 詈 暑 詈詈 ! 皇 詈葛皇皇皇!皇皇暑!詈穹詈詈詈 毫詈毒!皇皇詈皇詈 毫 毒詈!毫皇穹皇皇!!兰!皇暑暑詈!詈皇詈詈詈詈毫詈暑詈!詈詈墨 表3(1方法1中编码序列的不相似矩阵 ChiGot L(CatM(fasM(fusM(mu! Port S(sci Species Hyi M(Syl T(Syr Chi 0 0(01070(07250(26490(08270(12540(11550(18ll0(05370(28020(3299 GOr 0(0618 0 0(25420(0720(11470(10480(17040(043 0(26950(3192 0 0(19240(0102 0(043 Hyl 0(0529 0(10860(01880(20770(2574 L(Cat 0 0(18220(13950(14940(08380(2112O(01530(065 M(fas 0 0(04270(03280(09840(029 0(19750(2472 M(fus O 0(00990(05570(07l 7 O(15480(2045 M(mul 0 0(06560(0618O(16470(2144 M(Syl 0 0(12740(099l0(1488 Port 0 0(2265 0(2762 S(sci O 0(0497 T(Syr 0 这是原始数据矩阵，从这个矩阵中使用新算法的公式3(1得到相关距 离矩阵 D。，如式3(3所示;和利用算法中的公式3(2得到新的相似度高的距离矩 阵尺’，如 式3(4所示。 l 7(86414(5448(22429(518 1(0894 9(55158(41224(973715(27213(553 1(0894l 7(305715(26l7(64489(28159(22328(67679(719716(03814(5 7(8647(30571 17(5081(27125(94285(3538(70722(129218(56l17(93 14(54415(26117(508l 16(85213(03714(2495(601415(8991(1079 2(6605 8(22427(64481(271216(852l 4(91254(56137(91082(187217(92517(396 3(3 D’ 9(5189(28155(942813(0374(9125l 1(13224(92745(872914(04813(678 9(55159(22325(35314(2494(56131(1322l 5(622l5(374615(306 14(954 8(41228(67678(70725(60147(91084(92745(622ll 7(62446(14335(5553 4(97379(71972(129215(899 2(18725(87295(37467(6244l 16(8916(028 15(27216(03818(56l1(107917(92514(04815(3066(143316(89 l 2(7535 13(55314(5 17(932(660517(39613(67814(9545(555316(0282(7535l l 0(974510(741860(496670(732130(739950(752020(629630(788410(485880(50633 0(9745ll 0(476620(755430(735440(756990(61374 0(46654 0(76746 0(8124l 0(48646 0(741860(767461 0(390300(968740(761840(798600(588080(914860(383050(401ll l 0(496670(476620(39030l 0(386900(470l 0(456390(6l 3580(365480(968980(96l 24 0(732130(755430(968740(38690l 0(786730(823840(60093 0-379640(39794 3(4 0(91416 R’20(739950(735440(761840(4710l0(78673l 0(96325 0(455370(48192 0(706680(75680 0(752020(75699 0(823840(96325 0(798600(45639 l 0(674850(7960l0(441680(46686 0(629630(6l 374 l 3580(600930(70668 0(588080(6 0(67485 l 0(570540(59l 540(62354 0(7884l0(8l 24l l 0(9l 4l 6 0(94860(36548 0(756800(7960l 0(57054l 0(358730(377l 6 0(485880(466540(383050(968980(379640(455370(44l 680(59l 540(35873l 0(95346 0(506330(486460(40lll 0(961240(397940(481920(466860(623540(377160(95346l 2l 基于距离矩阵的进化树构建方法研究 然后对尺’进行传递闭包，算出了尺“，尺”，尺”，尺“6，如式3(5， 3(6，3(7，3(8所示。我 们可以直接看出尺“6是R’的传递闭包尺，如式3(9所示。 0(706680(81241 l 0(9745l0(788410(613580(788410(75680(78841 0(591540(62354 0(9745ll O(812410(613580(812410(761840(796010(706680(812410(591540(61374 l 0(96874 0(91486 0(788410(8124l 0(58808 0(79860(823840(?0668 0(588080(58808 O(613580(613580(588081 0(600930(613580(613580(623540(570540(968980(96124 0(78841 0(968740(60093l 0(706680(914860(591540(60093 0(81241 0(823840(82384 3(5 尺“: 0(75680(761840(79860(613580(82384l 0(963250(706680(7960lO(591540(62354 0(788410(796010(823840(613580(82384 l 0(706680(823840(591540(62354 0(96325 0(706680(706680(706680(623540(706680(706680(70668l 0(706680(623540(62354 0(812410(812410(914860(570540(914860(796010(823840(70668l 0(570540(57054 0(57054 0(591540(591540(588080(968980(591540(591540(591540(62354 l O(96124 0(623540(613740(588080(961240(600930(623540(623540(623540(570540(96124l 0(81241 l 0(9745l0(8124l0(623540(8124l0(7960lO(8124l0(70668 0(623540(62354 0(9745ll 0(812410(613580(8124lO(812410(812410(706680(812410(623540(62354 0(70668 0(812410(81241l 0(623540(823840(823840(82384 0(914860(623540(62354 0(623540(613580(62354l 0(623540(613580(623540(623540(623540(968980(96124 l 0(823840(823840(70668 O(812410(8124l0(823840(62354 0(914860(623540(62354 3(6 R“: 0(7960l0(8124l0(823840(613580(82384l 0(963250(706680(823840(623540(62354 0(823840(623540(823840(96325l 0(706680(823840(62354 0(8124lO(8124l 0(62354 0(706680(706680(706680(623540(706680(706680(70668l 0(706680(623540(62354 0(914860(623540(914860(823840(823840(70668l 0(623540(62354 0(8124lO(8124l 0(623540(623540(623540(968980(623540(623540(623540(623540(62354l 0(96124 0(961240(623540(623540(623540(623540(623540(96