基于距离进化树的构建算法地地研究

《基于距离进化树的构建算法地地研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、国内图书分类号：TP301.6U.D.C.:681.3.06工学硕士学位论文基于距离的进化树构建算法研究硕士研究生：于季芝导师：郭茂祖教授申请学位：工学硕士学科、专业：计算机科学与技术所在单位：计算机科学与技术学院答辩日期：2007年7月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP301.6U.D.C.:681.3.06DissertationfortheMasterDegreeofEngineeringDISTANCE-BASEDPHYLOGENETICMETHODRESEARCH

2、Candidate:YuJizhiSupervisor:Prof.GuoMaozuAcademicDegreeAppliedfor:MasterofEngineeringSpeciality:ComputerScienceandTechnologyAffiliation:SchoolofComputerScienceandTechnologyDateofDefence:July,2007Degree-Conferring-Institution:HarbinInstituteofTechnology哈尔

3、滨工业大学工学硕士学位论文摘要进化树是描述物种进化顺序和进化关系的一种拓扑结构。构建进化树在生物学中有重要的应用，研究高效准确的构建进化树算法有实际的应用价值。本文针对进化树构建问题进行研究。进化树构建问题是一个NP完全问题，因而构建算法都是启发式的。通常使用的方法分为三大类：(1)距离法，(2)最大简约法，(3)最大似然法。本文使用基于最大似然法的距离法构建进化树，主要分为两个阶段：首先估计所有分类群之间的进化距离，只有序列进化距离越精确，构建的进化树才会越准确；然后基于这些距离值之间的关系构建进化树

4、。本文工作主要包括以下两个阶段：在第一阶段，对距离估计方法和最大似然法进行了研究，改变了传统的进化距离估计方法，把序列比对由两个序列比对扩大到多重序列比对；利用基于quartet的最大似然法对进化模型进行优化并使用最小二乘法快速重构所有可能的quartet拓扑结构，并优化其分支长度，对两两序列间距离进行估计，为进化树的构建提供了更加准确的距离矩阵。在第二阶段，主要对邻接法构建进化树进行改进，改进工作分为两部分：一是针对在第一阶段得到的距离矩阵并不总是满足可加性的问题，引入了距离的方差和协方差，采用加权的

5、计算公式更新距离矩阵，使算法构建的拓扑结构更加准确。二是改进了邻接法的贪心特性，由于邻接法每次只聚合速率校正距离最小的两个分类单元，进而导致整个体系的偏差，实验证明速率校正距离最小的配对并不一定是在真实的进化树中进化距离最近的，基于此，改进算法每次聚合速率校正距离满足“neighbor”的两个分类单元，使算法不总是搜索分支长度之和最短的进化树，很大程度减少了这种体系偏差对真实进化关系的影响，并通过实验验证了该算法的准确性。最后，基于以上的研究成果，实现了一个进化树构建系统。关键词进化树；距离法；邻接法；

6、最大似然法-I-哈尔滨工业大学工学硕士学位论文AbstractPhylogenetictreeisakindoftypologicalstructurefordescribingthesequenceandrelationshipofspeciesrevolution.Itissignificanttoconstructphylogenetictreeinthebiologyfieldwhoseefficientandprecisealgorithmscouldyieldtoagreatdealofpr

7、acticalvalue.WestudytheproblemofconstructingPhylogenetictreeinthepaper.ThisproblemisaNPcompleteproblemwhosealgorithmsareallheuristic.Thereareusuallythreemainmethodsfortheproblem:(1)based-distance,(2)maximumparsimony,(3)maximumlikelihood.Wewillmergemaximu

8、mlikelihoodmethodtothebased-distancealgorithmprocessofconstructingphylogenetictreeonthebasisofadvantagesofbothbased-distanceandmaximumlikelihoodmethods.Therearetwomainphasesintheprocess:firstly,weestimatephylogeneticdistan