生物序列數(shù)據(jù)庫(kù)中相似性查詢(xún)處理技術(shù)的研究.pdf

1、隨著基因測(cè)序技術(shù)和人類(lèi)基因組計(jì)劃的發(fā)展，人類(lèi)已獲得了大量的生物序列數(shù)據(jù)，并且其積累速度還在飛速增長(zhǎng)。生物信息學(xué)作為一個(gè)新興學(xué)科，對(duì)如何利用信息技術(shù)來(lái)分析生物數(shù)據(jù)，提供了有效的解決方法。 從生物角度來(lái)講，基因序列結(jié)構(gòu)的相似性往往導(dǎo)致其功能上的相似性。序列相似性查詢(xún)就是應(yīng)用這個(gè)原理，給定一條查詢(xún)序列，找到數(shù)據(jù)庫(kù)中滿(mǎn)足查詢(xún)條件的一條或多條相同或相似的已知生物序列，從而利用已知的生物序列推測(cè)這個(gè)查詢(xún)序列的功能。 序列相似性查詢(xún)技

2、術(shù)主要分為基于索引的方法和非索引方法兩類(lèi)。非索引方法通常需要搜索整個(gè)數(shù)據(jù)庫(kù)，隨著數(shù)據(jù)庫(kù)的不斷增大，其性能越來(lái)越不理想。因此，基于索引的方法就應(yīng)運(yùn)而生，由于這種方法不需要搜索整個(gè)數(shù)據(jù)庫(kù)，其性能比較理想。然而，現(xiàn)有的基于索引的方法還存在很多問(wèn)題。例如，MRS索引方法為了保證能將該索引裝入內(nèi)存，使其最小綁定矩形中所包含的向量較多，因此索引中最小綁定矩形的平均體積很大，從而導(dǎo)致查詢(xún)字符串到被索引的MBR距離變小，從而使得索引的過(guò)濾性能降低。

3、 本文從研究生物序列的相似性查詢(xún)?nèi)胧郑岢隽艘环N聚類(lèi)的多解析度字符串索引結(jié)構(gòu)。為了降低最小綁定矩形的平均體積，我們對(duì)包含字符串較少的最小綁定矩形進(jìn)行聚類(lèi)，壓縮了每個(gè)最小綁定矩形的最高點(diǎn)和最低點(diǎn)的平均距離，增加查詢(xún)點(diǎn)到索引的距離，從而大大地提高了原有索引結(jié)構(gòu)的過(guò)濾能力。而且我們還提出了一種新的后處理方法，對(duì)從索引中過(guò)濾出來(lái)的字符串進(jìn)一步篩選，大大地降低了字符串之間的編輯距離的計(jì)算次數(shù)，從而加快了查詢(xún)處理的性能。 大量的實(shí)驗(yàn)表明