基于蚁群算法与中心比对算法的多序列比对研究

王彩芸,蔡乐才

摘 要:多序列比对问题是生物信息学中一个非常重要且具挑战性的课题。为了克服以往算法应用于多序列比对时所遇到的比对序列数受限制以及比对寻优速度慢的缺点,提出一种基于蚁群算法与中心比对算法相结合的新求解算法,给出了具体的算法设计。该算法充分发挥了蚁群算法和中心比对算法的优越性,可提高求解MSA 问题的计算精度和计算速度,同时较好地解决了群体的多样性和收敛深度的矛盾。

关键词:多重序列比对;蚁群算法;中心比对算法;算法设计

中图分类号:TP301文献标识码:A

文章编号:1004-373X(2009)12-085-03

New Algorithm Based on Ant Colony Algorithm and Consensus Alignment

for Multiple Sequence Alignment

WANG Caiyun,CAI Lecai

(Sichuan University of Science and Engineering,Zigong,643000,China)

Abstract:Multiple sequencealignment is a most important and challenging task in bioinformatics.In order to solve the problems of both thealignment sequences number limitation and time-consuming which manyalignments can encounter in multiple sequencealignment,a newalignment based on ant colonyalignment and consensusalignment and concrete algorithm design are proposed.This newalignment not only sufficiently exerts the advantages of the twoalignments,but also improves the computing precision and speed,and which solves the contradiction between the diversity of population and the convergence speed.

Keywords:multiple sequencealignment;ant colonyalignment;consensusalignment;algorithm design

0 引 言

多序列比对(Multiple Sequence Alignment,MSA)是生物信息学中最重要、也是最有挑战性的任务之一。通过多序列比对,可以预测新序列的结构和功能,可以分析序列之间的同源关系,以及进行系统发育分析。 多序列比对是一个具有极高计算复杂度的组合优化问题[1]。

两序列对比目前应用最广的就是动态规划方法[2,3],求得最优解,但多序列比对问题的求解至今仍然是生物信息学中尚未解决的难题,已经证明多序列比对问题是一个NP 完全问题[4]。从问题提出到现在,研究者们就多序列对比方法进行了有益的探索,其中比较常见的多序列比对方法有Pileup 算法、Clustalw算法[5]、Carrillo-Lipman算法[6],还有DCA算法[7]。但这些算法的主要缺点是不仅搜索速度慢,运行过程中还占用过多的内存[8];进化算法主要有模拟退火算法(SA)、遗传算法(GA) 、免疫算法和蚁群算法(ACO)等,它们的主要思想都是通过反复迭代来逐步搜索到最优解[9]。上述这些算法虽然在求解多序列比对时得到了一些通用的、高效的序列,但是它们都不能有效地得到精确的解。这里在遗传算法的基础上通过综合运用蚁群算法与中心比对算法相结合的优势来求解多序列比对。

1 多序列比对的描述

多序列比对已经接近序列之间的朦胧区。但尽管如此,序列之间仍会共有由保守残基形成的局部区域,即序列模体。序列模体往往是蛋白质分子的重要功能位点所在,寻找这些序列模体,并用它们构建蛋白质二级数据库是多序列比对的重要任务之一。因此可以说,多序列比对的目的从序列相似性转移到了功能相似性。

多序列比对是目前为止在生物信息学中最常用的方法。多序列比对有着广泛的应用,其中包括:寻找蛋白质家族中的保守区域,蛋白质的聚类、分类,点突变检测,推断进化关系和构建系统发育树,帮助预测蛋白质结构等。

多序列比对的定义:给定κ条蛋白质序列S={S1,S2,…,Sκ},寻找最优比对,也就是说,寻找{S1′,S2′,…,Sκ′},使得满足如下条件:

(1) Si′是Si通过插入空位得到的,其相对位置保持不变;

(2) 对任意的i和j,有|Si′|=|Sj′|,即比对后的序列具有相同的长度;

(3) 对于所有的i和j,使得∑i∑jsim(Si′,Sj′)最大,或者∑i∑jcost(Si′,Sj′)最小。其中,sim(X,Y)是序列X和序列Y的比对相似性函数;cost(X,Y)是序列X和序列Y的比对罚分函数。

