基于GPU的大规模基因片段并行匹配的方法

发布时间：2018-02-26 05:15

  本文关键词： 后缀数组 后缀树 GPU 基因片段匹配 并行　出处：《四川大学学报(自然科学版)》2017年02期 　论文类型：期刊论文

【摘要】：后缀树和后缀数组广泛用于生物信息学领域中,特别是通过启发式算法在对DNA基因片段进行匹配的阶段.本文提出了在GPU的平台下,利用多核和超多核体系构成的后缀树以及后缀数组并行匹配大规模基因片段,从而加速基因搜索匹配过程.相对于后缀树,后缀数组二分搜素算法具有内存占用少,缓存使用率高等优点.在GPU的性能评估中,后缀数组执行效率明显超过后缀树,后缀数组占用的空间仅为后缀树的20%~30%.相对于CPU的串行实现,后缀树组达到了约99倍的加速比.实验结果表明在基因片段匹配的过程中,基于GPU的后缀数组二分搜索是一种高效且实用的方法.
[Abstract]:Suffix trees and suffix arrays are widely used in the field of bioinformatics, especially in the stage of matching DNA gene fragments through heuristic algorithms. The suffix tree and the suffix array are used to match large scale gene fragments in parallel, which accelerates the gene search matching process. Compared with the suffix tree, the suffix array binary search algorithm has less memory. In the performance evaluation of GPU, the execution efficiency of suffix array is obviously higher than that of suffix tree, and the space occupied by suffix array is only 20 / 30 of suffix tree. The result of experiment shows that the binary search of suffix array based on GPU is an efficient and practical method in the process of gene segment matching.
【作者单位】： 四川大学计算机学院;四川大学锦江学院计算机学院;
【基金】：四川省科技厅支撑项目(2012GZ0091,2013GZX0138) 四川大学青年教师科研启动基金(2015SCU11050)
【分类号】：TP332

【相似文献】

相关期刊论文 前10条

1 黄影;;一种有效的后缀树建立方法[J];电子科技;2013年10期

2 赵杰文;原娇杰;;数据挖掘中后缀树算法的应用研究[J];焦作大学学报;2007年03期

3 黄影;;一种有效的后缀树建立方法[J];中国电子教育;2013年03期

4 乔百友,葛健,王国仁,韩东红;并行后缀树的构造及查询算法[J];东北大学学报;2004年03期

5 彭静;翟英;冯爽;;后缀树算法在舆情聚类中的应用[J];河北科技大学学报;2012年01期

6 葛健;王国仁;于戈;;后缀树的并行构造算法[J];计算机科学;2004年05期

7 曲文龙;杨炳儒;张克君;;基于广义后缀树的事件序列频繁情节挖掘算法[J];北京科技大学学报;2006年05期

8 王秉政;苏晓珂;张素智;;一种基于后缀树的简洁关联规则挖掘有效剪枝方法[J];郑州轻工业学院学报(自然科学版);2011年03期

9 董云耀;李笑;;基于后缀树的知识点间关联规则挖掘算法[J];杭州电子科技大学学报;2006年01期

10 师鸣若;姜中华;赵明茹;;基于概率后缀树的宏观网络报警事件序列分析[J];电脑开发与应用;2009年01期

相关会议论文 前1条

1 务孟庆;高军;王腾蛟;杨冬青;;WD-STC：一种基于网络词典的WEB新闻文档后缀树聚类算法[A];全国网络与信息安全技术研讨会论文集（上册）[C];2007年

相关硕士学位论文 前10条

1 李双江;基于压缩后缀数组的空间高效短读比对算法[D];西安电子科技大学;2014年

2 陈智达;支持字符串局部比对的内存及外存优化方法[D];东北大学;2013年

3 王哲;面向基因组的高效FM-index构造算法[D];西安电子科技大学;2015年

4 郭海涛;用加强的后缀数组查找MUM[D];西安电子科技大学;2007年

5 王学;基因组中最大唯一匹配的查找算法研究[D];西安电子科技大学;2009年

6 王坚;基于后缀数组的滑动窗口匹配压缩改进算法研究[D];华中科技大学;2012年

7 陈月妥;一种新型后缀数组构造外存算法的性能优化技术[D];中山大学;2014年

8 荣元媛;改进后缀树的中文检索结果聚类系统[D];北京林业大学;2013年

9 董丽霞;基因组比对中若干改进算法研究[D];西安电子科技大学;2009年

10 唐德昌;基于串核的蛋白质分类算法的研究与实现[D];哈尔滨工业大学;2008年

，

本文编号：1536650