基于PRUFER编码的遗传算法在简约树构建中的应用

摘 要本文提出的基于Prufer编码的遗传算法，首先将给定的N个物种的系统发生树进行编码，得到与系统发生树一一对应的Prufer编码，其次设计了遗传操作算子，从而通过遗传操作来寻找最优解。计算结果表明，Prufer编码简化了树的存贮，使改进算法的准确性和运算效率都有较大提高。

【关键词】系统发生树 最大简约法 遗传算法 Prufer编码

系统发生是指生物形成或进化的历史。对于给定的分类单元数，有很多棵可能的系统发生树，但是只有一棵树是正确的。系统发生分析的最终目标就是寻找这棵能真实反映历史的树。最大简约法是构建树的常用方法，遗传算法是计算数学中用于解决最优的搜索算法，因此，基于遗传算法来寻找最大简约树是适合的。

1 最大简约法与遗传算法

最大简约法（Maximum parsimony）是根据离散特征数据构建生物的系统发育树的重要方法。该算法假定进化次数最少的进化树是最符合自然进化的，树的代价计算就是沿着各个分支累加特征变化的数目。遗传算法（genetic algorithm，以下简称为GA） John Holland教授通过模拟生物进化过程设计了最初的遗传算法，称之为标准遗传算法。GA的遗传算子是影响GA行为和性能的关键，直接影响算法的收敛性。

2 基于PRUFER编码的遗传算法的最大简约法

2.1 Prufer编码

图论计算中一个经典的定理是Cayley定理，即在一个有n个顶点的完全图中，有n^（n-2）个不同的树。一棵树n个结点，其Prufer序列有n-2个位置，因此可以在这n-2个位置里面任何的填充1～n之间的数形成一个prufer序列，且一个prufer序列唯一的对应一颗生成树。标号树及其对应的Prufer序列如图1所示。

2.2 编码方式、适应度函数和种群的初始化

编码方式：对给定的N个物种进行编号1至n，做为生成树的叶子结点，对其所形成的n-1个内部结点从n+1至2n-1进行编号。Prufer序列是n+1至2n-1之间的n-2个数字的排列。以此来确定树的拓扑结构。

适应度函数：以简约法的树长计算函数为适应度函数，以历史最大简约树为历史最低适应值的树。

初始种群：根据输入物种的DNA序列，随机产生Prufer序列。

2.3 遗传算子设计

在遗传的过程当中要确保Prufer序列{3，5，1，3}中所有的结点至少出现过一次，但出现的次序可变。如果丢失节点，会导致原来的内部结点变成了叶子结点，产生无效解。

2.3.1 选择操作

采用随机联赛选择法，联赛规模N的取值为2。随机选择初始群体两个个体Pi和Pj，将其转换为树Ti，Tj并计算其个体适应度值fi和fj，如fi≤fj，则选择个体Pi遗传到下一代。

2.3.2 复制操作

将种群里中序列对应的进化树，依据适应值进行排序。得分越低，进化树差异越小，越靠前。将种群里的进化树排序完成后，复制过程也就结束了。

2.3.3 变异操作

对群体中的个体，以某一概率，一般取值[0.00l～0.0l] 改变某一个或某一些基因座上的基因值为其他的等位基因。为了保证原本可行的解经过变异后不会产生不可行解，设计以下三种变异算子。

（1）交换变异 在亲代的Prufer序列中随机选择两个位置，进行对换后形成新子代。

交换前Prufer序列3，5，1，3交换后Prufer序列 3，1，5，3

（2）插入变异 在亲代的Prufer序列中随机选择两个位置，将第二个位置的编码插到第一个位置编码的后面。插入前Prufer序列3，5，1，3 插入后Prufer序列 3，3，5，1

（3）逆向变异 在亲代的编码串中，随机取一段编码，将其位置反向。

逆向前Prufer序列3，5，1，3逆向后Prufer序列3，3，1，5

2.4 更新初始群体

将进化过程中产生的Prufer 序列作为下一次迭代的初始群体。若当前群体中最佳个体的适应度值比总的历史最好个体的适应度还要高，以该最佳个体作为新的历史最好个体。

2.5 结束条件

群体进化的次数超过最大叠代次数；或进化代数超过一定值，但进化树的适应度值不再有所提高时，系统结束，最后一代进化中适应度值最小的个体即为最优解。

3 基于Prufer编码的遗传算法构建简约树的比较分析

本文以TreeBASE所提供的序列资料作为数据源，以运行时间和树长为衡量标准， 并与PHYLIP软件中的Dnapenny.exe分支限界法搜索最大简约树的软件相比较.算法参数如下：群体规模PopSize=200，最大叠代次数MaxGeneration=200，初始群体用P0表示，选择算子联赛规模N=2，交换变异k1=0.001 插入变异k2=0.001，逆向变异k3=0.001.PRUFER编码简化了树的存贮，使遗传操作在线性时间内完成，本方法简单有效，它能够在较短的时间内产生一批最小树或次小树，从而为实际研究提供更多选择，此外， GA中各种参数的选择也是影响结果和速度的关键因素。

参考文献

[1]郭静，王超，张宏彬，陈.系统发生树构建方法综述[J].计算机应用研究，2013（03）.

[2]雷亮，汪同庆，彭军，杨波.改进的自适应遗传算法应用研究[J]，计算机科学，2009年，vol36 （NO.6） ：203.

[3]吴浩扬，常炳国，朱长纯，刘君华.基于模拟退火机制的多种群并行遗传算法[J].软件学报，2000，vol.11（NO.3）：416.

[4] 周丽娟，乐晓波.遗传算法在求解最小生成树中的运用[J].开发研究与设计技术，2007（06）.

[5]王镌，严坤妹.基于数组的Prufer编解码的线性算法[J].西安石油大学学报，2013（01） 第28卷第1期.

[6]王晓东，吴英杰.Prufer编解码的最优算法[J].小型微型计算机系统，2008（04）.

作者简介

刘清雪（1977-），女，吉林省长春市人。硕士学位。现为吉林建筑大学城建学院讲师。主要研究方向为生物信息学序列比对及系统发育分析。

作者单位

吉林建筑大学城建学院 吉林省长春市 130111