多叉进化树构建方法的研究与实现

多叉进化树构建方法的研究与实现分子系统发育分析是生物信息学中的重要研究领域,它的主要研究手段是从一组同源的DNA或蛋白质序列出发,计算各个序列之间的进化距离,从而得到反映物种进化关系的进化树。进化树通常是一棵二叉树:树的叶结点,代表了某个具体序列;树的拓扑结构表现了各物种之间的亲缘关系远近;树的分枝长度刻画了进化距离的大小。构建进化树的方法主要分为三类,即距离矩阵法、最简约方法和极大似然法。其中,距离矩阵法以结构简单、具有良好的理论基础等特点获得了广泛的应用。但是,研究指出一些基于距离矩阵的建树方法在某些情况下会产生拓扑结构不惟一的进化树结果,即进化树的具体拓扑结构会根据同源序列输入算法的顺序不同而发生变化。不加权算术平均组对法(UnweightedPair-GroupMethodusingArithmeticaverages,以下简称UPGMA)是一种比较常见的距离矩阵法,该方法也存在上述问题。虽然该方法被设计为针对同一组序列数据产生惟一的进化树结果,但是可以证明在算法迭代过程中,如果距离矩阵中出现最小元素不惟一的情况,则算法产生的进化树拓扑结构是随着序列输入顺序的不同而变化的。这一现象为系统发育分析结果的解释带来了困难——在多个进化树结果中,显然只能有一棵进化树反映了真实的物种进化关系,但是在出现多个结果时UPGMA并不能判断哪一棵树的拓扑结构是正确的。并且大多数流行的分子系统发育分析软件并没有处理UPGMA产生的进化树不惟一的问题。通常仅根据算法实现方式的不同,给出了其中一种拓扑结构。针对以上问题,本文详细分析了UPGMA产生不惟一结果的原因,在此基础上提出并实现了UPGMA的一种改进算法,即不加权算术平均组群方法(UnweightedMulti-GroupMethodusingArithmeticaverages,以下简称UMGMA)。UMGMA是UPGMA的一种扩展,而UPGMA可以看作UMGMA的一个特例。在迭代计算过程中,UPGMA总是选取距离矩阵中最小的元素对应的一对序列生成新的分类群单元。而UMGMA则通过引入距离容差参数τ,将所有小于τ的元素对应的序列作为生成新分类群单元的基础。该方法在一次迭代中可以产生多个新的分类群单元,因此其进化树结果可能是多叉树。在UPGMA结果不惟一的情况下,各种可能的二叉树结果在UMGMA中被综合构建成一棵惟一的多叉树,从而解决了惟一性的问题;而在UPGMA结果惟一的情况下,取距离容差参数τ等于零,UMGMA得到的结果将与UPGMA的结果完全一致。基于实际数据的进化树构建实验表明,UMGMA不仅能够产生结果惟一的进化树,而且通过选择不同的容差参数τ,还能产生不同层次的进化树。这意味着在大规模系统发育分析中,UMGMA可以通过调整τ的值,不断突出进化树的整体脉络。本文的课题研究工作中还实现了一种包含完整UMGMA算法实现以及传统UPGMA方法实现的分子发育分析软件——Multi-Tree。该软件是一个基于Microsoft.Netframework2.0平台构建的客户端应用,其中使用WebService完成多序列比对功能,并提供一套基本的分子进化分析流程,包括:多序列比对结果编辑、距离矩阵计算以及多种方法构建进化树,并以多种风格显示进化树。Multi-Tree软件系统有别于大多数传统的分子发育分析工具软件包,它具有友好的富