文章编号"#$$#%&’’()*$$’+$,%$*#’%$-生物序列比对算法分析与比较钟诚#.宋彬*)#/广西大学计算机与电子信息学院.广西南宁(,$$$’0*/中国科学技术大学计算机科学技术系.安徽合肥*,$$*&+摘要"序列比对是生物信息学的一个非常重要的操作/它可以预测生物序列的功能1结构和进化过程等/文中首先介绍双序列比对的基本算法0接着分析和比较多序列比对的四个常用模型和三类算法以及并行比对算法0最后.给出一些研究问题/关键词"生物信息学0双序列比对0多序列比对0精确算法0近似算法0启发式算法中图分类号"23,$#04-##文献标识码"5生物信息学是一门综合数学1计算机科学和生物学的交叉学科6#7/生物信息学内涵非常丰富.其核心是基因组信息学.包括基因组信息的获取1处理1存储1分配和解释/基因组信息学的关键是8读懂9基因组的核苷酸顺序.即全部基因在染色体上的确切位置以及各:;5片段的功能0在发现新基因信息之后模拟和预测蛋白质空间结构.然后依据特定蛋白质的功能进行药物设计/生物序列中的信息在系统进化1生态守恒1疾病控制1病毒起源甚至<=>病毒统计和传播等的研究中是一个非常重要的基本工具6*7.因此.序列比对是生物信息学的基础/序列比对分为全局比对)?@A B C @5@D E F G H F I +和局部比对)J A K C @5@D E F G H F I+/全局比对要求把一个序列中的所有符号和另一个序列中的所有符号进行匹配比较.它描述整个序列的相似性/将两个序列进行比对就是双序列比对.它是比较两个生物序列相似性的重要工具/这个分析工具已经成功地运用到预测生物序列的结构1功能和进化例程中/随着生物医学中有更多的序列合成出来.人们开始用多序列比对来更好地研究生物序列/将多个序列进行比对就是多序列比对问题.它是一个将不等长的多个序列通过插入空格变成等长的过程.这些位置上的空格代表着相比较的序列从共同的祖先通过插入L 删除操作的进化过程6,7/求解多序列比对问题的算法主要分为精确算法1近似算法和启发式算法三种/#双序列比对对于两个长度分别为M 的序列有*M N OM P )*M +Q )M Q +)M Q +R**MS T M种比对情况.这是一个指数级复杂度的计算问题/#U &$年.;H H V @H G C F 和WX F Y K Z 基于动态规划方法6’7提出了第一个双序列比对算法6(7#U -*年.?A I A Z 对其做了进一步的改进6[7/<D \Y K Z B H \E 于#U &(年提出一个线性时间复杂度的算法来计算双序列比对6&7.而]^H \Y 和]D @@H \改进了该算法6-7/基于动态规划方法._G D I Z 和WC I H \G C F 给出一个局部比对算法6U 7/#U -&年.WC I H \G C F 和‘E E H \I给出一个计算双序列中a 个局部比对的算法6#$7/#U U #年.<X C F E 和]D @@H \给出一个线性空间复杂度的算法来计算双序列中a 个局部比对6##7/*多序列比对及其比对模型*b #多序列比对问题定义#设c 为符号集合.d 代表空格.给定序列组e #.e *.f.e a.多序列比对g 表示把这些序列放第*U 卷第,期*$$’年U 月广西大学学报)自然科学版+h A X \F C @A i ?X C F E j D k F D l H \Y D I ^);C I _K D ‘V +>A @/*U .;A /,_H m I /.*$$’!收稿日期"*$$’$’*#0修订日期"*$$’$-#&基金项目"广西自然科学基金)桂科自$,,U $$-+0国家-[,计划)*$$#55###$’#+作者简介"钟诚)#U [’+.男.广西桂平人.广西大学教授.博士/万方数据到!行中"每行一个序列"这些序列可以插入#"从而得到超级序列组$%"$&"’"$!"但序列组中每列不可全为#"使得($)(*+且,的代价-+)*%./$%/)0"$&/)0"’"$!/)00最小"其中./$%/)0"$&/)0"’"$!/)00代表第)列的代价1一般地"列代价反映该列中符号不相似的程度1多序列比对是一个组合问题"随着插入空格的数量与位置的不同"可得到很多种比对情况2%31目前"依旧没有非常有效的方法来求解实际的多序列比对问题1从多序列比对的定义可以看出"随着代价函数.定义的不同"就会产生不同的比对结果1对.的不同定义可得出不同的比对模型/456789:8;<=>:502%&?&@3A B C 比对/B C456789:8;0D 中心比对/E =8F :8F G F 456789:8;"也称为B ;H I 456789:8;0D 树比对/J I ::456789:8;0和熵比对/K 8;I =L M456789:8;01&1&B C 比对模型/B G 9N =O NC H 6I 456789:8;0B C 比对模型,中第)列的代价定义为./$%/)0"$&/)0"’"$!/)00*-%PQ RS P!./$Q /)0"$S/)00"其中./$Q /)0"$S /)00表示同一列中两个相应符号$Q /)0和$S/)0的代价1这个代价函数常称为B C /B G 9N =O N H 55N C H 6I F 0代价2%31B C 比对在实际应用中是一个非常有用的模型"被大家广泛地研究2%&?%T "%U ?&%31可以看出B C 比对实际上是将序列两两进行比对"这样序列在比对中的地位是相等的1若我们不知道序列之间的关系"那么我们就可以使用这个模型"通过假设序列相互之间不关联"来得出较好的结果1人们已经证明在B C 比对模型上求解多序列比对是V C W X H I >问题2&&3"并且Y 6=86Z Z =86和[:>=\H 还证明了即使对于符号集只含两个元素的情况"在B C 比对模型上求解也是个V C N X H I >问题2&&31此外"若假设序列间地位相等"则没有充分利用自然序列间本身具有的关联性"也没有建立在统计学的基础上"并且当序列中有一个符号发生改变时"结果就会有很大的变化"这和实际情况不符1&1]中心比对模型/E =8F :8F G F 456789:8;"B ;H I 456789:8;0中心比对模型第)列的代价定义为./$%/)0"$&/)0"’"$!/)00*968^_-‘a #b -cd *%./$d/)0"^0"也就是说"为了定义,的代价"重新构造,中每一列的符号或空格"这样就得到一个和所有输入序列的代价最小的e 中心f 序列1这个e 中心f 序列就可以代表输入的诸序列2%T 31与B C 比对模型相比"中心比对模型把两两比对转化为多对一的比对"这样比对次数大大减少"问题复杂性大大降低1但是"求解中心序列的过程却相当复杂"依旧需要考虑到所有的序列"这样就把两两比对的复杂性转嫁到求解中心序列的问题上"从而本质上没有突破1因此"依旧有非常困难的结果A 当符号集只含有g 个元素"代价函数定义简单/如匹配为@"不匹配为%0时"在中心比对模型上求解也是V C N X H I >问题2&]31当代价函数定义是任意的时候"中心比对更是一个<4h N B V C N X H I >问题2&g 31&1g 树比对模型/J I ::456789:8;0为了定义树比对,的代价/J I ::N i =F ;0"假设已知一个含!个叶子的进化树/K \=5G ;6=8H I MjC X M 5=7:8:;6i J I ::0k*/l "m 0"其中l 和m 代表树k 的点集和边集"树k 的每一叶子d 代表一个输入序列^d n !o %"!o &"’"!o p 代表树k 的内部结点1为了得到比对,的第)列的树代价A ./$%/)0"$&/)0"’"$!/)00"需要重建每个内部节点d 的符号或空格$d /)0"使得-/Q "S 0_m./$Q /)0"$S/)00最小1第)列的树代价定义为./$%/)0"$&/)0"’"$!/)00*-/Q "S 0_m./$Q /)0"$S/)00"其中./q "r 0用来衡量从q 到r 的e 进化f 距离"比对,第)列的树代价实际上就是进化树k 产生符号或空格的$%/)0"$&/)0"’"$!/)0最小代价2%31这个模型由B H 8s =O O 于%t u T 年首先提出2&T 3"在计算分子生物学领域中引起了广泛的关注1与B C 比对和中心比对相比"树比对更加符合自然界本身的状态"与自然进化过程有着天然的联系1比对又是建立在进化树基础上"减少了计算量1实际上"中心比对为树比对中进化树是星形的一种特殊情况1在进化树已知的情况下"在树比对模型上求解多序列比对问题显然是最佳的选择1但是进化树的构建常常需要T%&第]期钟诚等A 生物序列比对算法分析与比较万方数据多序列比对的结果!这样就产生了一个"死循环#!很难得到满意的结果$%$&熵比对模型’()*+,-./012)34)*5熵比对模型6第7列的代价定义为8’9:’75!9%’75!;!9<’755=>?@A ?B CD 7@0,2E 7@!其中D 7@代表符号@在第7列出现的次数!即D 7@=?F G’9F ’75=@5!G ’9F ’75=@5=:!HI !若9F’75=@!其余情况$E 7@代表符号@在第7列出现的概率$直观上看!每一列的变换越大!该列的熵越大J 熵越小!即每列的变换越小!也就越相似!求出熵最小的情况就是最"相似#的比对$K L 比对M 中心比对和树比对模型都是建立在双序列比对的基础上!而双序列比对问题本身也是一个比较复杂的问题!仍然需要继续研究$熵比对模型则摆脱了这个"怪圈#!从一个新的角度来解决问题!但熵比对模型的正确性和实用性还没有得到生物学家的公认$N 多序列比对算法的分析与比较动态规划算法是求解多序列比对问题最直接的方法$它不仅可以得出精确最优解!还是后面许多近似算法M启发式算法的基础$当序列条数不太多M 序列长度不太长时!动态规划算法能够有效地解决问题$但是!在生物信息学中!需要比对的序列长度常常很长!序列条数也较多!这样动态规划算法就显得"力不从心#了$这时!可以降低"标准#!不再求精确解!而只求出近似的比对结果就行了$为此!许多近似算法应运而生$N O :精确算法设P :!P %!;!P <是<个给定的序列!每个序列的长度分别为Q :!Q %!;!Q <!P 7R F S 代表P 7序列中第F 个符号!T ’7:!7%!;!7<5代表以P :R 7:S !P %R 7%S !;!P <R 7<S 结尾前缀的最优比对代价!则动态规划算法为T ’7:!7%!;!7<5=31)T’7:>:!7%>:!;!7<>:5U V ’P :R 7:S !P %R 7%S !;!P <R 7<S 5!T ’7:!7%>:!;!7<>:5U V ’>!P %R 7%S !;!P <R 7<S 5!WT ’7:>:!7%>:!;!7<5U V ’P :R 7:S !P %R 7%S !;!>5!T ’7:!7%!;!7<>:5U V ’>!>!;!P <R 7<S 5!WT ’7:!7%>:!;!7<>:!7<5U V ’>!P %R 7%S !;!>5!X Y Z W可以看出!空格出现的组合方式有%<>:种’全为空格的情况不满足比对条件5$整个算法的初始M 终止和迭代步骤与双序列比对的动态规划算法完全相同R :&S$该算法需要建立一个Q :[Q %[;[Q <规模的矩阵$为了计算矩阵中每个元素的值!需要考虑到每列中%<>:种空格的组合方式$若最终比对序列中的每条序列的长度均为Q !则动态规划算法的空间复杂度为Q <!时间复杂度为\’%<Q <5$动态规划算法复杂的时空复杂度!给计算带来很大的不便$于是人们试图利用各种方法来改进动态规划算法$]^++100,和_1-3^)在K L 模型中!提出通过减少计算体积来改进动态规划算法的方法$其基本思想就是!通过两两比对计算比对的上界!若在<维的比对矩阵中的元素超过了上界!就不予考虑!从而简化了动态规划算法R :%S$还可以用寻找最短路径的方法来改进动态规划算法$考虑这样一个有向无环网状图!图中的顶点集为‘!边集为a !使得‘=H ’b :!b %!;!b <5c b 7=I !:!;!Q 75!a=B d A H I !:e<H ’f !f U d 5c f !f U d A ‘!d g I e $这样!从顶点P =’I !I !;!I 5到顶点h =’Q :!Q %!;!Q <5的一条路径对应于一个序列比对R %i S$K -,j 24将求解最短路径问题中的/k 算法用来改进动态规划算法以计算多序列比对R %l S$m n 4o ^和m 3^1将这种/k 算法直接运用到多序列比对中R %p S $i :%广西大学学报’自然科学版5第%q 卷万方数据实际上!"#$作为现在少有的试图求最优比对的软件之一!就是用分枝界限方法和%&’()*+,的最短路径算法相结合来改进动态规划算法的时空复杂度-./01此外!2&33&,4!5&)36和789:,+使用双动态规划算法考虑序列的三维空间结构及其比对-.;01<1.近似算法首先介绍近似算法的性能比=概念!它使得对于问题中的所有实例>有?@>A B C D E @>A F =!其中?@>A 表示实例在算法?中的代价!C D E @>A 表示在最优算法中的代价15G )H &6I 于J ;;<年提出了第一个在#K 比对模型上的近似求解中心方法@L 68*6+)*,+46*M N I A 1其基本原理是!将中心比对模型与#K 比对模型O 融合P 起来!把中心比对模型中O 中心序列P 的概念引入到#K比对模型中!从而简化计算1其基本步骤是从给定的Q 个序列中选择一个中心序列R S 使得T QU V J W @R S !R UA 最小!其中W @R S !R U A 代表R S 和R U 双序列比对的最优代价X 然后!将Y Z [R S\的序列一个接一个地加入到比对]中!使得每个新加入的序列与R S 的双比对是最优的@若需要!则在比对前的序列中插入空格A !直到所有的序列都被加入为止!这样就得到了Q 个序列的多序列比对]!Y V @R J !R .!^!R QA 1该算法的时间复杂度为C @Q.>.A 1已经证明!中心方法得出的比对代价至多是最优代价的.倍-J _!J ‘01在中心方法的基础上!a ,H 8,!b ,c 6+和K 6:d 86+提出了>Z )*,+)方法1它的基本思想是!同样选择一个中心序列R S !将Q 个已知序列分成若干组!每组都包含R S 且共有>个序列!每组比对这>个序列!通过中心序列R S 将各组序列组合起来得到最终的比对1这种方法的难点是如何分组!具体细节请参看文献-J ;01上述方法均是将比对中每种情况进行穷举来求近似解1于是!人们想到!能不能加一定的限制条件!这样就可以不去考虑很少出现最优解的情况!而只考虑常会出现最优解的情况1e S Z I &,9N 8,3比对1设Y V @R J !R .!^!R QA 是Q 个序列的集合!每个序列的长度为f !它们的比对]中每条序列的长度是>1一个S Z I &,9N 8,3比对是指!对于任意的g !U 和h !如果序列R U 中的第g个符号在比对]中的第g i 列!序列R h 中的第g 个符号在比对]中的第ji 列!则k g i Z j i k F S 1也就是说!空格被O 均匀P 地插入到各个序列中!每个序列的第U 个位置至多与别的序列的第U 个位置相距S 1然而!S Z I &,9N 8,3比对的求解同样是建立在#K 比对模型和中心比对模型上的l K Z M ,+I 问题-J _!.<01b &!a &8和b G )M 689给出了在#K 比对模型和中心比对模型上的多项式时间近似求解算法1算法的基本思想是!构造在$m n o $5nS Z 5$K 限制条件下问题的K p $#解!利用这个K p $#解来得到想要的结果1q $:6+,96S Z 9,r#K 比对1求比对]使得每个序列中平均只有S 个空格插入和删除!并使得#K 代价最小1下面看看b &给出的$:6+,96S Z 9,r#K 比对的K p $#算法-</01它的理论依据是s 设t 是序列R J!R .!^!R u 的比对]的长度!v h !u 是符号w在]中的第h 列的出现次数!#K 的代价函数表示为x D @]A V T th V J Tw yzw !z {T |[}\v h !w v h !z !其中v h !u B u 表示符号w 在第h 个位置的概率1因此!可用v h !uB u 作为元素得到大小为t~@k !k "JA 的概率矩阵1这样!算法可以如此来计算s 随机地从u 个序列中选择=个序列@如图J 所示A X 穷举所有的比对!得到这=个序列的O 正确P 比对]=X 然后!计算这个比对]=的概率矩阵!并假设这个矩阵就是比对]的概率矩阵X 按照]的概率矩阵计算原先Q 个序列的比对!得出需要的结果1图J 任取=个序列的比对#J .第<期钟诚等s 生物序列比对算法分析与比较万方数据有了!"#$%&#’(&%)*+比对的结果,就可以求’(-.%&/0%1比对2首先,动态地把序列切成小的碎片,使得每个碎片满足前面!"#$%&#’(&%)*+比对的条件,且每个碎片的*+代价大约为’345,平均每个序列的碎片有’3次插入或删除6然后,用前面!"#$%&#’(&%)*+比对的+7!*算法来处理碎片8如图596最后,将碎片的结果组合起来,得到原问题的结果2因为考虑到采用的是’(-.%&/0%1比对,所以每个碎片的错误最多为’452这里问题的难点是碎片如何划分:具体内容请参考文献;<=>,该算法的性能比是?8@A 5B 83(5(@B ’99;<=>2图5序列的分割<C <启发式算法在启发式算法中,比较重要的一类是渐进比对方法8+$/&$#D D ."#!1.&0E #0F G#F H /-D 92它将两个多序列比对的结果合并成一个多序列比对2多序列比对软件I J !K L M N 和O 1P D F %1Q 就是借助向导树8&P .-#F $##9使用该方法的2O 1P D F %1Q 首先使用动态规划算法求出每两个序列间的最优比对,并把结果存储到代表进化距离的距离矩阵并构建进化树6然后,用进化树作R 向导S ,对序列渐进比对,具体的内容可参看;<@,<5>2迭代方法也是求解多序列比对的常用方法2常见的有T #$&#$(GP 0D /0算法和*%0U /V V 算法等2@W X <年,*%0U /V V提出了用迭代方法来作树比对2其基本思想是,将树中的内部节点放上序列,选择其中一个顶点Y ,使用相邻的三个节点进行比对,依次重复做,直到结果不再改进为止2在图<所示的迭代方法中,将圆上的三个序列依次进行比对,直到树上的代价不再减少,这样就得到了需要的结果;@Z ,<<>2图<*%0U /V V 的迭代算法图[多个序列中的E /F .V块多序列比对的一个重要的应用就是寻找多个序列中R 固定S 的区域,通常把这些R 固定S 的区域称为E /F .V 块2图[的粗线表示的就是E /F .V 块,这些E /F .V 块没有必要绝对的相同,而只需要E /F .V 块比与其他的区域相似得多即可2目前,求解E /F .V 块的常用方法有隐马尔柯夫模型8\.--#0G%$U /"G/-#19和M .]]D 取样8M .]]D D %E )1.0&92它们的基本思想都是将E /F .V 块作为随机的分割,然后用自学习的技巧,得出结果2所不同的是,M .]]D 取样是假设E /F .V块中的元素相互不关联,而隐马尔柯夫模型假设相互关联;<[>2[并行比对算法最直接的方法是,人们尝试把动态规划算法并行化从而降低序列比对的时空复杂度2由于动态规划X @5广西大学学报8自然科学版9第5W卷万方数据算法中!矩阵中的元素值依赖于左边一点"上面一点和对角线上一点#因此!线$上的点在之前的点的值已知的情况下!可以并行地执行#对于双序列比对!该算法若使用%个处理器则时间复杂度由&’%()降到&’%)#当两个生物序列比较相近时!动态规划矩阵中只有部分元素是有价值的#若加入一个限制条件*!则串行比对算法只要&’*%)时间!并行比对算法可以用&’*)个处理器在&’%)时间内完成’图+)#由此可推广到多序列比对即动态规划矩阵是,维’,-()的情形#图.是/维的情况!同样若加上限制条件*!则串行比对时间复杂度为&’*(%)0若使用&’*()个处理器!则并行比对的时间复杂度为&’%)1/+2#图+双序列并行比对方法图./维的并行比对方法3444年!56787!97:;<78;和=>?8@:8;运用计算前缀的方法1/.2!使用&’%A 6@B %)处理器!设计一个时间复杂度为&’C 6@B %)的双序列比对并行算法#3443年!D >8B >8和=7E F @E 提出一个基于迭代的多序列比对算法1/G 2!它的基本思想是!第3步!把输入的,个序列随机地分成两组!将两组之间的序列进行比对!并将比对结果和空格位置记录下来0第(步!若新的比对结果比当前比对的结果好!就将标记设为H !否则为I 0第/步!若第(步中的标记设为H !则用第3步中记录的空格位置更新当前的比对!更新过的和没有更新过的比对作为下一次循环的输入0如此下去直到结果达到某个标准为止#显然!迭代算法的基本思想是以后的结果由当前的输入来决定!这种串行关系给并行化带来一定困难#J F ?K L ;M ;等人将D >8B >8N =7E F @E 迭代算法改造成并行算法1/O 2P 并行计算所有’(,Q 3Q 3)种可能的分割或’,R ,’,Q 3)A ()种限制的分割’每组序列的数目大大影响到最后的结果!若在第3组中的序列只有一个或两个则结果会很好!这样分割的情况就从’(,Q 3Q 3)种限制到了’,R ,’,Q 3)A ()种)!将得出的最好结果作为下一次循环的输入#S K >E B 等人于344+年改进了该算法1/42#另外!T ;F 7F ?K 等人在使用5U 算法思想求多序列比对的基础上!提出一个并行算法来求多序列比对!将执行时间降到了人们能够V 忍受W 的范围内1X Y 2#Z B 7[>E 等人提出一个新的基于遗传算法的多序列比对算法!且将算法改写为并行算法来降低时空复杂度1X 32#+结语多序列比对问题依旧是当今分子生物学中最具有挑战性的研究问题之一#文献132给出了关于多序列比对的公开讨论问题P ’3)如何设计一个实用的多序列比对程序来处理成千上百的序列比对\’()如何将多序列比对与进化过程统一起来\自然地!可以考虑用进化树来解决该问题!但是人们知道产生进化树是=5]^Z _N ?;8‘问题!没有_S 5^!于是!问题依旧需要探索#’/)能不能利用序列中特殊区域的信息!使多序列比对成为一个交互式的过程\该问题的结果将是解决组合复杂性的关键#如何在_(_!a 8K ‘!D ^_A D ^_U!b =c ^d !e c f f=;:8K g 等并行计算模型上设计具有良好加速比的可扩放的动态规划并行算法和序列比对并行算法!以及如何更好地考虑到序列的空间结构进行比对等都是需要探索的课题#此外!如何借鉴近似串匹配并行算法1X (2的设计思想来开发高效的多序列比对并行算法也是一个值得重视的方向#参考文献P 132S h K ;E B !T ]7!=i j ?;E B #e 788>E :S @k K l F K Ee @<k 7:;:K @E ;6=@6>l 76;8D K @6@B [1=2#e ;<m 8K ‘B >!=;F F ;l ?7F >::FP 43(第/期钟诚等P 生物序列比对算法分析与比较万方数据!"#$%&’’()**)+,)-./01’23’$(4562&/7(85%98+:&;2&<=3/>2?/&’&@3&6A &5/2B 6=&6>26?C 1/0B &6&>2A565/1’2’,7-+!0/&A 3/5%$C 1/0B &6&>2A ’569D ;0/3>206()***(E F G H I J H E K L H H *+,H -M 06N 5/0M (85%9O 8(71%P 2!+4Q .=3/>2?/&’&@3&6A &5/2B 6=&6>’,7-+!0/&A 3/5%R 1’>&=5>2A ’569D ;0/3>206J #C &0%1569$%5A >2A &()**E (E *K L E E F +,S -T &//=56:D +4165=2A $%0B %5==26B ,!-+$%26A &>06J $%26A &>06U 62;+$%&’’(E V W K +,W -Q &&9/&=56RT (836’A CO4+.B &6&%5/=&>C 095??/2A 5X /&>0>C &’&5%A CY 0%’2=2/5%2>2&’26>C &5=2605A 29’&@3&6A &’0Y ><0?%0>&26’,7-+7!0/T 20/(E V K *(S Z J S S H L S W H +,F -M 0>0C[+.62=?%0;&95/B 0%2>C =Y 0%=5>A C 26BX 20/0B 2A 5/’&@3&6A &’,7-+7!0/T 20/(E V Z )(E F )J K *W L K *Z +,K -\2%’A C X &%B 4R +./26&5%’?5A &5/B 0%2>C =Y 0%A 0=?3>26B =5]2=5/A 0==06’3X ’&@3&6A &’,7-+O 0==0Y .O !(E V K W (E Z J H S E L H S H +,Z -!1&%’D8(!2//&%8+[?>2=5/5/2B 6=&6>’26/26&5%’?5A &,7-+O 0=?3>.??/2A T 20’A 2(E V Z Z (S J E E L E K +,V -R =2>C#^(85>&%=56!R +"9&6>2Y 2A 5>2060Y A 0==06=0/&A 3/5%’3X ’&@3&6A &’,7-+7!0/T 20/(E V Z E (E S K J E V W L E V K +,E *-85>&%=56!R (D B B &>!+.6&<5/B 0%2>C =Y 0%X &’>’3X ’&@3&6A &5/2B 6=&6>’<2>C5??/2A 5>206>0>:Q .A 0=?5%2’06’,7-+7!0/T 20(E V Z K (E V K J K )H L K )Z +,E E -\356B_(!2//&%8+.>2=&L &Y Y 2A 2&6>(/26&5%L ’?5A &/0A 5/’2=2/5%2>15/B 0%2>C =,7-+.9;.??/!5>C(E V V E ()J H H K L H W K +,E )-O 5%%2//0\(‘2?=564+#C &=3/>2?/&’&@3&6A &5/2B 6=&6>?%0X /&=26X 20/0B 1,7-+R ".!703%65/06.??/2&9!5>C(E V Z Z (S Z J E*K H L E*Z )+,E H -‘2?=564(./>’A C 3/R^(a &A &A 20B /374+.>00/Y 0%=3/>2?/&’&@3&6A &5/2B 6=&6>,7-+$%0A Q 5>/.A 59R A 2(E V Z V (Z F J SS E )L SS E W +,E S -M 3’Y 2&/94+D Y Y 2A 2&6>=&>C 09’Y 0%=3/>2?/&’&@3&6A &5/2B 6=&6><2>C B 35%56>&&9&%%0%X 0369’,7-+T 3//&>260Y!5>C &=5>2A 5/T 20/0B 1(E V V H (W W J E S E L E W S +,E W -M 3’Y 2&/94+./B 0%2>C =’06R >%26B ’(#%&&’(569R &@3&6A &J O 0=?3>&%R A 2&6A &569O 0=?3>5>2065/T 20/0B 1,!-+Q &<b 0%P J O 5=X %29B &U 62;&%’2>1$%&’’(E V V K +,E F -R 56P 0Y Y4(a %3’P 5/7+#2=&85%?’(R >%26BD 92>’(569!5A %0=0/&A 3/&’J #C &#C &0%1569$%5A >2A &0YR &@3&6A &O 0=?5%2’06,!-+:&5926B!.J .992’068&’/&1(E V Z H +,E K -85>&%=56!R +"6>%093A >206>0O 0=?3>5>2065/T 20/0B 1J !5?’(R &@3&6A ’(569M &60=&’,!-+‘06906J O C 5?=56569\5//(E V V W +,E Z -T 5A 0064(.69&%’068+!3/>2?/&’&@3&6A &5/2B 6=&6>,7-+703%65/0Y !0/&A 3/5%T 20/0B 1(E V ZF (E V E J E W H L E F E +,E V -T 5Y 65c (‘5<&%D ($&;N 6&%$+.??%0]2=5>2065/B 0%2>C =’Y 0%=3/>2?/&’&@3&6A &5/2B 6=&6>,7-+#C &0%&>2A 5/O 0=?3>&%R A 2&6A &(E V V K (E Z )J )H H L )S S +,)*-M 3?>5R (a &A &A 20B /37(R A C 5Y Y &%.+!5P 26B >C &’C 0%>&’>L ?5>C ’5??%05A C >0’3=L 0Y L ?52%’=3/>2?/&’&@3&6A &5/2B 6=&6>=0%&’?5A &&Y Y 2A 2&6>26?%5A >2A &,.-+$%0A +F >CR 1=?+06O 0=X 265>0%25/$5>>&%6!5>A C 26B (‘Q O R V H K ,O -+T &%/26J R ?%26B &%(E V V W (E )Z L E S H +,)E -R A C 3/&%M 4(./>’A C 3/R ^(‘2?=5647+.<0%P X &6A CY 0%=3/>2?/&5/2B 6=&6>A 06’>%3A >206569565/1’2’,7-+$%0>&26’J R >%3A >3%&(^36A >206569M &6&>2A ’(E V V E (V J E Z *L E V *+,))-T 062N N 062$(4&//5c &90;5M +#C &A 0=?/&]2>10Y =3/>2?/&’&@3&6A &5/2B 6=&6><2>CR $L ’A 0%&>C 5>2’=&>%2A ,7-+#C &0%&>2A 5/O 0=?3>&%R A 2&6A &()**E ()W V G E L )I J F H L K V +,)H -‘2!(!5T (856B‘+^26926B ’2=2/5%%&B 206’26=561’>%26B ’,.-+$%0A H E ’>.O !R 1=?+[6#C &0%10Y O 0=?3>26B,O -+Q &<b 0%P J .O !$%&’’(E V V V (S K H L S Z )+,)S -7256B#(‘5</&%D ‘(856B‘+./2B 626B’&@3&6A &’;2556&;0/3>2065/>%&&,.-+O 0=?/&]2>15695??%0]2=5>206+$%0A +)F >C.O !R 1=?+[6#C &0%10Y O 0=?3>26B ,O -+Q &<b 0%P J .O !$%&’’(E V V S (K F *L K F V +,)W -R 56P 0Y Y 4(:03’’&53$+‘0A 5>26B>C &;&%>2A &’0Y 5R >&26&%>%&&26565%X 2>%5%1=&>%2A ’?5A &,7-+!5>C$%0B %5=(E V K W (V J )S *L )SF +,)F -a 0X 515’C 2\("=52\+"=?%0;&=&6>0Y >C &.d 5/B 0%2>C =Y 0%=3/>2?/&’&@3&6A &5/2B 6=&6>,e -+$%0A 0Y V >C<0%PL ’C 0?06M &%60=&"6Y 0%=5>2A ’(#0P 10J U 62;&%’5/.A 59&=1$%&’’(E V V Z (E )*L E H *+,)K -R ?03B &7‘+R ?&&926B3?4165=2A$%0B %5==26B./B 0%2>C =’Y 0%Y 26926B[?>2=5//5>>2A &?5>C ’,7-+R ".!7.??/!5>C(E V Z V (S V G W I J EW W )L EW F F +*))广西大学学报G 自然科学版I 第)V 卷万方数据!"#$%&’()*+%,)-./0)1234)5678-29,:78;<52-=5’>’?<’@A ’35-6@,’@2!B $/C 87A /7:D 29E 78&197=7@F ’8@7,’%@:78,)2-A 1+*7&G 7H I @-J ’81)53A )(’,GC 8’11+K L L M +L N O L L /!"L $P-55-),Q *+F -15’>+%@6J )8R /;<52-=5’=872’-@1’?<’@A ’)5-6@,’@2<1-@6(7<S 5’O (G @),-A=8768),,-@6!T$/U 7,=<2’81)@(U 9’,-128G+"N N N +"M H V WK "/!V N $X -;+;)Y +P)@6X /Z ’)87=2-,)5,<52-=5’)5-6@,’@2E -29-@)S )@(-@=75G @7,-)52-,’!B $/C 87A/V "@(3U ;>G ,=/[@*9’78G7:U 7,=<2-@6+Z ’E \78&H 3U ;C 8’11+"N N N +M "D O M V M /!V K $*97,=17@T +.-66-@1]+F -S 17@*/U 5<12)5P H %,=87J -@629’1’@1-2-J -2G 7:=8768’11-J ’,<52-=5’1’?<’@A ’)5-6@,’@22987<691’?<’@A ’E ’-692-@6+=71-2-7@O 1=’A -:-A 6)==’@)52-’1)@(E ’-692,)28-^A 97-A ’!T $/Z <A 53A -(1Q ’1+K L L M +""_""‘H Ma b V O Ma #N /!V "$0’@6]+]775-225’Q 0/C 8768’11-J ’1’?<’@A ’)5-6@,’@2)1)=8’8’?<-1-2’27A 788’A 2=9G 576’@’2-A 28’’1!T $/T ;75R J 75+K L #b +"D H V D K O V a N /!V V $>)@&7::]/;-@-,)5,<2)2-7@28’’17:1’?<’@A ’!T $/>%3;T 7<8@)57@3==5-’(;)29+K L b D +"#H "D O M "/!V M $]<8S -@Q +R ((G>+c 87693+d e f g /Y -7576-A )5>’?<’@A ’3@)5G 1-1H C 87S )S -5-12-A ;7(’517:=872’-@1)@(@<A 5’-A )A -(1!;$/Z ’E \78&H U ),S 8-(6’I @-J ’81-2GC 8’11+K L L #/!V D $I &-G ),)Z +%,)-./C )8)55’5,<52-=5’)5-6@,’@21)@(29’-8-,=5’,’@2)2-7@7@U ;D !T $/F ’@7,’%@:78,)2-A 1K L L V +M H K N V O K N #/!V a $>35<8<+Z 0<2),<8)+c ;’98728)/Y -7576-A )51’?<’@A ’A 7,=)8-17@<1-@6=8’:-^A 7,=<2)2-7@1!B $/C 87A K V 29%R R R%@2’8@)2-7@)5C )8)55’5C 87A ’11-@6>G ,=71-<,+X 7135),-271+U )5-:78@-)H %R R RU 7,=<2’8>7A -’2GC 8’11+K L L L +a D V O a D L /!V b $;C Y ’86’8+C T;<@17@/3Z 7J ’58)@(7,-h ’(5-2’8)2-J ’128)2’6G:78)5-6@-@6,<52-=5’=872’-@1’?<’@A ’1!T$+U 7,=<23==5Y -71A -+K L L K +M b L O M #M /!V #$;%19-&)E )+;.719-()+;.-871)E )+d e f g /;<52-=5’1’?<’@A ’)5-6@,’@2S G=)8)55’51-,<5)2’()@@’)5-@6!T$/U 7,=<23==5Y -71-A -+K L L "H"a b O "b V /!V L $*-’@6c \+C ’2’8T ;+[=9-80+d e f g /C )8)55’5,<52-=5’1’?<’@A ’)5-6@,’@2<1-@61=’A <5)2-J ’A 7,=<2)2-7@!B $/C 87A7:29’K L L D %@2’8@)2-7@)5U 7@:’8’@A ’7@C )8)55’5C 87A ’11-@6/Y 7A )Q )27@H U Q UC 8’11+K L L D +V Ha N O a b /!M N $\)1<19-*+\<2)&)3+c ’@2)87[+d e f g /R ,=57G -@634)5678-29,-@=)8)55’5,<52-=5’=872’-@1’?<’@A ’)5-6@,’@2!T $/%C >T >%F Z 72’1+L b O ;C >O K a O M +K L L b +K L O "M /!M K $Z 6<G ’@.]+\719-9)8)%+\),),78-c +d e f g /3=)8)55’59G S 8-(6’@’2-A)5678-29,:78,<52-=5’=872’-@1’?<’@A ’)5-6@,’@2H R J 75<2-7@)8GA 7,=<2)2-7@!B $/C 87A /7:29’"N N "U 7@68’117@U R U +X 7135),-271+U )5-:78@-)H %R R R U 7,=<2’8>7A -’2GC 8’11+"N N "+K H V N L O V K M /!M "$钟诚+陈国良/C Q 3;和X 3Q C Y >模型上的近似串匹配并行算法!T$/软件学报+"N N M +K D _"‘H K D L WK a L /i j k l m n o n k j pq r s t k u o n r jv r u w o r n x y z x j q x k l o {j s x j |k l {r u o |}s nB .[Z F U 9’@6K+>[Z F Y -@"_K /U 755’6’7:U 7,=<2’8)@(R 5’A 287@-A 1)@(%@:78,)2-7@+F <)@6^-I @-J ’81-2G +Z )@@-@6+D V N N N M +U 9-@)~"/]’=2/7:U 7,=<2’8>A -’@A ’)@(*’A 9@7576G +I @-J /7:>A -/)@(*’A 9/7:U 9-@)+.’:’-+"V N N "b +U 9-@)‘i w n |u k q |H >’?<’@A ’)5-6@,’@2-1)@-,=782)@27=’8)2-7@-@Y -7-@:78,)2-A 1/%29)1S ’’@<1’(1<A A ’11:<55G27=8’(-A 229’:<@A 2-7@+128<A 2<8’+)@(’J 75<2-7@7:S -7576-A )51’?<’@A ’1/%@29-1=)=’8+17,’:<@(),’@2)5)5678-29,1:78=)-8E -1’1’?<’@A ’)5-6@,’@2)8’-@287(<A ’(+29’,<52-=5’)5-6@,’@2,7(’51)@(,)-@&-@(17:,<52-=5’)5-6@,’@2)5678-29,1)8’)@)5G h ’()@(A 7,=)8’(+)@(29’=)8)55’5)5678-29,1:78S -71’?<’@A ’)5-6@,’@2)8’1<,,)8-h ’(/0-@)55G +17,’7=’@=87S 5’,1)8’6-J ’@/!x m "r u p n H S -7-@:78,)2-A 1~=)-8E -1’1’?<’@A ’)5-6@,’@2~,<52-=5’1’?<’@A ’)5-6@,’@2~’^)A 2)5678-29,1~)==87^-,)2-7@)5678-29,1~9’<8-12-A )==87)A 9’1_责任编辑刘海涛‘K""第V 期钟诚等H 生物序列比对算法分析与比较万方数据。