NJ进化树构建方法的改进及其应用

《NJ进化树构建方法的改进及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要分子系统发育分析是生物信息学中的重要研究领域，它的主要研究手段是从一组同源的DNA或蛋白质序列出发，计算各个序列之间的进化距离，从而得到反映物种进化关系的进化树。进化树通常是一棵二叉树：树的叶节点，代表了某个具体序列；树的拓扑结构表现了各物种之间的亲缘关系远近；树的分枝长度刻画了进化距离的大小。构建进化树的方法主要分为三类，即距离矩阵法、最简约方法和极大似然法。虽然距离矩阵法以结构简单、具有良好的理论基础等特点获得了广泛的应用，但是这种方法在某些情况下会产生两个或多个拓扑结构不同的“等价”进化树，也就是文献上所说的“tiedtrees"。邻接法(Neighbor—Joining

2、，以下简称NJ)是一种比较常见的距离矩阵法，也存在“tiedtrees”问题，尽管其设计目标是对同样的序列数据产生与输入顺序无关的唯一进化树。对于NJ法的“tiedtrees"问题，大多数流行的分子系统发育分析软件并没有进行有效的处理，通常仅根据算法实现方式的不同，只给出其中一种进化树的拓扑结构。·本文详细分析了NJ法产生“tiedtrees”问题的原因，提出并实现了一种改进邻接法(ImprovedNeighbor—Joiningalgorithm，以下简称INJ)。INJ是NJ的一种扩展，而NJ可以看作INJ的一个特例。在迭代计算过程中，NJ总是任意选取两个具有最小速率校正距离的

3、序列或种群进行合并来生成新的分类单元，而INJ则允许把多个(目前限制为3个)具有相同最小速率校正距离的序列或种群进行合并，因此它所产生的进化树可能是多叉树。在NJ树不唯一时下，INJ树通常是一棵唯一的多叉树；而在NJ树唯一时下，INJ树则与NJ树完全一致。因此，INJ法较好地解决了NJ法的“tiedtrees”问题。此外，本文还实现了一个包含完整INJ法和传统NJ法的分子发育分析软件叫ulti—Tree。该软件是一个基于Microsoft．Netframework2．0平台构建的客户端应用，其中包括：多序列比对和编辑、距离矩阵计算、多种进化树构建方法和显示模式。Multi—Tree

4、软件系统采用了基于插件的程序结构，从指定位置的一组程序集中动态获取系统的界面元素与业务逻辑，具有良好的扩展性与可维护性，还可支持多语言的界面显示。关键词进化树；二叉树；多叉树；邻接法；距离矩阵Abstract曼蔓曼曼曼曼曼曼曼曼詈曼曼皇．ml—mll曼!量曼曼!曼曼曼曼曼曼!曼!曼曼曼曼曼曼曼曼暑曼曼曼曼!曼!曼曼曼曼!曼!曼!曼曼曼AbstractMolecularphylogeneticanalysisisoneofthemostimportantfieldsofBioinformatics，hemaintaskofwhichiStoreconstructaphylogenet

5、ictreefromagroupofhomologousDNAorproteinsequences，bycalculatingtheevolutionarydistancesbetweenthem，toshowtheirevolutionaryrelationship．Usually,aphylogenetictreeisabinarytree，inwhichtheleafnodesstandforthespeciesortheorganisms，thetreetopologyindicatesthephylogeneticrelationship，andthelengthofbr

6、anchesfigureouttheevolutionarydistance．Therearethreemaintypesofmethodstoreconstructphylogenetictrees：distancematrixmethod，parsimonymethodandlil(elihoodmethod．Distancematrixmethodshavewideapplicationsbecauseofitssimplicityandsolidtheory,butsomeofthemmayproducemultiplephylogenetictrees("tiedtree

7、s”)givenasinglesetofhomologoussequencesincertaincases．OneofsuchmethodscommonlyusedisNeighbor-Joining(NJ)，whichmayalsohavetheproblemof“tiedtrees’’althoughdesignedtoproduceasinglephylogenetictreeunrelatedtoinputordersofsequences．Forthepro