基于后綴樹(shù)與后綴數(shù)組混合結(jié)構(gòu)的基因序列比對(duì)算法研究.pdf

1、分類(lèi)號(hào)TP301學(xué)校代碼10129UDC004學(xué)號(hào)2012210007基于后綴樹(shù)與后綴數(shù)組混合結(jié)構(gòu)的基因序列比對(duì)算法研究StudiedonGeneSequenceAlignmentBasedonmixedSuffixTreeSuffixArray申請(qǐng)人：焦雅學(xué)科門(mén)類(lèi)：工學(xué)學(xué)科專(zhuān)業(yè)：軟件工程研究方向：生物信息與大數(shù)據(jù)處理指導(dǎo)教師：高靜教授論文提交日期：二〇一五年六月摘要隨著基因測(cè)序技術(shù)的迅猛發(fā)展，基因數(shù)據(jù)庫(kù)中序列公共數(shù)據(jù)量呈指數(shù)形式增長(zhǎng)。

2、對(duì)于基因數(shù)據(jù)最基礎(chǔ)但最重要的分析方法為序列比對(duì)。本文通過(guò)對(duì)現(xiàn)今常用的分析算法和分析軟件在序列的類(lèi)型、特點(diǎn)和功能等方面研究和比較，發(fā)現(xiàn)序列比對(duì)算法的重點(diǎn)是對(duì)基因數(shù)據(jù)結(jié)構(gòu)進(jìn)行有效組織。目前這些數(shù)據(jù)結(jié)構(gòu)有哈希表和后綴樹(shù)、后綴數(shù)組，本文在此研究基礎(chǔ)上提出了新的算法BWL。BWL算法的特點(diǎn)：(1)采用了新的數(shù)據(jù)結(jié)構(gòu)，即后綴樹(shù)與后綴數(shù)組混合的新的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)不僅占用內(nèi)存空間比較小，解決了基因數(shù)據(jù)文件因內(nèi)存受限的問(wèn)題，而且能減少與外存頻繁交

3、互，提高比對(duì)運(yùn)算速度。(2)BWL算法在序列比對(duì)過(guò)程中引進(jìn)空位種子模型，提高算法敏感度。對(duì)于沒(méi)有完全匹配的序列，采用加入空位的方法，相對(duì)于精確的動(dòng)態(tài)規(guī)劃法或?qū)δＰ椭鹞谎h(huán)進(jìn)行增、刪、改再比對(duì)的試探方法在運(yùn)算速度方面有了進(jìn)一步提升，算法有效性明顯提高。最后本文做了序列比對(duì)仿真實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了詳細(xì)的分析。分析結(jié)果表明，本文提出的后綴樹(shù)與后綴數(shù)組混合的數(shù)據(jù)結(jié)構(gòu)占用內(nèi)存不會(huì)隨著基因數(shù)據(jù)的大小而改變，索引構(gòu)建速度也較其他算法更快。另外，序