基于前缀计算的序列比对研究.pdfVIP

计 算机 应 用 自动化技术与应用 2010年第29卷第 2期 ComputerApplications 基于前缀计算的序列比对研究 张 瑜，王继东 (西北师范大学 数学与信息科学学院，甘肃 兰州 730070) 摘 要：为了提高Smith—Waterman算法处理速度，同时不改变原算法的准确性，本文利用前缀计算方法修改Smith—Waterman算法， 并进行OpenMP并行化。在多核机上测试表明，前缀计算的共享并行化使得该局部比对算法的速度得到很大的提高。 关键词：并行编程 ；smith—waterman算法；前缀计算 、 中图分类号：TP31l 文献标识码：A 文章编号：1003～7241(2010)020035—04 ResearchonAlignmentBasedonPrefixComputation ZHANG Yu，WANGJi-dong (SchoolofMa~emaficsandInformationScience，NorthwestNomralUniversity，Lnaz_hou730070China) Abstract：InordertospeedupSmith—W atermanalgorithmsandkeepitshighprecision，prefixcomputationisusedtochangeSmiht— Watermanalgorithm，thenthisalgorithm isparallelizedusingOpenMP．Thetestonmulti—coresshowsthattheperfor— manceisimprovedmuchmorethanhteoriginalsequentialprogram． Keywords：parallelprogramming；Smith—W atemr na algorithm；prefixcomputation 1 引言 并行算法的引入，有效的降低了双序列比对的计算时 序列相似性是生物信息学处理中最基本的问题 。 间，更符合超长生物序列的特点。 如何获得结果更准确，时间、空间效率更高的序列相似 OpenMP~6】是一个为在共享存储的多处理机上编写并 性 比较算法是生物信息学研究中的一个重要课题 。在 行程序而设计的应用编程接口，由一个小型的编译器命 寻找基因序列最佳相似比对的算法中，Feelders等人… 令集组成 ，包括一套编译制导语句和一个用来支持它的 介绍动态规划方法进行精确查找两个序列的最优局部 函数库。OpenMP是通过与标准的Fortran和C＼C++结 比对 ，但因其代价太大，对超长生物序列直接应用这种 合进行工作的[儿引，对于同步共享变量、合理分配负载等 技术是不可行的。Stjepan Rajko[2】利用可分负载原理 任务，都提供了有效的支持，具有简单通用、开发快速的 将双序列 比对并行化 ，并对罚分 函数进行改进 ，将时间 特点。OpenMP是可移植多线程应用程序开发的行业标 和空间复杂度分别降低到O(mnlP)和O(m+n／p)。Katoh[】 准，在细粒度循环级别与粗粒度函数级别线程技术上具 对算法的优化包括对算法时间和空间复杂度的优化 ，还 有很高的效率。对于将串行应用程序转换成并行应用程 考虑结果的精确度 ，提出了基于FFT分析序列的算法 ， 序 ，OpenMP指令是一种容易使用且作用强大的工具，它 该算法能对 同源区快速识别 ，它的CPU 时间降低到 具有使应用程序因为在对称多处理器或多核系统上并行 NlogN。同时它还提出了一个简单 的分数系统来降低