基于SSE2的Smith-Waterman算法

Smith-Waterman动态规划算法是生物信息学使用最广泛的序列匹配算法,由于存在严重的数据依赖关系,该算法的细粒度数据并行性开发受到了很大限制。文章从简化数据依赖关系出发,采用前驱计算思想,提出了基于X86处理器多媒体指令集SSE2的Smith-Waterman细粒度并行算法SWSSE2,在相似性显著的情况下比普通的SW算法性能提高5倍,且与测试集无关。一般相似性不显著的情形下,同目前最好的动态规划细粒度并行算法SWMMX相比可以获得1.5倍的加速比。

Smith-Waterman算法OpenMP并行化

基因比对可以实现对海量生物信息的分析和处理,其中Smith-Waterman算法实现的比对信息精确度较高,但是处理速度慢。本文利用共享存储编程的工业标准OpenMP对Smith-Waterman算法进行了并行化实现。在一个拥有四个双核CPU的SMP节点上的测试表明,共享并行化使得该局部比对算法的速度提高了40%。

Smith-Waterman算法在脉动阵列上的实现及分析

Smith Waterman算法是一种经典的序列比对算法 ,在双序列比对的情况下具有比较好的性能 ,但是在大规模的序列比对时 ,其性能并不能令人满意 .脉动式阵列和Smith Waterman算法有比较好的吻合性 .该文通过在龙芯 1号处理器上附加一个脉动式阵列的协处理器 ,构建了硬件模型 .通过模拟器的验证 ,附加了协处理器的龙芯 1号的性能与没有附加协处理器时的性能之比接近于线性 .该文最后根据硬件模型和模拟器的性能数据 。

基于FPGA的带回溯的Smith-Waterman算法加速器的设计与实现

针对传统的Smith-Waterman硬件算法加速器未保存回溯路径而无法回溯的问题,通过将计算路径存入外存,在FPGA平台上基于脉动阵列实现了带回溯的Smith-Waterman算法加速器,详细阐述了算法加速器回溯设计中的关键技术以及算法加速器的系统结构。实验表明,与传统的解决方案相比,带回溯的算法加速器最高可获得161倍加速比,能够有效提高带回溯的Smith-Waterman算法执行效率。

Comparative Study of the Parallelization of the Smith-Waterman Algorithm on OpenMP and Cuda C

In this paper, we present parallel programming approaches to calculate the values of the cells in matrix’s scoring used in the Smith-Waterman’s algorithm for sequence alignment. This algorithm, well known in bioinformatics for its applications, is unfortunately time-consuming on a serial computer. We use formulation based on anti-diagonals structure of data. This representation focuses on parallelizable parts of the algorithm without changing the initial formulation of the algorithm. Approaching data in that way give us a formulation more flexible. To examine this approach, we encode it in OpenMP and Cuda C. The performance obtained shows the interest of our paper.

基于OpenCL的Smith-Waterman算法硬件加速研究

生物序列分析由于其数据的海量性、分析算法的多样性和复杂性,因此其对运算平台以及软件工具有着很高的要求。在生物序列分析领域中,文中针对序列比对所采用的经典算法即Smith-Waterman算法在FPGA加速平台下的性能进行研究,利用开放运算语言OpenCL进行异构平台的硬件加速设计。通过利用Smith-Waterman算法的波前特性,在硬件设计层面上实现算法在运算过程中的高度并行化,弥补了在CPU单一平台下只能进行串行运算的不足。通过对大量不同样本序列的测试表明,利用算法的波前特性,针对短序列比对,FPGA的运算速度最高能达到CPU的4倍。

基于Smith-Waterman算法的并行分而治之生物序列比对算法

生物序列比对是生物信息学中最常见的问题之一,基于动态规划思想的Smith-Waterman算法是序列比对中最基本的算法.然而现有的并行Smith—Waterman算法都需要庞大的内存,且无法处理大规模的数据串,随着生物数据的急剧增长,这些并行算法对内存空间的需求已成为需要迫切解决的问题.由此提出一种并行生物序列比对算法,PSW—DC算法,该算法采用分而治之的方法把query序列划分为若干片段,并分配给相应的各个处理器,而后并行地按Smith—Waterman算法与目标(subiect)序列进行比对,再通过按一定规则的扩展过程求取序列的优化匹配.与其他并行算法相比,该算法有效地降低了内存空间的需求,并实现了对大规模数据串的并行处理.为实现该算法,给出了一种称作C&E的拓展规则及实现方法.且该方法已经在实际系统中得到实现.

Smith-Waterman算法优化改进与Spark并行化研究

Smith-Waterman算法是1种精确度最高、广泛应用于文本搜索的生物学序列比对算法。在对Smith-Waterman算法深入研究的基础上,从减少计算任务量和降低计算复杂度两个方面对算法进行优化改进,将优化改进算法基于Spark平台进行算法并行化设计,并通过准确性测试、算法运行速度测试、算法速度比较测试、算法可扩展性测试等实验分析优化改进算法和并行化算法的性能。实验结果表明:优化改进和并行化后的算法在保证准确性的前提下,极大地提高了算法运行速度和可扩展性。

GPU加速的生物序列比对

为了精确高效地进行生物序列比对,提出一种GPU加速的Smith-Waterman算法.该算法使用菱形数据布局以更充分地利用GPU的并行处理能力;使用查询串分批处理技术来支持上百兆规模的序列比对;同时引入树形算法,以优化最大匹配值的计算.将该算法在一块NVIDIA GeForce GTX285显卡上实现,并使用多组不同规模的生物序列进行了比对实验.实验结果表明,与CPU上的串行算法相比,采用文中算法最高可获得120倍以上的性能提升.

