基于SSE2的Smith-Waterman算法 被引量：2

1

作者 戴正华 张庆丹 +2 位作者 徐琳 谭光明 冯圣中 《计算机工程与应用》 CSCD 北大核心 2006年第11期85-87,共3页

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

关键词 smith-waterman 算法 细粒度并行算法 SIMD SSE2

在线阅读 下载PDF 职称材料

Smith-Waterman算法OpenMP并行化 被引量：3

2

作者 张瑜 王继东 《自动化技术与应用》 2010年第1期37-40,共4页

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

关键词 OPENMP smith-waterman算法 并行编程

在线阅读 下载PDF 职称材料

Smith-Waterman算法在脉动阵列上的实现及分析 被引量：6

3

作者 汪冬 唐志敏 《计算机学报》 EI CSCD 北大核心 2004年第1期12-20,共9页

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

关键词 smith-waterman算法 脉动阵列 序列比对算法 计算机 生物信息学

在线阅读 下载PDF 职称材料

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

4

作者 邹丹 窦勇 +1 位作者 夏飞 倪时策 《国防科技大学学报》 EI CAS CSCD 北大核心 2009年第5期29-32,共4页

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

关键词 FPGA smith-waterman算法 脉动阵列 回溯

在线阅读 下载PDF 职称材料

Smith-Waterman算法优化改进与Spark并行化研究 被引量：4

5

作者 李雷孝 刘燕凤 高静 《内蒙古农业大学学报（自然科学版）》 CAS 北大核心 2019年第5期76-85,共10页

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

关键词 基因序列比对 smith-waterman算法 优化改进 Spark并行化

原文传递

基于图数据结构的生产追溯信息处理系统

6

作者 徐志达 鲍敏 《自动化与仪表》 2025年第8期128-133,共6页

为了解决目前离散型工厂MES系统深层数据查询时间长以及生产环节中返工返修的信息追溯问题,通过对生产过程数据的归一化和重组等操作,针对实际产线的工序流程进行了图数据建模,实现了关系型数据和图数据的映射关系,并通过Smith-Waterma... 为了解决目前离散型工厂MES系统深层数据查询时间长以及生产环节中返工返修的信息追溯问题,通过对生产过程数据的归一化和重组等操作,针对实际产线的工序流程进行了图数据建模,实现了关系型数据和图数据的映射关系,并通过Smith-Waterman序列比对算法对返工返修产线进行归因与匹配,得到相似产线工序的最大公共子集,建立了基于图数据库存储的信息处理系统。结果表明,利用在图数据库中已建立的工序数据,重复序列检测能够有效地识别工序中的返工返修问题。 展开更多

关键词 图数据 实体建模 过程追溯 smith-waterman算法

在线阅读 下载PDF 职称材料

沙戈荒风电场经柔性低频送出线路保护方案

7

作者 刘至圣 徐嘉豪 +2 位作者 张粲 杨茜茜 孙琳 《内蒙古电力技术》 2025年第3期44-53,共10页

针对沙戈荒风电系统交流线路两侧故障电流特征较为特殊,传统电流差动保护存在拒动风险的问题,提出一种基于改进Smith-Waterman(SW)算法的新型纵联保护方案,并通过硬件在环(Hardware-in-the-Loop,HIL)实验对方案进行验证。结果显示,所提... 针对沙戈荒风电系统交流线路两侧故障电流特征较为特殊,传统电流差动保护存在拒动风险的问题,提出一种基于改进Smith-Waterman(SW)算法的新型纵联保护方案,并通过硬件在环(Hardware-in-the-Loop,HIL)实验对方案进行验证。结果显示,所提方案能够准确判断区内外故障,具备较强的抗过渡电阻干扰能力,对于TA存在15%测量误差或存在25 dB高斯噪声干扰的情形仍具有较好的适应性,能够满足柔性低频输电线路保护方案要求。 展开更多

关键词 沙戈荒风电场 柔性低频输电 纵联保护 故障特征 改进smith-waterman算法

在线阅读 下载PDF 职称材料

Access原发性肝癌数据库的建立及其应用价值分析 被引量：1

8

作者 王海永 孔春丽 +2 位作者 周利芬 洪怀江 王祖飞 《数字通信世界》 2024年第12期108-110,共3页

目的:探讨Access原发性肝癌数据库的建立方法及其应用价值。方法:选择本院2020年1月至2024年4月期间确诊的原发性肝癌患者,数据来源为医院内局域网系统中的患者信息数据,通过Access数据库保存和管理患者的临床资料,建立原发性肝癌患者... 目的:探讨Access原发性肝癌数据库的建立方法及其应用价值。方法:选择本院2020年1月至2024年4月期间确诊的原发性肝癌患者,数据来源为医院内局域网系统中的患者信息数据,通过Access数据库保存和管理患者的临床资料,建立原发性肝癌患者的临床资料专科数据库。结果本院成功创建了原发性肝癌数据库并应用于临床诊疗、教学和科研等工作中。结论:建立原发性肝癌数据库并形成肝癌临床数据库管理系统,从而为临床诊疗工作和科研工作提供有效数据支撑,应用价值较高。 展开更多

关键词 原发性肝癌 ACCESS数据库 k均值聚类算法机器 smith-waterman算法 应用价值

