多序列比对问题并行近似算法.pdfVIP

第35卷第5期 中国科学技术大学学报 V01．35，No．5 JOURNALOF唧RSITYOFSCIENCEANDTECHNOLOGYOFCHINA 2005年10B Oct．2005 文章编号：0253—2778(2005)05—0656—09 多序列比对问题的并行近似算法 宋彬1，陈国良2，鄢超2，沈一飞2 (1中国科学技术大学计算机科学与技术系，安徽合肥230027；2国家高性能计算中心，安徽台肥230027) 摘要：基于中心方法的思想，采用分治策略，在SIM口CREW模型上设计了一个使用 log＆)的并行近似算法．在实际情况中，由于logk远远小于m，相对于时间复杂度为 0(mZk2)的串行中。方法，该算法在理论上达到线性加速．与现有的并行算法相比， 它可以适用于任意情况，且易于分析时间复杂度．利用I。ARPBS模型的特点和并行 求前缀和的方法，调用LARPBS模型上求和与最大(小)值的并行算法，首次给出了 器，时间复杂度为O(m+loglogD)，其中D为序列两两比对的代价值的最大值．该 算法同样适用于任何情况，由于loglogD通常远小于m，所以它在理论上也是线性 加速的． 关键词：多序列比对；并行算法；SIMnCREW；LARPBS模型；SP比对 中图分类号：TP339，TP301文献标识码：A 0引言 sequence 多序列比对(multiple 性的问题．它广泛应用于寻找分子序列中的保守区域、预测种族的进化历史等领域[1]．多序 列比对问题又是一个组合问题，随着插入空格的数量与位置不同，可以得到多种比对情 orSP 况口]，这给问题的求解带来一一定的困难．在SP比对(sum-of-all—pairs 问题口]．现有常用的模型，如中心比对模型和树比对模型，多序列比对问题同样是NP-hard 问题，有的甚至是MAX-SNP-hard问题[3“]． 求解多序列比对问题有很多算法，动态规划算法是其中最直接的方法．它是一种完全算 法，可以得出精确最优解，且当序列条数不是太多、序列长度不是太长时是有效的．但该算法 解最短路径问题中的A’算法来改进动态规划算法求解多序列比对问题’6]，但这些改进的 收稿日期：2004-0,3—24；修回日期：200409—24 基金项目：国家“863”计划(2001AAIll04l，2002AAl04560)，中科院高标准高校建设项目． u吼ceduc12． 作者简介：宋彬．硕士生研究方向：并行算法，生物信息学E-mail；heather@mail 万方数据 第5期 多序列比对问题的并行近似算法 657 算法在最坏情况下时间复杂度依旧是十分复杂的．为解决多序列比对问题，Gusfied于1993 Star 年首次提出了在SP比对模型上的近似算法即中心方法[7](CenterMethod)．在此基础 制条件的多项式时间近似方法求解的算法口]．但这些近似算法依旧没有把时间复杂度降到 实用的范围内，并且这些方法通常只对特定情况有效，适用范围有一定的限制． 实际情况中，多序列比对问题中的序列条数较大(如大于100个)，上面提到的算法若是 串行执行，常常需要几天的时间．但若使用并行算法，让它们在并行机上运行，理论上就可以 算法[1目；Nguyen等给出了一个并行混合遗传算法[1”．上述算法都只给出了具体的实验数 据，很难进行详尽的算法复杂度的定量分析．而Ukiyama等人给出的并行多序列比对算 法口“只适合于序列组相似度较高的情况． 间复杂度为O(m+log女)的并行近似算法，其中k为序列个数，m为最长的序列长度．与时 间复杂度为O(m2k2)的串行算法相比，该算法几乎达到了线性加速，且保证了性能比为2． 与现有的或针