基于层次聚类进化树的构建算法地地研究

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

1、基于层次聚类的进化树构建算法研究摘要系统发育分析是生物信息学研究的重要领域之一，它主要研究同源的DNA或蛋白质序列，对这些序列进行进化分析，从而得到能够反映蛋白质序列或者DNA序列之间进化关系的系统发育进化树。系统发育进化树的研究已有很长的历史了，它在分子进化与系统发育研究中起到了重要的作用。系统进化树直观的反映了生物进化的关系，有助于了解生物进化历史和进化机制。进化树构建方法从不同的角度可以得到不同的分类，可以把进化树构建算法分为两类：基于算术聚类方法和基于最优搜索方法。由于基于最优搜索方法常常

2、要比基于算术聚类方法慢得多，所以基于算术聚类方法得到了广泛地应用。．·基于算术聚类方法中层次聚类方法应用于进化树构建方面最为常用，但是传统的基于算术聚类方法中都是建立在序列比对的基础上的。所以本文为了解决这个问题，提出了两种新的基于层次聚类方法，这两种都是不需要进行序列比对，而且算法的计算量小，容易实现。两种新方法是：基于横纵建树法和基于调整权重的自组织映射建树法。基于横纵建树法也是一种基于距离矩阵建树法。它是在距离矩阵基础上进行的，结合横向找点，纵向找边的思想得到一棵二叉树，在此基础上进行聚类。

3、基于调整权重的自组织映射建树法是建立在自组织映射网络基础上提出来的。自组织映射网络既可以应用于分类和聚类，也可以应用于进化分析和进化树的构造。但是当自组织映射网络应用于进化分析和进化树构造的研究中，算法比较复杂，而这种方法降低了算法的复杂度。这种方法与基于距离矩阵建树法比较，它不用进行相似分析构造距离矩阵，而是直接得到一颗最小权重二叉树，然后通过聚类进行进化树构建。评估构建进化树的方法可行性，通常是采用PHYLIP软件中的Neighbor．exe程序来评估的，通过做实验来验证算法的可行性。关键词：

4、构建进化树；层次聚类；距离矩阵；自组织映射II硕士学位论文L．L．．IIAbstractMolecularphylogeneticanalysisisoneofthemostimportantfieldsinbioinformatics，whichmainlystudieshomologousDNAorproteinsequencesandtheevolutionanalysisforproteinsequencesorDNAsequences．Sothephylogenetietreeisobt

5、ainedwhichisreflectedevolutionaryrelationshipofproteinsequencesorDNAsequences．Theresearchofphylogenetictreereconstructionhasalongtimehistory；itplaysamoreandmoreimportantpartinmolecularevolutionandphylogenetieresearch．Thephylogenetictreereflectsthesequ

6、enceofthespeciesevolution，ithelpsUStofindthehistoryandevolutionmechanismofspecies．Phylogenetictreeconstructionmethodscanbeobtaineddifferentcategoriesofthedifferentviews，SOwecandividethephylogenetietreeconstructionmethodsintotwocategories：basedonmathem

7、aticsclusteringmethodandbasedontheoptimalsearchmethod．Asbasedonoptimalsearchmethodsaremuchslowerthanbasedonmathematicsclusteingmethods，basedonmathematicsclusteringmethodhaswideapplications．Thehierarchicalclusteringmethodofbasedonmathematicsclusteringm

8、ethodisagenerallymethodinphylogenetietreesconstruction，butthetraditionalmathematicsclusteringmethodisbuilttobaseonsequencealignment．Therefore，inordertosolvethisproblem，weproposetwonewmethodsbasedonthehierarchicalclustering，bothofwhicharewithou