多重序列的比对B用一个二维矩阵表示。矩阵中的每一行对应于一个序列这个序列可能只是原来序列的一个简单复制,也可能在保持原序列中各残基相对顺序不变的情况下,插入若干个空位而形成的一个新序列。矩阵中不允许某一行同时为空位,因此矩阵的行数等于序列的数目。多重序列比对的目的就是对多个序列通过插入、删除等操作将之排列以达到相同的长度,同时使得矩阵中同列匹配的字符个数尽可能多,不匹配字符和空位个数尽可能少。对于每个矩阵都会有一个相应的适合度值,作为是否在遗传进化中继续生存产生下一代的依据。这里采用通用的SP 模型对比对的质量进行评估[8]。比对B的适应度函数为:

sp-score(j)=∑N-1i=1∑Nk=i+1p(cij,ckj)

式中:L为比对中各个序列的长度;第i条序列中第j个字符为cij(1≤j≤L );p(cij,ckj)为字符cij及ckj的记分。

2 蚁群算法和中心比对算法

蚁群算法是近来出现的一种新型的模拟进化算法,它由意大利学者M.Dorigo等人首先提出来[10]。蚁群算法实际上是模拟蚂蚁集群觅食规律而设计出的一种算法,蚂蚁在寻找事物的过程中会在其经过的路径上留下一种称为“信息素”的物质;其后经过该路径的蚂蚁会利用这些“信息素”经验来判断是否选择这条路径,并留下新的信息素以给后来的蚂蚁提供信息。即在个体寻优的过程中,每一只蚂蚁会利用这些信息素的浓度来矫正自己的行为,并把经验提供给后来的蚂蚁[11]。路径上的信息素浓度越高,该路径被蚂蚁选中的概率就越大。在开始时,蚂蚁被随机放置在路径结点上,并向可行的临近结点移动,信息素被存储在路径上。同时引入信息素挥发机制,即信息素会随时间的推移而逐渐挥发甚至消失。这样可以避免局部收敛的现象,还可以增大搜索空间。

中心比对算法是一种求解MSA 问题的快速启发式方法,它基于一个固定序列与所有其他序列的配对比对而建立的,这个固定序列有一中心,使用一种称为“一旦为空格,始终为空格”的技术将这些配对比对向中心汇集。即在中心与其他序列的优化比对过程中,会不断往中心序列中加入空格以适配比对,且决不移出已经加入的空格,也就是空格一旦加入到中心序列,就始终留在中心序列中,直到所有其它序列与中心序列优化比对完。算法描述如下:

步骤1:对于一组含有κ条序列的集合Ω,首先找出序列St,St∈Ω,使得∑i≠tscore(Si,St)的值最小,令A={St}。

步骤2:逐次添加Si∈Ω-{St}到A中,使Si与St的B比对值最小,并假设S1,S2,…,Si-1已经添加到A中。由于在分别与St进行比对的过程中需要加入一些空格, 故此时A ={S1′,S2′,…,Si-1′,St′}。按照两条序列比对的动态规划算法比较St′和Si,分别产生新的序列St″和Si′,再按照St″中添加空格的位置调节序列{S1′,S2′,…,Si-1′}成{S1″,S2″,…,Si-1″}, 并用St″替换St′,最后得到的比对即中心比对。

3 用蚁群中心比对算法相结合求解MSA

该算法主要是模拟自然界演化的周期性的特点。自然界的演化往往是进化和退化交替进行的,表现出周期性的特点。它是一个循环往复的过程,但不是一种简单的回复。这里所提出的算法就是使群体的进化有周期性,用精英保留策略使得群体不发生退化,保持进化的趋势特点,突变算子有可能使群体发生退化的特点。算法对一个进化周期的设计是:首先将序列进行编码,接下来使用遗传算子(交叉算子、变异算子、选择算子)对群体进行进化,当群体经过一定的进化代数后,不是直接进入下一个循环,而是先利用“滑动窗口”[10]检测出不匹配的区域,用蚁群算法“改善”这些区域:让蚂蚁逐渐遍历比对中每个序列的一个残基,直至全部残基被遍历完结束本次循环;经过一定的代数进化后,仅保留最优解;对最优个体所对应的序列组进行中心比对,比对后的序列组对应的染色体个体如果更优则取代最优解,重新生成其余个体,进入下一个周期。这种策略并非退化,而是尽快摆脱进化迟钝状态,开始一个新的进化周期。算法就是通过若干个这样的进化周期,最后找到最优解的。

