本文關(guān)鍵詞： 后綴數(shù)組 后綴樹 GPU 基因片段匹配 并行　出處：《四川大學(xué)學(xué)報(自然科學(xué)版)》2017年02期 　論文類型：期刊論文

【摘要】：后綴樹和后綴數(shù)組廣泛用于生物信息學(xué)領(lǐng)域中,特別是通過啟發(fā)式算法在對DNA基因片段進行匹配的階段.本文提出了在GPU的平臺下,利用多核和超多核體系構(gòu)成的后綴樹以及后綴數(shù)組并行匹配大規(guī)�；蚱�,從而加速基因搜索匹配過程.相對于后綴樹,后綴數(shù)組二分搜素算法具有內(nèi)存占用少,緩存使用率高等優(yōu)點.在GPU的性能評估中,后綴數(shù)組執(zhí)行效率明顯超過后綴樹,后綴數(shù)組占用的空間僅為后綴樹的20%~30%.相對于CPU的串行實現(xiàn),后綴樹組達到了約99倍的加速比.實驗結(jié)果表明在基因片段匹配的過程中,基于GPU的后綴數(shù)組二分搜索是一種高效且實用的方法.
[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.
【作者單位】： 四川大學(xué)計算機學(xué)院;四川大學(xué)錦江學(xué)院計算機學(xué)院;
【基金】：四川省科技廳支撐項目(2012GZ0091,2013GZX0138) 四川大學(xué)青年教師科研啟動基金(2015SCU11050)
【分類號】：TP332

【相似文獻】

相關(guān)期刊論文 前10條

1 黃影;;一種有效的后綴樹建立方法[J];電子科技;2013年10期

2 趙杰文;原嬌杰;;數(shù)據(jù)挖掘中后綴樹算法的應(yīng)用研究[J];焦作大學(xué)學(xué)報;2007年03期

3 黃影;;一種有效的后綴樹建立方法[J];中國電子教育;2013年03期

4 喬百友,葛健,王國仁,韓東紅;并行后綴樹的構(gòu)造及查詢算法[J];東北大學(xué)學(xué)報;2004年03期

5 彭靜;翟英;馮爽;;后綴樹算法在輿情聚類中的應(yīng)用[J];河北科技大學(xué)學(xué)報;2012年01期

6 葛健;王國仁;于戈;;后綴樹的并行構(gòu)造算法[J];計算機科學(xué);2004年05期

7 曲文龍;楊炳儒;張克君;;基于廣義后綴樹的事件序列頻繁情節(jié)挖掘算法[J];北京科技大學(xué)學(xué)報;2006年05期

8 王秉政;蘇曉珂;張素智;;一種基于后綴樹的簡潔關(guān)聯(lián)規(guī)則挖掘有效剪枝方法[J];鄭州輕工業(yè)學(xué)院學(xué)報(自然科學(xué)版);2011年03期

9 董云耀;李笑;;基于后綴樹的知識點間關(guān)聯(lián)規(guī)則挖掘算法[J];杭州電子科技大學(xué)學(xué)報;2006年01期

10 師鳴若;姜中華;趙明茹;;基于概率后綴樹的宏觀網(wǎng)絡(luò)報警事件序列分析[J];電腦開發(fā)與應(yīng)用;2009年01期

相關(guān)會議論文 前1條

1 務(wù)孟慶;高軍;王騰蛟;楊冬青;;WD-STC：一種基于網(wǎng)絡(luò)詞典的WEB新聞文檔后綴樹聚類算法[A];全國網(wǎng)絡(luò)與信息安全技術(shù)研討會論文集（上冊）[C];2007年

相關(guān)碩士學(xué)位論文 前10條

1 李雙江;基于壓縮后綴數(shù)組的空間高效短讀比對算法[D];西安電子科技大學(xué);2014年

2 陳智達;支持字符串局部比對的內(nèi)存及外存優(yōu)化方法[D];東北大學(xué);2013年

3 王哲;面向基因組的高效FM-index構(gòu)造算法[D];西安電子科技大學(xué);2015年

4 郭海濤;用加強的后綴數(shù)組查找MUM[D];西安電子科技大學(xué);2007年

5 王學(xué);基因組中最大唯一匹配的查找算法研究[D];西安電子科技大學(xué);2009年

6 王堅;基于后綴數(shù)組的滑動窗口匹配壓縮改進算法研究[D];華中科技大學(xué);2012年

7 陳月妥;一種新型后綴數(shù)組構(gòu)造外存算法的性能優(yōu)化技術(shù)[D];中山大學(xué);2014年

8 榮元媛;改進后綴樹的中文檢索結(jié)果聚類系統(tǒng)[D];北京林業(yè)大學(xué);2013年

9 董麗霞;基因組比對中若干改進算法研究[D];西安電子科技大學(xué);2009年

10 唐德昌;基于串核的蛋白質(zhì)分類算法的研究與實現(xiàn)[D];哈爾濱工業(yè)大學(xué);2008年

，

本文編號：1536650