一种面向生物信息学的可重构加速卡的设计与实现

人类基因组测序工作完成后,对基因数据的处理和分析能力提出了更高的要求.生物信息学的基本研究方法之一就是计算,其算法的特点是数据量较大、算法比较简单、运算类型单一、重复性较强、潜在的并行度较高.用现有的大规模并行机或超级服务器等通用系统解决这些问题,既浪费系统的资源,使用维护也比较复杂,有些问题甚至无法在限定的时间内完成.提出了一种比较通用的算法可重构硬件加速卡的体系结构,以全局SmithWaterman算法为例,阐述了从算法到硬件实现的映射过程,并指出了将其他类型算法映射到该加速卡上的可行性.

面向OpenCL架构的大规模生物序列比对

为提高生物序列比对算法的性能和效率,提出一种异构处理平台下可移植的大规模生物序列比对算法及其优化方法.通过改变原有Smith-Waterman算法的计算流程和数据依赖关系,增加序列比对的并行性;通过改变存储器布局后使用向量数据类型,提高全局存储器的带宽利用率;通过增加偏移量改变存储器模块的映射方式,避免模块访问冲突,提高局部存储器的使用效率.实验结果表明,优化后的生物序列比对性能提升了近100倍.

基于SVM和序列联配的攻击特征提取方法

针对序列联配应用于攻击特征提取时的碎片和噪声干扰问题,采用SVM分类器将多攻击样本转换成单一攻击样本,以减少联配过程中的噪声序列;在两序列联配Smith-Waterman算法的基础上,改变空位罚分方式,引入连续匹配字符奖励,提出一种改进的Smith-Waterman(ISW)算法。结合SVM分类器与ISW算法构建攻击特征提取模型。研究结果表明:该模型的联配结果能准确地表达攻击特征,降低检测系统的误报率。

基于动态时间规划的基因芯片数据识别

研究了动态时间规划 (DP)在基因芯片数据识别中的应用 ,提出了基因芯片数据的全局最大自相似度的定义以及基于最大自相似度和高维局部片段校对的基因芯片数据自动识别方法。讨论了基于最大相似度建立模板的方法与基于最大相似度的基因沿校对路径平均的建立模板方法对基因识别和分类的影响。对肿瘤基因的识别实验结果表明 :基于最大相似度的DP算法 (DP MS)能够达到 10 0 %的识别率 ,本方法可以应用于基因芯片数据的识别、分类和基因疾病推断。

用动态扣分策略消除序列局部联配中的马赛克问题

1引言 生物信息学中,对各种生物大分子序列进行分析是一件非常基本的工作,Paul A.Rota[1]通过测定SARS(又名非典型性肺炎)病毒的基因组序列,找到了含有制造蛋白质指令的部分基因,其中包括公认的制造四种蛋白质的基因,证实了非典病毒是一种全新的冠状病毒,这一成果将有助于加快诊断、治疗和预防非典的步伐.

关于DNA序列比对算法的简述

按照序列的数量,先对双序列比对中Smith-Waterman算法、FASTA算法、BLAST算法、MUMmer算法和遗传算法等进行了详细分析和比较,然后对多序列比对中的CLUSTAL算法和星比对算法也进行了比较全面的总结,并指出了当前的研究热点。

基于GPU并行的生物序列局部比对算法

对Smith-Waterman算法的计算公式进行了改进以适应GPU并行的特点,并提出新的基于BLOCK分块的并行前缀扫描法;通过UP-DOWN步骤、BLOCK间调整、Eij微调等步骤在O(logn)时间内计算出行中每一个元素的前缀最大值;最后将回溯过程置于GPU端,避免了CPU与GPU间内存的拷贝.与传统的Smith-Waterman算法相比,该算法在低端的GPU平台性能提升90倍;与同样基于GPU的SWAT算法相比,性能也有较大的提升.

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

为了提高Smith-Waterman算法处理速度,同时不改变原算法的准确性,本文利用前缀计算方法修改Smith-Waterman算法,并进行OpenMP并行化。在多核机上测试表明,前缀计算的共享并行化使得该局部比对算法的速度得到很大的提高。

基于GPGPU的生物序列快速比对

在CPU-GPU异构平台下,提出一种高效的生物序列比对方案。该方案利用GPU的并行处理能力,通过对读延迟、写延迟、重组函数及数据传输进行优化,在OpenCL框架下重构Smith-Waterman算法,加快生物序列比对速度。实验结果证明,与CPU上传统的串行算法相比,该算法最高可获得约100倍的性能提升。

基于K-中心点聚类算法的论坛信息识别技术研究

提出了一种从非确定结构的论坛页面自动获取信息区域的方法。该方法在对K-中心点聚类算法的研究基础上克服了算法中固定簇数的缺陷,并在算法的簇中心距离计算中引入Smith-Waterman改进算法,提高了算法聚类的精确度。通过对大量论坛网页进行信息识别的实验显示,该方法切实可行并且具有较高的准确性。

生物信息学双序列比对算法加速器设计与实现

双序列比对算法是进行生物信息学研究的基础算法。在FPGA上实现大规模脉动式阵列对双序列比对算法进行加速能够大幅度提高比对的效率。然而现有的设计方法在比对序列长度较短的情况下,处理单元利用率很低;在序列的长度较大时,需要占用大量的片内存储资源。通过将两条序列同时送入阵列进行比对减少比对时间。将比对数据送入外部存储器,优化比对过程中的数据存储调度,有效降低了对片内存储器的需求。以Smith-Waterman算法为例进行了实现验证,结果表明本设计在性能上优于传统设计。与Pentium42.60GHz通用微处理器计算机相比,使用加速器对长度为65536的序列进行比对可获得1555倍的加速比。