具体算法设计如下:

Procedure ant-consensusalignment

begin

对序列进行编码初始化;计算P 中个体的适应值;

optimal-indivi←P 中最优的个体;

gen←0;

while gen

begin //一个进化周期开始

k←0;

while k

begin

使用遗传算子对初始化群体进化;检测不匹配区域;

用蚁群算法改善这些区域;

k←k + 1;

end;

//保留最优个体

if P 中最优个体好于optimal-indivi then optimal-indivi←P 中的最优个体

对最优个体所对应的序列组进行中心比对,比对后的序列组对应的染色体个体如果更优则取代最优解;

//在进入下一个进化周期前进行重组

S←{随机生成N-1个体};//N为种群规模

P←S+ {个体optimal-indivi};

gen←gen+1;

end;

end;

4 结 语

这里提出的基于蚁群算法与中心比对算法相结合的对序列比对算法有效地解决了局部收敛的问题,加强了算法寻求最优解的能力。利用该算法求解多序列比对问题不但减少了计算时间,而且改善了所求解的质量。因此,用一种进化算法协助另一种进化算法来使用往往能取得更为理想的结果,且在效率上更具优越性。

参考文献

[1][美]Andreas D,Baxevents,B F Francis Ouellette.生物信息学:基因和蛋白质分析的实用指南[M].李衍达,孙之荣,译.北京:清华大学出版社,2000.

[2]Thompson J D,Higgins D G,Gibson T J.CLUSTALW:Improving the Sensitivity of Progressive Multiple Sequence Alignment through Sequence Weighting,Position-Specific Gap Penalties and Weight Matrix Choice [J].Nucl.Acids Res.,1994,22:4 673-4 680.

[3]塞图宝,梅丹尼斯.计算分子生物学导论[M].朱浩,译.北京:科学出版社,2003.

[4]Jiang T,Wang L.On the Complexity of Multiple Sequence Alignment [J].Comput.Biol.,1994:337-378.

[5]Andrada M A,Sander.Bioinformatics from Genome Data to Biological Knowledge[J].Current Opinion Biotechnol,1997,6:675-683.

[6]Carrillo H,Lipman D J.The Multiple Sequence Alignment Problem in Biology[J].SIAM.Appl.Math.,1998:1 073-1 082.

[7]Stoye J,Moulton V,Dress A W.DCA:An Efficient Implementation of Thedivide-and-Conquer Approach to Si-multaneous Multiple Sequence Alignment[J].Comput.Applic.Biosci.,1997,6:625-626.

[8]张静乐,王世卿,王乐.具有新型遗传特征的蚁群算法[J].微计算机信息,2006,22(5):257-260.

[9]Chellapilla K,Fogel G B.Multiple Sequence Alignment Using Evolutionary Programming [J].Proc.IEEE Congress Evol.Comput.,1999:445-452.

[10]Dorigo M,Maniezzo V,Colorni A.Ant System:Optimization by a Colony of Coorperating Agents[J].IEEE Trans.on Systems,Man and Cybernetics,1996,26(1):29-41.

[11]Dorigo M,Caro G D.Ant Colony Optimization:A New Meta-Heuristic[J].Proc.Congress Evol.Comput.,1999:1 470-1 477.

[12]Krogh A.An Introduction to Hidden Markov Models for Biological Sequences[A].Computational Methods in Molecular Biology[C].Elsevier,1998:45-63.

[13]Lee L Z,Lee C Y,Su S F.An Immunity-based Ant Colony Optimization Algorithm for Solving Weapon-Target Assignment Problem[J].Appl.Soft Comput.2002:39-47.

[14]Wang L,Jiang T.On the Complexity of Multiple Sequence Alignment[J].Comput.Biol.,1994,1(4):337-348.

[15]胡桂武,郑启伦,彭宏.求解MSA 问题的新型单亲遗传算法[J].计算机工程与应用,2004,40(8):5-7,53.

[16]Lawrence C,Altschul S F,Boguski B,et al.Detecting Subtle Sequence Signals:A Gibbs Sampling Strategy for Multiple Alignment[J].Science,1993:208-214.

[17]Gen M,Cheng R.Genetic Algorithms and Engineering Design[M].John Wiley & Sons Inc.,1997.