基于蚁群算法的双序列比对及其实现

序列比对是生物信息学的基础，本文首先分析了基于动态规划的经典双序列比对方法，然后根据蚁群算法求解旅行商问题的思路，将旅行商问题与双序列比对问题简单比较了它们的异同点，并详述了基于蚁群算法的双序列比对步骤，根据双序列比对过程的具体特点，对基本蚁群算法各个参量以及更新公式进行了相应的修改，成功实现了基于蚁群算法的双序列比对过程。

【关键词】蚁群算法 双序列比对 更新公式

序列比对是生物信息学的基础，通过在基因比对中获得大量的序列信息，可以推断基因的结构、功能和进化关系。生物序列比对主要应用在生物信息学上，例如DNA双序列比对其相似性能够反映出两条DNA亲缘关系，实现生物基因识别技术；通过研究病变的生物蛋白序列和正常的序列，能够有效地研究病变机理甚至采取一定的预防措施。在计算机领域，一般首先是将序列元素用不同的字符表示，一整条序列就可以用字符串来表示，因此，双序列比对问题就是比较两条字符串的相似性。

目前对于双序列比对方法主要是基于动态规划算法有经典的Needleman-Wunsch算法和Smith-Waterman算法，利用一定的打分规则和填充分值矩阵等步骤，可以进行序列的精确比对，主要包括比对和回溯两个过程，需要耗费大量的时间，对于较长序列，需要耗费大量存储空间来存储分值矩阵，因此，经典序列比对算法对机器性能有一定的要求。对于此种方法的不足，主要有两方面的改进与优化，一是算法上的优化，二是硬件上的优化。万文利用CUDA开发平台实现了基于CPU与GPU异构系统来加速Smith-Waterman算法，并且对算法进行了深入分析，设计CPU+GPU的协同并行方案，对应用程序性能与系统性能有显著的提升效果。夏飞利用FPGA器件结合通用处理器实现了算法加速器，并且设计了细粒度并行算法，成功解决了FPGA逻辑单元和存储资源在进行长序列比对时资源受限问题。

另一方面，已经衍生了很多优化算法做近似比对，比如遗传算法，模拟退火算法等现代智能算法，它们不能保证每次都能找到最优解，但是采用这些算法收敛速度快，效率高。本文详细分析了蚁群算法求解旅行商问题，并且与双序列比对问题做了具体的比较，得出它们的异同点，并将蚁群算法运用到求解双序列比对问题中。

1 经典比对算法及其实现

经典的Needleman-Wunsch算法和Smith-Waterman算法对于双序列比对分为两个过程：比对和回溯，比对结果可以得到两条序列的相似程度，回溯过程则可以得到序列中元素的配对结果，但回溯过程不是必须的。

1.1 双序列比对过程

假设对于给定的两条DNA序列，其中一条序列字符串表示为，另一条序列字符串表示为，两条序列中各元素sj和lj分别表示DNA四种碱基{A，G，C，T}。对于这两条序列的比对过程分三种编辑操作：替代、删除与插入，序列比对可以通过这三种编辑操作得到最大的相似性，即最优比对结果。

通常，为表示这个最优比对结果会采用一定的打分规则来表示比对过程的进行以及结果分析，设打分函数为：

如果序列元素sj与lj匹配相同，而且sj和lj都不是空位，则当前元素比对结果为+2分；如果sj与lj匹配不相同，而且sj和lj都不是空位，则比对结果为-1分，如果sj与lj其中一个为空位-，则比对结果为-2分。因此，通过对两条序列中的元素逐个比对，最终会得到一个总分值来表示双序列的匹配程度。经典的NW算法和SW算法就是利用打分规则和分值矩阵，填充完分值矩阵，然后是回溯过程，从分值右下角开始往上搜索局部最大分值最终可得到最优比对结果。

2 基于蚁群系统的双序列比对

2.1 问题比较与算法设计

蚁群算法是一种现代智能仿生算法，它通过模拟蚁群在觅食过程中寻找最短路径的方法来求解最优化问题，最早是应用在TSP问题上，取得了很好的效果，又来又与多种优化算法相结合，开始得到了廣泛应用。

用蚁群算法求解序列比对问题是在该领域的一种尝试，在利用蚁群算法求解TSP问题的基础上，将其算法思想用于求解序列比对问题上。双序列比对问题可以归结于：在分值矩阵中，求解出一条分值最大且路径最短的问题。如下，列出了利用蚁群算法求解旅行商问题和求解双序列比对问题上的主要异同点。

