随着分子生物学和全基因组测序技术的快速发展,产生了大量的基因数据,这使得对基因家族分子进化的研究成为可能。重建基因家族进化史对解决许多基本生物学问题起着非常关键的作用,近年来得到广泛的关注和重视,并发展成为比较基因组学中一个重要的研究方向。两物种的小系统发育问题是构建基因家族进化史的重要子问题。本文主要对该问题的求解算法进行研究,并开发了一个实用的软件包,具体工作如下：针对复制-丢失比对问题模型,对两物种小系统发育问题的算法进行研究,首先提出比对算法A LING,该算法基于字符最大匹配原则,通过在两条基因序列中插入一定数量的空格，以得到两条基因序列的一个序列比对。其次,对于给定的一个序列比对,本文提出种标记算法LABLE该算法分别从左至右和从右至左两个方向进行,利用复制-丢失操作序列标记给定的序列比对,并取对应代价较小的操作序列作为最终标记。论文基于提出的ALIGN算法和LABLE算法,设计了一种求解复制-丢失演化模型下两物种小系统发育问题的遗传算法G2SP。算法G2SP通过ALIGN产生初始解,利用LABLE来衡量解的适应度,并引入了重新匹配基因块、基因智能移动及移动基因块3种智能变异算子,以提高种群的收敛性,使算法能更快地进化到最优解区域。利用6种真实菌属的rRNA基因数据和模拟数据对算法性能进行测试,实验结果表明,算法G2SP能够获得较PBLP算法更小的进化代价,且其运行时间在实际应用中是可行的,是求解两物种小系统发育问题的一种有效方法。根据G2SP算法思路,设计并实现了一个用于求解复制-丢失演化模型下两物种小系统发育问题的实用软件包。该软件包使用c#言和Visual Studio2012开发工具进行开发,可以在装有NET Framework4.0 的 window XP 及 window 7以上的系统中运行。该软件包主要包括参数设置、读入生物数据、重建祖先、查看结果和帮助等功能模块。参数设置模块可以根据具体情况,设置进化周期、种群规模、迭代次数、变异率和交叉率等实验参数。读入生物数据是指从文本文件中读入两条生物的基因序列,每条序列由代表特定基因家族的基因构成。该软件在求解问题过程中同时显示运行时间及每次迭代的最优解等信息,最终结果保存在文件中,记录两条基因序列带有标记的序列比对、祖先信息序列及两条基因序列的进化史。综上所述,本文对两物种小系统发育问题的求解算法进行研究,针对复制-丢失比对问题模型,提出了有效的遗传算法G2SP,并获得了较好的优化效果,为解决系统发育问题提供了一种新的思路和方法。此外,开发的软件包可为求解复制-丢失演化模型下的两物种小系统发育问题提供实用工具。