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

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

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

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