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

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

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

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