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

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

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

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

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