文档库

最新最全的文档下载
当前位置:文档库 > 多重序列比对的蚁群算法

多重序列比对的蚁群算法

  收稿日期:2005-08-29  基金项目:国家自然科学基金资助项目(60473012);国家科技攻关项目(2003BA614A -14);江苏省自然科学基金(BK2005047);南京大学软件新技术国家重点实验室开放基金资助项目  作者简介:陈娟(1979-),女,硕士研究生,主要研究方向:生物计算和并行算法设计; 陈崚(1951-),男,教授,博士生导师,主要研究方向:算法设计和并行计算.

文章编号:1001-9081(2006)06Z -0124-05

多重序列比对的蚁群算法

陈 娟1

,陈 崚

1,2

(1.扬州大学信息工程学院,江苏扬州225009;

2.南京大学计算机软件新技术国家重点实验室,江苏南京210093)

(lchen@yzcn .net )

摘 要:序列多重比对是生物信息学特别是生物序列分析中的一个重要的操作。提出了一种解决多重序列比对的蚁群算法,利用了人工蚂蚁逐个选择各个序列中的字符进行配对。在算法中,蚂蚁根据信息素、字符匹配得分以及位置偏差等信息决定选择各序列中的字符的概率,通过信息素的更新与调节相结合的策略,以及参数的动态自适应调节方法,较为有效地解决了局部收敛的问题,加强了算法寻求全局最优解的能力。实验显示,该算法可以有效解决多重序列比对问题。

关键词:生物信息学;序列多重比对;蚁群算法中图分类号:TP301.6;TP18  文献标识码:A

0 引言

多重序列比对是生物信息学中的一个重要的问题,是基因识别、蛋白质结构预测、生物进化树的构建、基因组信息的分析等问题中用到的一个基本操作。在生物信息学中,比对的序列可以是DNA 或者是蛋白质序列。

假设已发现一个基因,并且知道它的功能,可以将它与基因组数据库中所有的序列片段进行比对,如果某个序列与该基因很相似,则可能它们的功能也相似,并且它们可能是同源序列。

通过同源序列的多重比对,能够发现与结构域相关的保守序列片段。对于一系列同源蛋白质,人们希望研究隐含在蛋白质序列中的系统发育的关系,以便更好地理解这些蛋白质的进化。在实际研究中,生物学家着重于研究相关蛋白质序列中的保守区域,进而分析蛋白质的结构和功能。所以要发现多个序列的共性,必须同时比对多条同源序列。

序列比对也可以用来发现遗传疾病的病因。可以将一些健康者的基因序列与一些疾病患者的基因序列进行比对,如果疾病患者的基因都有共同的某种变异,而没有一个健康者的基因含有这种变异,则很明显,这种变异是这种疾病的病因。

通过序列的多重比对,可以得到一个序列家族的序列特征。当给定一个新序列时,根据序列特征,可以判断这个序列是否属于该家族。进行多序列比对后,可以对比对结果进行进一步处理,例如构建序列的特征模式,将序列聚类构建分子进化树等。

总之,序列比对是生物信息学中的一个非常重要的基本操作。

多重序列比对的目标是发现多条序列的共性。简单来说,就是对于输入的多条序列插入空位并排列比对,使其达到相同的长度,并使得序列之间匹配字符的个数尽可能的多,而

不匹配字符和空位(gap )的个数尽可能的少。为了反映序列

比对的质量,要有一个定量的标准来度量它们之间的相似程度。我们可以通过计分函数来评估多重序列比对的质量。在实际计算中,su m -of -pairs (SP )模型是应用最为广泛的计分方法,该函数将所有两两序列比对得分的和作为多序列比对的得分。对于两个序列比对的分值,传统的基于编辑距离的计算方法,是将比对中所有列(即字符对)的得分求和作为两个序列比对的得分。其中对于非空位字符对的打分,通常我们可以根据打分矩阵(scoring matrix )得出,最常用到的打分矩阵有P AM 系列矩阵以及BLOS UM 系列矩阵。另外,对于空位的罚分,最常用到的是仿射罚分函数模型,该模型的参数通常根据经验设定。

在解决多重序列比对问题中,要解决两个问题,一是如何根据包括结构信息在内的生物学意义对给定比对打分,二是在打分机制确定的情况下,如何求得分值最高的最优比对。第一个问题要依据生物学的知识和实际问题的需要来决定。本文提出的基于蚁群的多重序列比对算法,主要是用来求解第二个问题,即在计分机制确定的前提下,对于给定的多条序列,寻找使得分值最高的最优比对。

文献[1]是双序列比对最经常用到的经典算法,该算法的时间和空间复杂度均为O (m n ),其中,m 和n 分别是两个序列的长度。虽然文献[1]的算法可以对两个序列找到最优解,但如果将这个算法直接延伸应用到多序列比对的问题上来,时空开销将达到O (2N

-1)(

∏N

i =1

|S

i

|),其中N 为序列的

个数,|S i |为第i 个序列的长度。所以算法虽然简单,在多重序列比对问题中却不实用。很多人对此算法作了改进,如基于Carrill o 和L i pman 的算法[5]的M S A [2],基于分治策略和

MS A 的DCA

[3]

,优化DCA 算法的OMA

[4]

等等,可是这些算

法处理的序列长度和数量仍受到很大限制。

多序列比对的启发式计算方法通常在适度牺牲正确性的基础上来提高计算效率。文献[6]是应用最为广泛的多重序列比对软件,它是高效的渐进方法的代表。文献[7]作了一

第26卷2006年6月

 

计算机应用

Computer App licati ons

 

Vol .26June

多重序列比对的蚁群算法

2006

© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.wendangku.net/doc/eee5bbb869dc5022aaea0022.html