系统发生树的构建是一个非常具有挑战性的问题,对此问题的研究在生物信息学中变得越来越重要。由于可能拓扑结构的系统发生树数目随着物种数目增加呈指数形式增长,关于最优树的构建问题都是NP-Complete问题,巨大的搜索空间使得系统发生树的构建极其消耗计算资源。当物种数目很大时,没有一种优化算法能在适当的时间内计算得到其精确解,因此,寻找能够在合理的时间内得到最优近似解的算法就有很强的实际意义。遗传算法(Genetic Algorithm)和蚁群算法(Ant Colony Algorithm)是两种求解复杂优化问题的模拟进化算法。大量实验结果表明,这两种算法在解决许多组合优化问题时都能表现出较好的求解能力。针对系统发生分析问题的组合复杂性,及遗传算法和蚁群算法在解决此类问题中的优势,本文将这两种算法应用于系统发生树的构建问题,提出了四种系统发生树的构建方法。首先,本文提出了一种构建系统发生树的遗传算法GA-PTC,将可能的系统发生树的拓扑结构编码成问题的解空间,并在解空间中搜索最优树。在此方法中,我们提出了系统发生树的后缀表示法作为遗传算法的编码方式,在对个体评价时,采用基于距离设计的适应度函数对个体进行记分,并根据选择概率与适应度成正比的赌轮盘选择策略从父代中选择部分较优个体,然后通过遗传操作产生新一代个体。实验结果表明,此算法能够得到正确的系统发生树。其次,本文在分析蚁群算法的原理及性能的基础上,提出三种基于蚁群算法的系统发生树构建方法:(1)基于TSP问题的构建系统发生树的蚁群算法TSP-PTC。给定一个物种集合以及它们之间的距离矩阵,我们可以构造一个带权图。对于图中的每一条哈密尔顿回路,都可以对应于一棵系统发生树,在所有回路所对应的系统发生树中,适应度值最小的是TSP问题的解所对应的系统发生树。因此我们可以利用蚁群算法在带权图中寻找最优路径,然后用此回路及物种之间的距离构建系统发生树。在构建系统发生树时,首先根据回路构建其拓扑结构,然后根据拓扑结构和距离矩阵给各边分配权值。此方法比传统算法构建出来的系统发生树的准确度要高。(2)基于蚁群聚类的构建系统发生树的蚁群算法AC-PTC。在算法开始搜索之前,同样将物种群用一个带权图来表示。图中的顶点表示待研究的物种,边上的距离用蚂蚁在访问图的过程中所积累的信息素来衡量。用蚂蚁遍历该图并在遍历过程中更新信息素,在算法停止迭代后删去图中某些信息素较少的边,然后通过求该图的强连通分量达到对物种聚类的目的。我们在算法中引入了信息素的自适应更新策略,以防止算法早熟和局部收敛。最终系统发生树由各个聚类构建而成。(3)基于后缀表示的构建系统发生树的蚁群算法SR-PTC。在此方法中,蚂蚁访问物种集合的目的是形成一个对应于最优系统发生树的后缀表示序列。一个合法的后缀表示序列对应于一棵二叉树。为构成一个合法的系统发生树的后缀表示,蚂蚁对内部结点的选择要受到限制,我们分别为叶结点和内部结点设置两个不同的选择概率,并用赌轮盘选择方法来决定两种结点的选择。另外,在信息素更新时,加入当前树的评价值来影响蚂蚁的运动方向。我们用本文的算法与传统的系统发生树构建方法进行了比较。实验结果表明,三种基于蚁群算法构建系统发生树的方法都能得到较为准确的拓扑结构。另外,我们还分析了本文提出的三种基于蚁群的系统发生树构建方法在解决不同问题时的性能。实验结果表明,TSP-PTC方法构建出的系统发生树在准确度最高,AC-PTC方法在物种数目较大时消耗的时间最短,而SR-PTC方法在物种数目较小时速度最快。