自适应蚁群算法在序列比对中的应用
第22卷 第1期 计 算 机 仿 真 20O5年1月
文章编号 ：1006—9348(2005)01—0100—03
自适应蚁群算法在序列比对中的应用
粱 栋 ，霍红卫
(西安电子科技大学计算机学院，陕西 西安 710071)
摘要 ：序列 比对是生物信息学的重要研究-rg。蚁群算法是一种新型的模拟进化算法，并被成功地应用于旅行商问题(TSP)
等组合优化问题中。该文将蚁群算法应用于序列比对，并提出基于 自适应调整信息素的改进算法。仿真结果表明这种新的
比对算法是有效的，而它的改进算法的效果更为理想。
关键词：蚁群算法；序列比对 ；信息素 ．
中圈分 类号 ：TP301．6 文献标识码 ：A
An Adaptive An t Colony Optimization Algorithm and Its Application
to Sequence Alignment
LIANG Dong，HUO Hong—wei
(School of Computer Science，Xidian University，Xi’all S~mnxi 710071，China)
ABSIltAcr：Sequence alignment is one of the moat in驴删 tools in bioinfmmmics m~arch．Ant colony叩而 0Il is a
novd simulated evolutionary algorithm successfully usedin combinatorial 0p血li翻d0Il 】ble蛆 such鹪 I印 ．Inthis paper，
ACO is applied in sequence al and improved by adaptive ng the pI螂啊 啦 ．The a；n,!A．on results demon-
strate that the Ilew approach is eflldent and the improved algorithm is m帆 efficient．
KEYWORDS：Ant colony op*imlmtion；Sequence a]igmnem；Pheromone
1 引言
序列比对(Sequence Alignment)是一种重要的生物信息处
理技术，通过比对 中获得的序列信息可以推断基因的结构 、
功能和进化关系，是生物信息学的重要研究工具。
蚁群算法(Ac0)是一种新型的模拟进化算法 ，通过由候
选解组成的群体在不断进化的过程 中寻求最优解 ]。它是
在对 自然界蚁群 的寻径 方式进行研究和模拟的基础上，由
DorigoM．等人首先提 出的u J。 目前该算法在 旅行商 问题
( I印)等组合优化问题 中有较多的研究 J。
本文将蚁群算法应用于序列 比对，并在此基础上 。针对
蚁群算法易于陷入局部最优解的特点，提出动态 自适应调整
信息素的改进算法，以求扩大搜索空间，提高收敛速度。仿
真实验证明这种新的比对算法是有效的，而其改进算法的效
果更为理想。
2 序 列比对问题描述
双序列比对是多序列比对和序列 数据库搜索 的基础。
Needleman和 Wunsch提出的比对方法属于动态规划范畴[3l。
收稿 日期 ：~003—10—14
— 100 一
对于一个序列 S，l S l是 S中的字符个数，S[‘]表示序
列的第 ‘个字符。S[1．．i]表示序列的前 个字符组成的子序
列。S中的字符由某个有限字符集合n确定(如DNA由4种核
糖核酸 A， ，C，G确定)。基 因序列在突变 中的变化包括替
代、插入和删除，我们用“一”来表示插入和删除所产生的空
位。对于 ，Y∈n U {一}，定义 口( ，Y)为计分函数 ，表示 ，
Y比较时的得分 ，以下是最简单的一种：
f2 Y∈n
口( ，Y)={一1 ≠Y∈n (1) 【
一
l = ‘一’。r)，= ‘一'
S和 的一个 比对A用序列和中字符的一一对应表示 。
其中 ① l l=l， l，② l l，l， l去掉空格就是 S和 。
A的得分为 ：
(A)：∑ I$1口( [ ]， (2)
取得最大值的比对就是最优比对。
3 蚁群算法应用于序列比对
3．1 蚁群算法的原理
人工蚁群算法是受到真实蚁群觅食行为的启发提出的。
维普资讯 http://www.cqvip.com
蚂蚁这种群居昆虫，虽然单个个体的行为十分简单 ，但是由
其组成的群体却能完成较为复杂的行动 ，比如可以找到巢穴
到食物源的最短路径。仿生学家经过研究发现，每只蚂蚁觅
食时在走过的路线上会 留下一种称为信息素(pheromone)的
物质 ，蚂蚁之间就是靠感知这种物质的浓度进行信息传递
的。蚂蚁倾向于朝浓度高的方向移动，而且找到食物后会顺
原路返回。这样就形成 了一种正反馈机制：由于外激素随着
时间而挥发 ，距离短的路径因蚂蚁来回用时少，信息素浓度
将高于距离长的路径，后来 的蚂蚁选择距离短的路径，然后
又留下新的信息素，随着时间的推移，距离短的路径上的信
息素越来越多，选择它的蚂蚁也逐渐增多，最后整个蚁群聚
集到最短路径上。
人工蚁群算法模拟了这一过程。每只蚂蚁在解空间独立
地搜索可行解，解越好留下的信息素越多，随着算法推进，较
优解路径上的信息素增多，选择它的蚂蚁也随之增多，最终
收敛到最优或近似最优的解上 』。
3．2 蚊群比对算法的设计
对序列 S=CAGGA和 T=CGGITA，仿照动态规划法那
样阵建立矩阵(如图 1)。
蚂蚁从矩阵左上角出发选
择一条路线到达右下角，就形成
一 个比对 ，我们规定在水平或垂
直方向上移动一格，表示在相应
的序列中插入一个空位，沿对角
线移动一格表示到达的新位置
对应字符的匹配。图 1中的路线
表示了如下比对结果：
C G G T T A
_
C ll
A ll
6 ■
6
A ■
图1 单个蚂蚁的行走路线
序列 S ：CAGG一一A
序列 -I'，：c—GGITA
根据式(1)和(2)得分为 5。在找到的所有路线中得分最
高的比对就是最优比对。
与 ISP问题不同，蚂蚁在每个位置选择移动方向的数 目
是固定的，总是向右，向下 ，沿对角线向右下三个方向，序列
比对对加入的空位数量也有一定要求。所以蚁群 比对算法的
设计与 TSP问题有所不同。
我们用 谴(t)表示 t时刻图 1中(i， )位置上第 k个方
向的路径 R谴上的信息素浓度。其中 i=0，1，2? I s I， =
0，1，2．．．I I，而 k=0，1，2分别表示向右，向下 ，即向右下
方向。初始时刻，设定 r诚(0)= ro(r。为常数)。
蚂蚁 ：(：=1，2? m)从矩阵左上角出发，每走一步 ，根
据当前位置上各条路径上的信息素浓度决定 向某一路径转
移。为(i，．，)位置上蚂蚁 ；选择第七个方向的路径定义一个得
分：
SCORE~=讯(f) (3)
讯 (f)的意义如前面所述。肘为启发信息，可 以根据式
(1)来确定 JIIf的值。当 k=2时，即向右下方移动，所到达的
新位置上，序列 s， 对应位置上的字符如果相同，肘 的值取
匹配得分 ，式(1)中为 2，不相同则 JIIf值取不匹配罚分的绝对
值的倒数，为 1。k=0或 1时，即向右或向下移动，必然在序列
中产生空位 ，JIIf的值取空位罚分的绝对值的倒数，为 1。当然
计分方式不同，JIIf的取值方法会不同。
为防止空位过多，应尽量使蚂蚁大致沿着对角线方向行
走。我们采用 d来调整蚂蚁的选择概率，如果蚂蚁的位置为
(
．
)，当 i和，之差的绝对值在某个正数日以内，三个方向的
d值相同，这样三个方向等可能被选择 ，超过 日时，如果 i>
， 我们分配给向右和右下方向更大的 d值 ，增大蚂蚁选择这
两个方向的可能性，i<，的情况类同。日的大小对连续插入
空位的数目起到了限制作用。
a，口，y是分配给信息素，启发信息和 d的权值，体现了
它们对决策的影响力大小，在实验中可以进行合理地调整。
我们采用了这样的选择策略：首先设定 q。∈(0，1)，蚂蚁
在选择路径时产生一个(0，1)之间的随机数 P，当 P≤ qo时，
蚂蚁 ：选择 SCORE's,(k=0，1，2)之中分值最大的方向 k。当
P> 时，蚂蚁 ：按照式(4)决定三个方向被选择的概率。
p
s com '~ ‘4)
式(4)采用轮盘赌的方式实现。如果 q0=0．3，则蚂蚁以
0．3的概率选择分值最大的方向，以 0．7的概率按式(4)决
策。q0选得小，有利于增加解的搜索空间，但不容易收敛。q。
选得大则反之【4J。
经过一代进化，当所有的蚂蚁通过不同的路线到达矩阵
右下角，得到一组比对结果 ，就完成 了寻找最优路线的一次
循环。这时要对每条路径的信息素进行全局更新 ，新的信息
素要加进来 ，旧的信息素要挥发。定义 ∈ (0，1)为衰减系
数 ，则 1一qK反映了信息素的挥发程度。更新公式如下：
r毋(t+1)=叮g×r (f)+△r驰
△ =∑ △r鑫
(5)
(6)
△ 为本次循环 中路径 R 中的信息紊增量。初始时刻
△r =0o△r螽为第；只蚂蚁在路径 上留下的信息素。
．
f Q×A：(蚂蚁 =经过 )
，、 △略 i0(蚂蚁：未经过R )’ (7)
Q为常数 ，A：与蚂蚁=所走路线代表的序列比对的分值
相关。在 TSP问题中，用 表示路线的长度，它总是大于零
的。但序列比对分值可正可负，所以要将其映射到正值再分
配给 ，比对分值越高，A：越大。
由于蚂蚁选择不同的路线 ，经过的格子数可能不相等，
即不是同时到达矩阵右下角。为每只蚂蚁增加一个初始值为
0标志，当到达右下角时置为 1。当所有的蚂蚁都到达右下角，
完成信息素全局更新后，所有的蚂蚁被重置到矩阵左上角，
置标志为 0，开始下一轮循环。算法在达到最大进化代数或最
一 101 —
维普资讯 http://www.cqvip.com
优解连续 l0代没有变化时终止。
为了加快搜索 ，记录每代取得 的最好的解 ，和历代最好
的解 比较获得最优解。
4 自适应调整信息素的改进算法
蚁群算法通过正反馈机制来强化较好的解，但容易出现
停滞，陷入局部最优解l5J5。针对这个问题 ，提 出自适应调整信
息素的方法 ，根据解的搜索情况，动态地调整信息素的分配。
采用式(8)的时变函数 Q(t)来代替式(7)中的常数 Q。
进化初期为了增大搜索空间，p(t)取较小的值 ，随着算法的
推进取值逐步增大，强化较好的解。在算法的仿真中，我们采
用 ql=0．0001，q2：0．0OO5，Q3：O．001以及 TI：30，TI
： 6o0
r QI(0< t≤ TI)
Q(t)={q2(TI
p3(T2< t)
在陷入局部最优解时，某条路径上的信息素在数量上占
绝对优势[5l，因此我们对信息素的最大值和最小值进行了限
制 ，如规定 r )面 ：O．05， 彝(t)一 ：30．0o限制最大值可以
防止某条路线的信息素浓度过大，限制最小值可以防止搜索
后期没走过的路径信息素浓度过低 ，使较差的路线被强化。
为了鼓励解质量的改善 ，又不减小搜索空间，在进化一
定代数以后 ，采用式 (9)根据解的情况动态地调整信息素的
分配。若路线 R谴上取得的解(即比对得分)为 Score，较目前
得到的最优解 s∞ 一 有所改善 ，则增大路线 R 上的信息素
增量的分配，并更新 & 一 的值，若低于最优解，则减小信
息素增量的分配。
△礓 ： × (9)
如果最优解在几代 内没有改善，则可以适当减小要添加
的信息素，以求摆脱局部最优解。
5 仿真结果
采用 NC=lOO(最
大 进 化 代 数 )，m =
1o(蚂蚁总数)，r0=20．
0，a = 4．0， = 3．0，y
= 2．0，qo= 0．3， =
0．8作为蚁群算法的参
数进行仿真实验。
选择平 均长 度 为
520的两条 DNA序列进
行 比对，采用式 (1)作
圈2 两种算法的进化曲线
为计分函数 ，最优解事先通过动态规划算法求得为 902。图 2
显示了基本蚁群算法和自适应蚁群算法 的进化过程。横坐标
轴表示进化的代数 ，纵坐标轴表示某一代取得 的最优解。曲
一 102 一
线 I和 2分别代表基本算法和自适应算法的进化曲线。
从图 2中看出基本算法在第 3l代达到 854，之后就陷入
了局部解 850中。自适应算法增大了解空间，开始阶段解质量
低于基本算法 ，但搜索到更优秀解的概率较大，随着算法的
推进 ，在第 45代收敛到最优解 902，连续 lO代最优解不变后
算法终止。
表 I，表 2显示了在不同长度的几组序列上 ，基本蚁群算
法和 自适应改进算法的比对结果。每组序列进行 20次比
对。从表中可以看出改进算法的寻优能力明显优于基本算
法，在长序列的比对中更为突出。
裹 1 基本蚁群算法比对结果
编号 序列平均长度 最好结果 最坏结果 平均值 已知最优解
l l26 234 230 232．40 234
3 430 768 712 736．65 768
5 ll50 姗 l864 l936．75 嬲
．裒2 自适应蚁群算法比对结果
编号 序列平均长度 最好结果 最坏结果 平均值 已知最优解
l l26 234 230 233．35 234
2 430 768 755 764．00 768
4 l150 嬲 嬲 2053．95 嬲
表 3显示了蚁群算法对氨基酸序列的比对效果。我们
选用 “皮 质 铁 氧 还 蛋 白氧 化 还 原 酶”编号 为 I：'08165和
Q61578，平均长度为492的两条序列，共进行 20次比对。计
分方法采用PAM250替换矩阵和仿射空位罚分，“空位设置罚
分”为 一lO，“空位扩展罚分”为 一0．5，匹配得分为 5，不匹配
罚分为 一4，与“欧洲生物信息研究所(珊 )”提供 的双序列 比
对程序“EMBOSS—Align”一致。最优解也通过该程序计算求
得 。
裹 3 氨基酸序 列比对结果
采用算法 最好结果 最坏结果 平均值 已知最优解
基本算法 2l94．5 208l 2l42．95 2： 1．5
自适应算法 2： 1．5 2181 2l96．55 2： 1．5
从平 均值 看 出 自适 应 算 法 的 结果 更接 近最 优 解。
PA．~．50替换矩阵计分方法比较复杂 ，除了精确匹配外还要
计算相似得分，因此结果偶然性大 ，解的精确性有所下降。
6 结论
仿真实验表明，蚁群算法在序列 比对中的应用取得了较
好的效果，而动态 自适应调整信息素的改进算法可以明显地
提高蚁群算法的寻优能力。相信经过进一步研究 ，蚁群算法
在序列比对中的应用前景会更广阔。
f下转第 1 页
维普资讯 http://www.cqvip.com
2 O．95 O．58 29 不收敛 一
3 O．6 0．48 30 不收敛 ?
4 O．85 O．5 40 收敛 8
5 O．88 0．48 45 收敛 一 10
6 O．9 O．38 90 收敛 一 5
7 O．96 O．8 l20 不收敛 口过大
说明：’*’代 表 化 时 3小 时 以 下；’**’代 表 化 时 3至 7小
时；’***’代表化时 l2小时以上
策略 2：
初始染色体随机生成 4条 7位十进制串；
迭代时间：45分钟 ；
优化后的 BP网络参数 =0．91 a=0．43 n=35；
随后的预测准确次数 37；
参考文献：
[1] w Sebiffm,m~，M Joost，Rwm ．0I曲 ∞ 0fthe Backpl叩日 一
／d~rithmforTriningMultilaye~Pe~'eeptromTedmical Rer,lt[1~]．
IJnive~ity Kob]6111g，hastitute of科 ，1993．
[2] I-leeht— el。∞ R．|Il啪叮 ot"BEd 唧 ∞ Neural Netw~ [C]．
Proe．IJCI~ 一89．1989．1—593．
[3] R P ．Pattem 血 ng Neural Netw0IkB[J]．珊匝
Cora l，胁 ，Nov．1989，47—64．
[4] SY mg，J NH啪ng．AnAlgebraic Projeeti~ ^I蛐 forovti,i~
Hidden Units Size and bm iⅡg Rates in Back—en3pll~ oll bm iⅡg
[J]．皿 ，1991，I：363—370．
[5] s Y mg，I-hiYuHen．AFl~ nim Appr~mo-fioR Redueti~(FARM)
farDete~nlnlg 0ptiⅡ岫lNumber~ffl-liddm u~its[J]．珊匝，1991，II：
l63—168．
[6] M T}Iag匝，M B M∞出．Trai,l~,lg Foed F0rWaId Networks with Mar-
quart．AJ~ thm[J]．皿匝 Tram．∞ Neural№tW0IkB，1994，5(6)：989
— 993．
[7] T P V嘲 ，J K M∞gi8，ect．Accelerated the c啊w日霹臣lce 0fthe Back
nDpag妇 I Methoa[J]．Bio．Cyt~m，1988，59(9)：256—264．
[8] 蔡国正，屈粱生．共轭梯度神经网络 的研究[J]．西安交通大学
学报 ，1995，29(8)：73—76．
[9] 叶东毅 ．BP网络的一个非单调学习算法[J]．模式识别与人工智
能，1997，10(3)：221—225．
[1O] 杨秋贵，张杰 ，张素贞 ．基于拟牛顿法的前向神经元网络学习
算法[J]．控制与决策，1997，12(4)：357—360．
[11] 袁曾任．人工神经网络及其应用[M]．北京：清华大学出版社，
2OOO
[12] JHHolland．Adll~ ollinNalural and Artifieal Srstems．Ann Arb∞．
MI：Univem tyMichigan P ∞．1975．
[13] 杨启文，等．遗传算法优化速度的改进[J]．软件学报，2001，12
(02)：270—275．
[14] 唐飞，膝弘飞．十进制整数编码遗传算法的模式定理[J]．计算
机科学，1999，12(6)：54—56．
[15] 潘正君，等．演化计算[M]．北京，清华大学出版社 ，1999．
目 [作者筒介】 闫河(1 一1)，男(汉族)，陕西勉县人，信息获取与 处理专业在读博士生，讲师，主要研究方向：管理信 息系统、人工智能系统、图象处理技术、模式识别； 成卫(1 一7)，男(汉族)，重庆市人，硕士，副教授， 主要研究方向：数据库技术、人工智能系统
、 虚拟现
实技术；
潘英俊(19e)一9)，男<汉族)，重庆市人，教授、博导，主要研究方向：
光电测控与传感技术、智能机器人触觉传感技术、信息光学理论与应
用、微波治疗技术及仪器研制等；．
何光敏(1 73—6)，女(汉族)，四川平昌县人，本科，高级教师，主要研
究方向：多媒体技术。
(上接第 1112页J
参考文献：
[1] M ，VMiiIlie~o andA Col~i．The Ant ：0p血
I,y＆eolotq 0f o00p印 ng age,~[J]．皿匝 n锄鼬 ∞ Srstems，
Man，and c，bem cs—part B，l996，26(1)：l—l3．
[2] 王颖 ，谢剑英．一种 自适应蚁群算法及其仿真研究[J]．系统仿
真学报，20吆一l，l4，(1)：3l一33．
[3】 S B NeN~llemm and C D~rumeh．A C．meral Method Apl~lleabletothe
SearchforSimilaritiesintheAminoAcid&ql ce 0fTwoR ei|∞[J]．
J．1~1o1．Bio1．，1970，48：443—453．
[4] 毕军，付梦印，张宇河．一种改进的蚁群算法求解最短路径问题
一 l06 一
[J]．计算机工程与应用，2O113，(3)：107—109．
[5] 覃刚力 ，杨家本．自适应调整信息素的蚁群算法[J]．信息与控
制，20吆一6，31(3)：198—201．
[作者简介】
梁 栋(1974一)，男(汉族)，河北省行唐县人，硕士研
究生，主要研究方向为算法设计、生物信息学等 ；
霍红卫(1963一)，女(汉族)，陕西人，教授，博士，主
要研究方向为分布与并行计算、算法设计、生物信息
学等。
维普资讯 http://www.cqvip.com
自适应蚁群算法在序列比对中的应用.pdf