在线阅读 下载PDF 职称材料

GPU加速的生物序列比对 被引量：15

9

作者 林江 唐敏 童若锋 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2010年第3期420-427,共8页

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

关键词 smith-waterman算法 序列比对 CUDA

在线阅读 下载PDF 职称材料

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

10

作者 张佩珩 刘新春 江先阳 《计算机研究与发展》 EI CSCD 北大核心 2005年第6期930-937,共8页

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

关键词 全局smith-waterman算法 可重构 硬件加速卡 FPGA

在线阅读 下载PDF 职称材料

面向OpenCL架构的大规模生物序列比对 被引量：2

11

作者 陈钢 韦刚 +2 位作者 李国波 裴颂文 吴百锋 《小型微型计算机系统》 CSCD 北大核心 2012年第2期392-398,共7页

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

关键词 OPENCL GPU 生物序列比对 smith-waterman算法

在线阅读 下载PDF 职称材料

基于SVM和序列联配的攻击特征提取方法 被引量：2

12

作者 刘卫国 胡勇刚 《中南大学学报（自然科学版）》 EI CAS CSCD 北大核心 2012年第11期4328-4332,共5页

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

关键词 入侵检测 攻击特征自动提取 支持向量机 序列联配 smith-waterman算法

在线阅读 下载PDF 职称材料

基于动态时间规划的基因芯片数据识别 被引量：1

13

作者 刘敬伟 程乾生 《北京大学学报（自然科学版）》 CAS CSCD 北大核心 2002年第5期611-615,共5页

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

关键词 数据识别 smith-waterman算法 动态时间规划 基因芯片 基因识别 最大相似度 模式识别

在线阅读 下载PDF 职称材料

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

14

作者 佘堃 黄均才 周明天 《计算机科学》 CSCD 北大核心 2003年第11期44-47,共4页

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

关键词 生物信息学 动态扣分策略 序列 局部联配算法 马赛克问题 smith-waterman算法 相似性 记分函数

在线阅读 下载PDF 职称材料

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

15

作者 林敏 钟一文 林娟 《福建农林大学学报（自然科学版）》 CSCD 北大核心 2015年第4期442-448,共7页

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

关键词 smith-waterman算法 并行前缀扫描 通用图形处理器 序列比对

在线阅读 下载PDF 职称材料

生物序列局部联配中的马赛克问题的一种解决方法

16

作者 黄均才 王凤碧 周明天 《生物信息学》 2006年第3期117-120,共4页

生物信息学中,Smith Waterman算法用于同源长序列的局部联配时,经常会出现马赛克问题(相似度很低的保守区域夹在两个相似度很高的区域中间)。在分析问题成因的基础上,提出利用动态加速扣分策略解决马赛克问题,即在计算得分矩阵的过程中... 生物信息学中,Smith Waterman算法用于同源长序列的局部联配时,经常会出现马赛克问题(相似度很低的保守区域夹在两个相似度很高的区域中间)。在分析问题成因的基础上,提出利用动态加速扣分策略解决马赛克问题,即在计算得分矩阵的过程中,如果存在保守区域,则加大扣分的力度,争取在离开保守区域前让得分为0,从而将保守区域切断。实验结果表明,动态加速扣分策略顺利解决了序列局部联配中的马赛克问题,并且没有显著增加算法的时间复杂度和空间复杂度。 展开更多

关键词 生物序列联配 smith waterman算法 马赛克问题 动态加速扣分策略

在线阅读 下载PDF 职称材料

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

17

作者 张瑜 王继东 《自动化技术与应用》 2010年第2期35-37,46,共4页

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

关键词 并行编程 smith-waterman算法 前缀计算

在线阅读 下载PDF 职称材料

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

18

作者 王燕 吴灏 毛天宇 《计算机工程与设计》 CSCD 北大核心 2009年第1期210-212,共3页

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

关键词 标签结构树 K-中心点聚类算法 smith-waterman算法 最小相异度 信息识别

在线阅读 下载PDF 职称材料

基于GPGPU的生物序列快速比对 被引量：5

19

作者 马海晨 韦刚 吴百峰 《计算机工程》 CAS CSCD 2012年第4期241-244,共4页

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

关键词 生物信息学 序列比对 通用图形处理器 smith-waterman算法 OpenCL框架

在线阅读 下载PDF 职称材料

生物基因序列信息处理中的数据库技术(综述)

20

作者 段敏 许龙飞 《暨南大学学报（自然科学与医学版）》 CAS CSCD 2004年第5期568-573,579,共7页

　介绍国内外生物基因序列信息处理的数据库技术,该技术包括对基因信息的获取、存储、查询、分析和注释等方面,重点介绍了国际上常用的基因序列分析算法,包括BLAST算法和SmithWaterman算法.同时介绍了生物基因序列信息处理的数据库技术... 　介绍国内外生物基因序列信息处理的数据库技术,该技术包括对基因信息的获取、存储、查询、分析和注释等方面,重点介绍了国际上常用的基因序列分析算法,包括BLAST算法和SmithWaterman算法.同时介绍了生物基因序列信息处理的数据库技术发展的趋势. 展开更多

关键词 生物基因序列信息 数据库 BLAST算法 smith Watemran算法

在线阅读 下载PDF 职称材料