利用树操作求解基因复制与丢失问题

摘要

1859年11月24日,英国生物学家Charles Robert Darwin发表了《物种起源》一书,提出了生物进化论学说。科学家们发现可以通过进化树来形象的展现物种之间所存在的遗传系谱关系。这样的进化树又称为系统发生树,它描绘了自然界中不同物种之间的进化关系。如何构建这样的一棵进化树已经成为生命科学的一个基本问题。
　　 随着基因技术的发展,人类逐渐掌握了越来越多的基因组序列信息。这些基因组序列信息为研究物种的演化史提供了大量的,潜在的数据。基于这些基因组序列信息,科学家们提出了一些用来构建生物进化树的模型和方法。这些模型或者方法有着一个共同的特征:都是将携带着大量遗传信息的基因作为研究起点来构建进化树。一般来说,为了构建一组物种的进化树,科学家们首先是根据从这些物种中得到的基因组序列信息来构建一组树,称之为基因树。在这一过程中,暗含着这样的一个假设:所选中的基因组序列的演化史模拟了物种的演化史。但是由于在生物进化过程中包含了诸如基因复制、基因丢失、基因重组等多种复杂的生物事件,所以,根据基因组序列信息所构建的进化树可能并不能正确的表达与之对应的物种之间的进化历史。
　　 基因复制与基因丢失是常见的生物进化现象,在生物进化史中扮演着举足轻重的角色。为了能够更好的解决进化树构建这一问题,Goodman等人提出了基因复制和丢失模型。它可以从一组基因树中推断出一棵能够准确的表达物种进化关系的物种树。在基因复制和丢失模型中,可以通过解决基因复制问题和基因丢失问题来推断出正确的物种树。这两个问题都是以一组基因树作为输入,目标是找到一棵最优的物种树,使得基因复制(或者基因丢失)的数量最少。
　　 Ma Bin等人证明了这两个问题都属于NP-hard问题。所以,在实际应用中,基于局部搜索的启发式算法通常被用来解决这两个问题。
　　 在本文中,深入研究了当前已有的解决基因复制与基因丢失问题的算法,并对基于SPR和TBR,这两种树操作的算法进行了改进:
　　 (1)具体分析了基于SPR操作的基因复制问题算法的实现过程,发现了其中有很重要的一步存在着大量的冗余计算,并设计了一个新的算法,去除了冗余计算。实验表明改进后的算法在性能上有了较大提高。
　　 (2)根据SPR操作与TBR操作之间的联系,提出了一种解决基于TBR操作的基因丢失问题的新算法。