本文關(guān)鍵詞：基于外存后綴樹的top-k局部比對(duì)算法

  更多相關(guān)文章： 局部比對(duì) top-k 外存后綴樹 叉子區(qū)域

【摘要】：局部比對(duì)是一種衡量字符串間相似程度的技術(shù),它在生物信息學(xué)領(lǐng)域具有十分重要的作用.介于此,許多學(xué)者已對(duì)其進(jìn)行了深入的研究.然而,隨著數(shù)據(jù)規(guī)模的擴(kuò)大,常規(guī)的內(nèi)存算法已不適用于支持大規(guī)模文本數(shù)據(jù)的局部比對(duì).為解決上述問題,該文研究了基于外存后綴樹的top-k局部比對(duì)算法.它從根本上消除了內(nèi)存空間對(duì)算法的束縛.為了提高算法的性能,該文首先將經(jīng)典內(nèi)存算法中的過濾策略引入該文.通過適當(dāng)?shù)男薷?這些策略可以基于外存后綴樹有效地降低計(jì)算開銷.其次,該文提出一種巧妙的算法支持top-k局部比對(duì)查詢.該算法通過引入啟發(fā)式策略有效規(guī)避了TA算法的固有問題.具體地,它一方面可以提高算法的過濾能力,另一方面可以降低候選對(duì)象的維護(hù)代價(jià).再次,該文對(duì)外存后綴樹和磁盤的工作原理進(jìn)行了研究.基于此,該文提出一種槽的結(jié)構(gòu)支持查詢.該結(jié)構(gòu)既可以實(shí)現(xiàn)磁盤的順序訪問,又可以降低磁盤的訪問次數(shù).因此,它可以有效提高算法的查詢效率.最后,大量的實(shí)驗(yàn)驗(yàn)證了該文所提出算法的有效性.
【作者單位】： 東北大學(xué)信息科學(xué)與工程學(xué)院;
【關(guān)鍵詞】： 局部比對(duì) top-k 外存后綴樹 叉子區(qū)域
【基金】：國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃項(xiàng)目基金(2012CB316201) 國(guó)家自然科學(xué)基金(61572122,61173031,61129002,61532021,U1401256) 國(guó)家優(yōu)秀青年科學(xué)基金(61322208)資助~~
【分類號(hào)】：TP391.1
【正文快照】： 1引言 局部比對(duì)是在兩條文本串之間尋找近似子串的過程.它在生物信息學(xué)領(lǐng)域具有重要應(yīng)用[1-2].具體來(lái)說(shuō),它有助于研究人員分析不同基因片段的功能,確定它們?cè)谶z傳學(xué)上的意義[3-4].和常規(guī)文本數(shù)據(jù)相比,基因數(shù)據(jù)的規(guī)模較大.常規(guī)PC機(jī)的內(nèi)存往往無(wú)法容納這些數(shù)據(jù)[5-8],更無(wú)法容納

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

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

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

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

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

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

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

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

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

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

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

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前1條

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

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

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

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

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

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

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

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

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

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

9 張任文;生物序列索引結(jié)構(gòu)的研究與實(shí)現(xiàn)[D];哈爾濱工業(yè)大學(xué);2006年

10 張吉;基于后綴樹模型的流文本表示研究及其應(yīng)用[D];中國(guó)科學(xué)院研究生院（計(jì)算技術(shù)研究所）;2005年

，

本文編號(hào)：936596