论文部分内容阅读
现存的物种间由于遗传因素,存在基因上的联系,可以根据这些关联信息构建一棵物种树,用来反映它们之间的进化关系。随着现代科技的发展,发现了越来越多的基因组序列的信息。这些基因组序列信息可以为我们研究物种演化史提供大量的、潜在的数据。根据从物种中得到的基因组序列信息而构建的一组树,称之为基因树。其中基因组序列的演化史模拟了物种的演化史。在进化过程中,有大量的基因复制和丢失现象,所以根据基因信息所构建的进化树可能并不能正确的表达与之对应的物种之间的进化历史,在构造实际的最优物种树时需要根据一定的标准考虑这些因素所造成的影响。构建物种树的问题是一个基础科学问题,而这个问题已被Ma Bin等人证明为NP-hard问题,所以为了有效地解决这个问题,在实际应用中,需要采用一些启发式算法来找到一棵较优的物种树,现存的启发式都是通过执行一些局部搜索算法来实现的。基因复制与丢失问题都是基于M. Goodman等人提出的模型的,在此基础上,M. S. Bansal等人设计了一系列的启发式算法,以便能够应用到实际物种进化研究中。这些启发式都是通过对一棵物种树执行某个树操作得到一个树空间集合,然后计算这个集合里的每一棵树的特征值,最后在这个树空间集合里执行局部搜索来找到局部最优解。目前常见的树操作有三种：NNI(the rooted nearest neighbour interchange), SPR(the rooted subtree pruning and regrafting)和TBR(the rooted tree bisection and reconnection)。基于NNI, SPR和TBR的基因复制问题的算法已分别被优化到O(kmn), O(kmn)和O(kmnlogm),而基于SPR,TBR的基因丢失算法也已被优化到O(kmn)和O(kmn2)。本文在原有研究的基础上,主要优化了两个问题。(1)提出了一个解决1-NNI基因复制问题的新算法,通过对基因树中的节点进行分类与分析,消除了许多冗余计算,使算法的运行时间得到了大幅度的缩减,并利用大量随机生成的基因树进行了对比实验加以验证算法的性能。(2)提出了一个解决基于NNI基因丢失问题的新算法,通过分析第二次执行NNI操作之后哪些节点的LOSS值没有发生改变来入手,得到一系列的性质与定理,然后重复利用没有改变的信息来求解。之前最原始的算法的时间复杂度为O(kmn2),本文提出的算法的时间复杂度为O(kmn)。