（1）在TSP问题中，蚂蚁的初始位置随机放置，而且在寻找下一个节点时也是随机选择，而在序列比对中，蚂蚁的初始位置位于分值矩阵的左上角，其搜索移动方向也只有三个：右边，下边和右下角；

（2）在TSP问题中，启发信息是城市间路径的长度，将每轮迭代中所有蚂蚁走的路径进行比较，选取其中一只蚂蚁行走的最短路径作为局部最优结果，而在序列比对中，将蚂蚁走的每一步所产生的字符匹配得分作为启发信息，当所有蚂蚁都走到分值矩阵的右下角时，比较每只蚂蚁所走路线的最终匹配得分，选取得分最高的作为局部最优解，并记录其行走路线；

（3）每轮搜索的终止方式不同：在TSP问题中，城市的数目一定，根据搜索禁忌表使得每只蚂蚁在每轮搜索中有且仅有一次机会就可以遍历完所有城市，而在序列比对中，由于每只蚂蚁行走的路线不同，因此，最终到达终点（分值矩阵的右下角）时存在着先后到达顺序，在此问题中，可以设置终点标志位，在未到达终点前，标志位为0，到达了终点，将标志位置为1；

（4）移动方向的选取原则类似（计算转移概率并依据轮盘赌法选择方向），但移动方向的概率公式不同。

2.2 更新公式

因此，根据基本的蚁群算法，在双序列比对问题中需要修改的参量以及更新公式如下：

2.3 算法实现

利用蚁群算法求解双序列比对问题详细步骤如下：

步骤1：规则设定。输入两条待比对序列，并设定其打分规则，再根据分值构建对应的比对字符匹配矩阵，将分值矩阵中的正数在字符匹配矩阵中相应的位置设为原值，负数取绝对值的倒数，则字符相同的位置为2，不相同的为1，有空位的为0.5；

步骤2：初始化。初始化m只人工蚂蚁，并设置各参数：迭代次数、方向权值、初始化信息素矩阵等，从分值矩阵的左上角出发向矩阵右下角按一定的规则开始搜索；

步骤3：有规则搜索。蚂蚁在前进搜索过程中，其搜索移动的方向只能三个：向下、向右和向右下方（以蚂蚁当前位置为参考点）。首先设定一个固定值q0，蚂蚁在选择前进方向时，先产生一个随机数，如果这个随机数小于q0，则蚂蚁选择右下方位置移动，如果这个随机数大于q0，则采用轮盘赌法来进行选择移动方向。

步骤4：移动一步之后，判断蚂蚁是否走到边界。蚂蚁如果走到最右边，则之后的移动方向只能选择向下；如果走到最下边，则之后的移动方向只能选择向右，因此，考虑到此种边缘情况，下一次迭代时，步骤3就不再需要计算概率。

步骤5：当蚂蚁移动到了分值矩阵的右下角，设定其结束标志位，结束当前一轮的搜索，同时记录蚂蚁的行走路线。

步骤6：当m只蚂蚁都搜索完之后，比较它们的行走路径和得分，与历史局部最优解比较，更新当前局部最优解，并保存这一轮的最高分及其对应的路径（局部最优解），然后更新全局最优解，同时更新信息素矩阵。

步骤7：判断当前迭代次数是否达到预先设定的次数，或者是，全局最优解连续T次未更新（更新为相同的值），如果条件满足，则算法结束，否则，进行下一次迭代，跳转到步骤2。

最终可根据全局最优解对应的蚂蚁行走路线可推出最佳序列比对结果，如果蚂蚁是向下方移动，则在序列L中对应的位置插入-，如果蚂蚁是向右方移动，则在序列S中对应的位置插入-，如果蚂蚁向右下角方向移动，则说明当前匹配的序列元素相同。

由此可以看出，利用蚁群算法求解双序列比对问题之后，不再需要回溯过程，而且在比对过程中，每只蚂蚁的行走路线不必太过依赖于前一步所走的位置，仅仅只是根据概率公式进行一个方向的选择而已，从一定程度上体现了蚁群算法的搜索随机性。

3 实验结果与分析

