ｉ－Ｉ－算机应用ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓ《自动化技术与应用》２０１０年第２９卷第２期基于前缀计算的序列比对研究张瑜，王继东（西北师范大学数学与信息科学学院，甘肃兰州７３００７０）摘要：为了提高Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ算法处理速度，同时不改变原算法的准确性，本文利用前缀计算方法修改Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ算法，并进行ＯｐｅｎＭＰ并行化。
在多核机上测试表明，前缀计算的共享并行化使得该局部比对算法的速度得到很大的提高。
关键词：并行编程；ｓｍｉｔｈｗａｔｅｒｍａｎ算法；前缀计算中图分类号：ＴＰ３１１文献标识码：Ａ文章编号：１００３７２４１（２０１０）０２—００３５０４ＲｅｓｅａｒｃｈｏｎＡｌｉｇｎｍｅｎｔＢａｓｅｄｏｎＰｒｅｆｉｘＣｏｍｐｕｔａｔｉｏｎＺＨＡＮＧＹｕ，ＷＡＮＧＪｉ－ｄｏｎｇ（ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ，ＮｏｒｔｈｗｅｓｔＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｌａｎｚｈｏｕ７３００７０Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：ＩｎｏｒｄｅｒｔｏｓｐｅｅｄｕｐＳｍｉｔｈ—Ｗａｔｅｒｍａｎａｌｇｏｒｉｔｈｍｓａｎｄｋｅｅｐｉｔｓｈｉｇｈｐｒｅｃｉｓｉｏｎ，ｐｒｅｆｉｘｃｏｍｐｕｔａｔｉｏｎｉｓｕｓｅｄｔｏｃｈａｎｇｅＳｍｉｔｈ—Ｗａｔｅｒｍａｎａｌｇｏｒｉｔｈｍ，ｔｈｅｎｔｈｉｓａｌｇｏｒｉｔｈｍｉｓｐａｒａｌｌｅｌｉｚｅｄｕｓｉｎｇＯｐｅｎＭＲＴｈｅｔｅｓｔｏｎｍｕｌｔｉ—ｃｏｒｅｓｓｈｏｗｓｔｈａｔｔｈｅｐｅｒｆｏｒ—ｍａｎｃｅｉｓｉｍｐｒｏｖｅｄｍｕｃｈｍｏｒｅｔｈａｎｔｈｅｏｒｉｇｉｎａｌｓｅｑｕｅｎｔｉａｌｐｒｏｇｒａｍ．Ｋｅｙｗｏｒｄｓ：ｐａｒａｌｌｅｌｐｒｏｇｒａｍｍｉｎｇ；Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎａｌｇｏｒｉｔｈｍ；ｐｒｅｆｉｘｃｏｍｐｕｔａｔｉｏｎ１引言序列相似性是生物信息学处理中最基本的问题。
如何获得结果更准确，时间、空间效率更高的序列相似性比较算法是生物信息学研究中的一个重要课题。
在寻找基因序列最佳相似比对的算法中，Ｆｅｅｌｄｅｒｓ等人…１介绍动态规划方法进行精确查找两个序列的最优局部比对，但因其代价太大，对超长生物序列直接应用这种技术是不可行的。
ＳｔｊｅｐａｎＲａｊｋｏ［２】利用可分负载原理将双序列比对并行化，并对罚分函数进行改进，将时间和空间复杂度分别降低到Ｄ（ｍｎ／ｐ）和ｏ（ｍ＋ｎ／ｐ）。
Ｋａｔｏｈ［３】对算法的优化包括对算法时间和空间复杂度的优化，还考虑结果的精确度，提出了基于ＦＦＴ分析序列的算法，该算法能对同源区快速识别，它的ＣＰＵ时间降低到ＮｌｏｇＮ。
同时它还提出了一个简单的分数系统来降低时间复杂度和提高精确度。
但Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ［４】算法可以产生最优结果，但是运算速度慢。
于是人们提出了很多并行化Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ算法的方法。
ＳｒｉｎｉｖａｓＡｌｕｒｕ［５１中运用计算前缀的方法，使用（ｎ／ｌｏｇｎ）处理器，设计了一个时间复杂度为（ｍｌｏｇｎ）的双序列比对并行算法。
收稿日期：２００９—０９—０９并行算法的引入，有效的降低了双序列比对的计算时间，更符合超长生物序列的特点。
ＯｐｅｎＭＰ［６］是一个为在共享存储的多处理机上编写并行程序而设计的应用编程接口，由一个小型的编译器命令集组成，包括一套编译制导语句和一个用来支持它的函数库。
ＯｐｅｎＭＰ是通过与标准的Ｆｏｒｔｒａｎ和Ｃ＼Ｃ＋＋结合进行工作的…８｜，对于同步共享变量、合理分配负载等任务，都提供了有效的支持，具有简单通用、开发快速的特点。
ＯｐｅｎＭＰ是可移植多线程应用程序开发的行业标准，在细粒度循环级别与粗粒度函数级别线程技术上具有很高的效率。
对于将串行应用程序转换成并行应用程序，ＯｐｅｎＭＰ指令是一种容易使用且作用强大的工具，它具有使应用程序因为在对称多处理器或多核系统上并行执行而获得大幅性能提升的潜力。
ＯｐｅｎＭＰ自动将循环线程化，提高多处理器系统上的应用程序性能。
用户不必处理迭代划分、数据共享、线程调度及同步等低级别的细节。
本文利用ＯｐｅｎＭＰ实现基于前缀计算的Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ算法并行化，修改后的算法在不改变原算法精确性的基础上，并获得了很好的加速比。
《自动化技术与应用》２０１０年第２９卷第２期计算机应用旦Ｑ受巳竺！皇！垒望巳！！旦璺！！Ｑ翼曼２Ｓｍ．１ｈ—Ｗａｔｅｒｍａｎ串行算法２．１描述序列比对的基本术语∑代表字母表，在ＤＮＡ中∑＝｛Ａ，Ｃ，Ｇ，Ｔ｝；“”代表空位，用于表示由于突变引起的插入与删除。
分数函数ｆ：∑ｕ｛一＇｝ｘＥｕ｛一，）ｊ吼描述比对中任何一个位置中没有空位时的分数。
这种分数函数阵对替换，通用的记分方法是采用替换矩阵，即给不同字符之间发生替换提供一个分值。
这种记分方式可以描述为矩阵的形式，矩阵上的每一格都表示它对应的行和列所表示的字符之间发生替换时的得分。
在生物学中通常使用的替换矩阵有ＰＡＭ和ＢＬＯＳＵＭ等矩阵。
仿射罚分方式：生物体在进化过程中会不断地产生突变，空位代表了突变引起的插入和删除，插入和删除比较通行的记分方法是采用空位罚分，即给予每个空位一定的罚分值，当出现空位时，则使得总分值减少。
仿射罚分方式就是其中的一种空位罚分方式，比如连续的ｋ个空位的罚分就是ｈ＋ｇｋ。
起始的空位罚分为ｈ＋ｇ，ｇ为延伸空位罚分。
２．２Ｓｍｉｔｈ．Ｗａｔｅｒｍａｎ算法Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ算法被认为是生物信息学中最基础的算法，它由两部分组成：（１）根据动态规划算法，计算两个序列的最佳比对分数，并记录相应的分数；（２）根据分数矩阵的值，通过回溯的方法识别出最佳的比对序列。
由于第一部分的计算比较重要，因此本文只考虑计算最优值。
假定两个比对序列的长度为ｍ、ｎ，并使用仿射罚分策略，使用的动态规划算法方程如下：ｆ啡－ｌ’，一１］］Ｔｌ¨】＿ｆ（ａｌ，ｂｊ）＋ｍａｘ｛Ｔ２［ｆ一１，Ｊ一１］｝【Ｔ３［ｆ＿１＇Ｊ—ｌ“Ｔ１【ｉ，ｊ－１］一（ｇ＋＾）１Ｔ２［ｆ，Ｊ】＿ｍａｘ｛Ｔ２［ｉ，』－１］一ｇ｝ｌＴ３【ｉ，Ｊ一１］一（ｇ＋＾）１Ｔｌ卜ｉ１，Ｊ卜（ｇ＋＾）１Ｔ３［ｆ，州＝ｉｎａｘ｛Ｔ２【ｆ＿ｉ１，ｊ］－（ｇ＋＾）｝【Ｔ３卜ｌ，Ｊ卜ｇＪ该算法使用三个表Ｔ，，Ｔ，，Ｔ，，它们的大小为（ｍ＋１）×０＋１）。
表中的每一个数组［ｉ，ｊ】代表相应的序列吼％…，ｑ与ｂｌ，ｂ２，…ｂｊ的最优比对值。
但是在如下的条件中：在Ｔｌ中ａｉ必须和ｂｉ匹配；在Ｔ，中“一”和ｂｊ匹配；在Ｔ，中ａｊ和“”匹配。
表Ｔ，，Ｔ，，Ｌ使用上述的方程计算。
３Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ算法ＯｐｅｎＭＰ并彳亍化本文在使用前缀方法的基础上对Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ算法进行ＯｐｅｎＭＰ并行化。
下面首先介绍使用前缀方法，让每个线程可以并行处理一列，实现多线程并行化。
然后介绍在此基础上划分成块进行０ｐｅｎＭＰ并行化过程。
本文中Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ算法是用Ｃ语言实现的，因此下文都是以ＯｐｅｎＭＰ＋Ｃ方式介绍并行化过程的。
３．１前缀并行计算方法基于动态规划算法实现的ＳｍｉｔｈＷａｔｅｒｍａｎ算法中，各元素之间存在着严重的依赖关系。
本文借鉴ＳｒｉｎｉｖａｓＡｌｕｒｕ等人提出的前缀计算并行化生物序列的方法，实现ＳＭＰ机上的ＯｐｅｎＭＰ并行化。
图１线程任务分配下面使用一个简单的例子说明如何使用并行前缀的方法按照列流水的方式计算表中的各个元素值。
假定在计算Ｔ，，Ｔ，，Ｔ；的第ｉ行时，它们的第ｉｌ行值已经计算完毕。
那么，表Ｔ，，Ｔ，可以直接计算，因为它们仅依赖于第ｉ１行。
通过计算它们后，表Ｔ，值的计算还需要知道本行中它前一个元素的值，即Ｔ，［ｉ一１］的值。
Ｔ，值的计算就使用并行前缀来计算。
具体的方法如下：定义：山】＿ｍａｘ㈨Ｔｔ［ｉ，ｊ川－１］Ｊ＿【－（ｇ刚＋ｈ））｝那么，咖】＿ｍ。
删【』２【ｉ，，让，一ｃ，，＝正卜，，一・，＋，ｓ＝ｍａｘ｛乏苫？ｚ；＋。
，计算机应用ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓ《自动化技术与应用》２０１０年第２９卷第２期其中对于所有的ｊ都是知道ｗ［ｊ］＋ｊｇ的，ｘ［ｊ］可以通过前一个ｘ［ｊ—ｌ】来计算，然后Ｔ２可以通过Ｔ２【ｔｉ，ｊ】：，Ｍ—Ｊｇ计算。
这样就可以按照列流水的方式进行并行化计算。
假如有ｎｔｈｒｅａｄ个线程，那么就可以让它们并行处理多列。
第ｉ个线程处理完一列可以继续处理第ｎｔｈｒｅａｄ＋ｉ列，具体的方法如图ｌ所示。
３．２分块并行计算上节中描述了基于前缀的并行化处理ＳｍｉｔｈＷａｔｅｒｍａｎ算法，但是直接按照这种方法计算序列中的每一个元素，会由于线程间通信次数太多，造成通信开销太大。
因此本文考虑将其中的元素计算按照块的方式进行并行化处理。
将整个矩阵分成Ｒｕｍ｝ｎｕｍ个块（其中ｎｕｍ为线程数目），然后继续按照前缀计算的方式计算，每个线程处理对应的列中的块。
３．３区分变量属性由于ＳｍｉｔｈＷａｔｅｒｍａｎ算法中并行化操作主要针对的是ｆＯｒ循环，因此区分好循环体中的变量属性至关重要。
并行区域里有若干个属性分类，如ｓｈａｒｅｄ，ｐｒｉｖａｔｅ，ｌａｓｔｐｒｉｖａｔｅ，ｆｉｒｓｔｐｒｉｖａｔｅ，ｄｅｆａｕｌｔ等。
所有处理器可以直接存取共享变量，每个处理器对私有变量进行各自的拷贝。
通过分析，算法循环结构中的共享变量和私有变量，使用编译制导语句表示如下：＃ｐｒａｇｍａｐａｒａＨｅｌｆｏｒｐｒｉｖａｔｅ（１ｉｎｅ）ｓｈａｒｅｄ（Ｔ，，Ｔ，，Ｔ，，ｗ，Ｘ）其中，ｐｒｉｖａｔｅ指定的为私有变量，即每个线程都私有，我们按照列进行并行化，其中的循环计数器为ｌｉｎｅ，ｌｉｎｅ代表列值。
ｓｈａｒｅｄ指定的为共享变量，所有线程共享这些变量。
通常未指定时，循环计数器值默认为私有变量，循环内的其它变量默认为共享变量，因此ｐｒｉｖａｔｅ也可以省略。
３．４ｎｏｗａｉｔ从旬为了最小化同步造成的开销，ＯｐｅｎＭＰ制导语句支持可选项ｎｏｗａｉｔ从句。
使用ｎｏｗａｉｔ从句时，每个线程在每个特殊的并行结构的结尾不用等待其他的线程。
Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ算法循环体中，按照列进行计算，仅在开始时需要等待前一列的Ｘ值，后面并行计算，线程之间不需要同步。
为了提高计算速度，每一个线程在计算完本列之后，开始计算第ｎｔｈｒｅａｄ＋１列。
ｎｏｗａｉｔ从句的编译制导语句如下：＃ｐｒａｇｍａｐａｒａＨｅｌｆｏｒｐｒｉｖａｔｅ（１ｉｎｅ）ｓｈａｒｅｄ（Ｔ，，Ｔ，，Ｔ，，ｗ，ｘ）ｎｏｗａｉｔ３．５任务调度ＳＣｈｅｄｕｌｅ子句指定如何调度ｆｏｒ循环迭代。
０ｐｅｎＭＰ的三种任务调度策略，静态调度、动态调度、引导调度。
动态调度是只要线程完成任务，需要任务就可以获得下一个迭代块，对于负载均衡的任务，动态调度系统开销比较大。
引导调度是一种混合策略，每个线程在第一次获得一个较大的块，以后运行中分配逐渐缩减块的大小，直到缩减至ｃｈｕｎｋＳｉｚｅ制定的限制值，块的大小按需要动态计算，这与块大小逐渐减少的动态调度类似。
