Needle-Wunsch论文--基于软件流水线的Needleman-Wunsch算法并行化设计

我们用表示得分矩阵指得分矩阵中第行第列的元素表示字符和字符的比较得分。

，的值由公式计算得到，得分矩阵各元素的值根据公式计算得到，然后回溯寻找最优比对序列。

且，均不为空格，≠且，均不为空格，有个是空格，三标准是种共享存储并行编程模型。

共享式存储的并行化具有编程简单灵活的特点，开发周期较短，并行效率较高。

年计算机软硬件厂商联合定义了共享内存编程应用接口的工业标准协议，克服了长期以来并行解决方案的可移植性和扩展性差的缺点。

由套编译制导语句函数库以及环境变量组成。

它通过与标准的语言结合来工作，主要是在循环级上的并行，指令以单程序多数据结构任务共享结构同步结构以及提供对数据共享或私有的支持扩展了原有程序的顺序结构模型。

在中，编译制导指令在每行以开头，编译制导指令定义个并行域，就会生成另外的些线程来并行执行这些代码。

制导指令可以实现循环中各迭代的并行执行。

具体用法的示例代码如下。

语句标明每个线程对变量都有自己的份私有拷贝。

，四算法的并行化软件流水线技术软件流水线是种传统的优化技术，它需要同时运行不同迭代的不同部分，通过交叠多个迭代的不同部分来加速程序循环代码的运行。

软件流水线技术是解决数据相关的种很好的方法，它的基本思想是通过调整循环体各迭代中操作的执行顺序但是对动态部分没有优化功能。

引导调度是种混合策略，每个线程在第次获得个较大的块，以后运行中分配逐渐缩减块的大小，直到缩减到限制值，块的大小按需要动态计算，这与块大小逐渐减少的动态调度类似。

运行时调度根据环境变量的值决定，本文使用静态调度，主要代码如下所示。

五性能分析采用软件流水线优化以及并行化后，算法的性能得到了很大提高。

如果比对的序列较短，程序的性能改善不太明显，这是因为编写的程序在运行时采用分叉合并方式，并行处理会带来相应的线程创建销毁开销，但是总体性能还是得到了提高。

六结论本文研究了生物信息学中的全局序列比对算法，并采用软件流水线技术和编程对其进行了并行化设计。

并行处理后的算法适合处理较长序列的比对，对于短序列，由于相应线程创建销毁开销等并行性开销，并行处理的速度会比串行处理慢，总体来说，采用软件流水技术使算法的总体性能得到了很大提高。

参考文献基于软件流水线的算法并行化设计摘要序列比对是分析海量生物信息的重要算法之，在现代生物信息中的搜索相似序列预测未知序列的序列信息寻找序列中的特定位点和预测蛋白质结构等研究领域起着重要的作用。

算法是最早的双序列全局比对算法，其以准确性得到了广泛应用，但是它的时间复杂度较高，处理速度慢，本文采用软件流水线技术对其进行并行化优化，利用共享存储编程的工业化标准对其进行并行化实现，性能能够得到很大提高。

关键字生物信息序列比对软件流水线引言序列比对是根据特定的计分规则，两个或多个符号序列按位置比较后排列，尽可能反映序列间的相似性，这过程称为序列比对，也叫做对位排列联配对齐等，是生物信息学形成早期的主要研究内容。

序列比对可以搜索相似的序列，预测个未知序列的序列信息。

还可以进行基因组测序寻找序列中的特定位点和预测蛋白质结构等，对发现生物序列中的功能结构和进化的信息具有非常重要的意义。

序列比对通常提供了个有力的途径来判断两个序列之间是否具有足够的相似性，从这种计算出的相似性进步来推断两者可能具有共同的进化祖先，即同源性。

所谓序列相似性只是经过定的算法所得到的可以量化的结果，而同源性则是个进化意义上的概念，即两个序列是否同源需要有进化事实的验证。

换句话说，两个蛋白质的序列比对可以反映个相同的进化祖先，或者代表相同的结构，但在进化上却未必有必然联系。

序列比对分为全局比对与局部比对。

全局比对是待研究序列的全部符号参加比较，最后也是序列的全部符号进行排列与计分，比对的结果中各序列长度相同，如算法。

局部比对是序列的全部符号参加比较，最后只将各序列中得分高的片段中的符号及进行排列与计分，即只排列局部的序列片段，如算法。

二算法动态规划算法动态规划是组合子问题的解而解决整个问题的，常常应用于最优化问题，即要做出组选择以达到个最优解。

序列比对中的动态规划的思想是如果条路径终止于最优路径上的点，那么这条路径本身就是起点到这个中间点的最优路径，也就是说，任何个终止于最优路径上的点的子路径必然就是终止于这点的最优路径本身。

这样，最优路径就可以通过把各个最优的子路径连接而成。

算法与在年提出基于动态规划法的全局比对算法，也是最早的双序列比对算法，以其准确性得到广泛应用，其时间复杂度和空间复杂度均为。

该算法解决序列比对问题的基本思想是使用迭代方法计算出两个序列的相似分值，存在个得分矩阵中，然后根据这个得分矩阵，回溯寻找最优的比对序列。

我们用表示得分矩阵指得分矩阵中第行第列的元素表示字符和字符的比较得分。

，的值由公式计算得到，得分矩阵各元素的值根据公式计算得到，然后回溯寻找最优比对序列。

且，均不为空格，≠且，均不为空格，有个是空格，三标准是种共享存储并行编程模型。

共享式存储的并行化具有编程简单灵活的特点，开发周期较短，并行效率较高。

年计算机软硬件厂商联合定义了共享内存编程应用接口的工业标准协议