C语言编程算法流程，并利用蚁群算法进行DNA雙序列比对，采用GCC编译器，运行环境：Intel（R） i3-4160 CPU@3.60GHz。蚁群算法的各参数设置如下：迭代次数NcMax =100，蚁群规模M =20，信息素重要Alpha = 5.0， 字符匹配重要程度Beta = 3.0，空位数目重要程度 Gamma = 2.0，转移概率设定值q0= 0.2，信息素挥发程度Rou = 0.05，信息素增加强度系数Q = 0.1， 信息素增量转化参数Qc = 50，方向权重参考值H = 5，比对结果如下：

在GenBank数据库中选取两条DNA序列进行比对，验证算法的可行性，其编号分别是DQ482171和DQ482174，序列长度为382，图1显示了比对过程中，局部最优解与迭代次数的动态变化关系。

由以上结果分析可知，随着迭代次数的增加，最优比对分值结果不断增加，说明蚂蚁在搜索过程中，信息素的更新起到了一定的作用，对蚂蚁行走的路线不断优化。然后再进行重复实验10次，表1显示了对于不同长度的几组序列利用蚁群算法比对结果：最优结果、最差结果、10次实验的算术平均值，以及程序运行十次的累计耗时。

其中编号1的双序列基因序列号分别是DQ482171和DQ482174；编号2的双序列基因序列号分别是AB023276和AB023278；编号3的双序列基因序列号分别是AF039225和AF039226，其中AF039225长度为613bp，而AF039226长度为612bp，以观察不同长度序列利用蚁群算法比对的结果；编号4的双序列对应的基因序列号分别是HIV1U39234和HIV1U39238，其长度较长，以观察在长序列中算法的适用性；编号5的双序列是对编号2序列进行了一定的修改，降低序列的相似度，以观察在低相似度中算法的适用性。

在进行长序列比对时，可以看到蚁群算法并不能保证求得最优解，这是因为，随着序列的增长，蚂蚁在前期搜索过程中如果偏离了最优路线，导致后期搜索很难收敛，甚至远离最优解。由此可以看出，长序列不如短序列的比对效果好。在进行不同长度序列比对时，蚁群算法仍具有很好的收敛性，并尽可能的求得最优解。在进行低相似度序列比对时，蚁群算法寻得路径也可能会导致并不是最优解，这是因为，在搜索时，如果蚂蚁尽可能的保证最优解而逐渐远离实际的最优解，不同字符匹配的数目越来越多，却增加了蚂蚁搜索的随机性，使得这一影响更为明显，搜索不到最优解的可能性也会越大。

由以上结果可以看出，利用蚁群算法求解双序列比对问题是可实现的，可以看到，在利用蚁群算法求解双序列比对问题时，还是具有一定的随机性，并且随着迭代的次数的增加，算法开始收敛直到最优结果，至于最优结果的最终表达取决于字符匹配过程中对规则的设定。

4 结束语

文中对比了TSP问题和双序列比对问题，并且成功将蚁群算法实现应用在序列比对之中，对于更新公式的替换，在很多参考文献中称之为改进的蚁群算法，在这方面还可以有很多值得研究的地方，而对于蚁群算法的参数寻优却仍是一个很有意义的研究方向，另外针对蚁群算法易陷入局部最优结果的弊端，此处也可以利用其它的算法来优化。如果对这几个方面有更大的改进，蚁群算法应该会使得双序列比对结果更加精确。

（通讯作者：汪楠）

参考文献

[1]Smith T.F.，Waterman M.S.Identification of Common Molecular Subsequences[J].Journal of Molecular Biology，1981，147（01）.

[2]万文.生物序列分析算法的CPU+GPU异构并行优化关键技术研究[D].国防科学技术大学，2012（03）.

[3]杨春燕，钟诚.CPU和GPU协同并行加速多生物序列比对[J].小型微型计算机系统，2016（12）.

[4]夏飞.生物序列分析算法硬件加速器关键技术研究[D].国防科学技术大学，2011（03）.

[5]李方洁.基于智能算法的DNA序列比对研究[D].山东师范大学，2011（06）.

[6]李娟.生物序列相似性搜索算法研究与实现[D].华南理工大学，2013.

作者简介

李宏周（1980-），男，桂林电子科技大学硕士生导师。研究方向为电路与系统。

汪楠（1993-），男，湖北省黄冈市人。桂林电子科技大学研究生。主要研究方向为嵌入式系统设计。

作者单位

1.桂林电子科技大学 计算机与信息安全学院 广西壮族自治区桂林市 541004

2.桂林电子科技大学 电子工程与自动化学院 广西壮族自治区桂林市 541004

3.桂林电子科技大学 生命与环境科学学院 广西壮族自治区桂林市 541004