生物序列數(shù)據(jù)庫相似性搜索算法研究.pdf

1、隨著國際人類基因組計劃的啟動，生物序列數(shù)據(jù)庫的數(shù)據(jù)呈爆炸性增長，生物序列數(shù)據(jù)庫中的數(shù)據(jù)蘊含著大量的信息和知識，如何挖掘和利用這些信息和知識是值得研究的問題。生物序列數(shù)據(jù)庫相似性搜索是生物信息處理中最基本的一個問題，通過比較待查詢的序列和數(shù)據(jù)庫的目標(biāo)序列的相似程度進(jìn)而推斷其同源性，以便滿足生物學(xué)研究人員的研究和應(yīng)用需求。雖然目前生物序列數(shù)據(jù)庫提供了基因序列數(shù)據(jù)進(jìn)行存儲管理和相似性搜索等功能，但是生物數(shù)據(jù)庫的序列數(shù)據(jù)增長達(dá)到了驚人的速度，平

2、均每十四個月就要翻一番，這對生物序列數(shù)據(jù)庫相似搜索算法的速度提出了挑戰(zhàn)。目前，大部分生物序列數(shù)據(jù)庫相似搜索算法的速度是通過犧牲一定的靈敏度而獲得的，如何研究和設(shè)計同時滿足高靈敏度和快速的生物序列數(shù)據(jù)庫相似搜索的算法是值得思考的問題。因此，本文的具體工作如下:
　　1、總結(jié)了點陣圖法和基于動態(tài)規(guī)劃算法的雙相似性序列比對算法，它們是最基本的生物序列相似性比對算法，也是生物數(shù)據(jù)庫相似搜索的理論基礎(chǔ)和靈敏度參照的標(biāo)準(zhǔn);詳細(xì)介紹了生物序列數(shù)

3、據(jù)庫相似性搜索算法的原理和經(jīng)典的生物序列數(shù)據(jù)庫相似性搜索算法，即BLAST算法、FASTA算法和PatternHunter算法。
　　2、研究了生物序列數(shù)據(jù)庫相似性搜索算法的重要參數(shù)-種子。種子是調(diào)節(jié)生物序列數(shù)據(jù)庫相似性搜索的速度和靈敏度閥門，目前使用的連續(xù)種子和空位種子相對靈敏度較低，如何設(shè)計高效率的種子是關(guān)鍵問題。因此，本文提出了一種新的匹配模式的種子-模糊匹配種子，理論和實驗證明模糊匹配種子在同樣的搜索長度下比連續(xù)種子和空位

4、種子具有更高的靈敏度，使用模糊匹配種子可以提高生物數(shù)據(jù)庫相似性搜索的性能。
　　3、給出了模糊匹配種子的最優(yōu)化計算方法。傳統(tǒng)的生物序列數(shù)據(jù)庫相似性搜索的種子長度都是取得一個經(jīng)驗值，在搜索的時候并不滿足最優(yōu)靈敏度且自適應(yīng)性較差。本文設(shè)計了一種模糊匹配種子的最優(yōu)靈敏度的數(shù)學(xué)規(guī)劃模型，并根據(jù)其數(shù)學(xué)模型的特點設(shè)計了一種簡單的求解方法。
　　4、本文還研究了局部相似性區(qū)域種子連接的問題。由于基因序列的基本操作還包括插入和刪除，而插入和