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

1、隨著基因測序技術(shù)和人類基因組計劃的發(fā)展,人們積累了越來越多的生物序列信息.如何分析這些生物序列,從中找到人類和其它生物的遺傳規(guī)律,并提取有價值的知識,是目前人們面臨的最大挑戰(zhàn).生物信息學(xué)的出現(xiàn)為解決這一難題提供了有效的方法.從生物角度講,基因序列結(jié)構(gòu)的相似性往往導(dǎo)致其功能上的相似性.因此,我們可以通過搜索相似序列的方法預(yù)測新基因序列的功能.這就是我們研究序列相似性查詢技術(shù)的意義所在.現(xiàn)有的序列相似性查詢技術(shù)分為基于索引的方法和非索引方法

2、兩類.非索引方法往往需要搜索整個數(shù)據(jù)庫,因此其性能很不理想;而基于索引的方法不需要搜索整個數(shù)據(jù)庫,性能較好.然而,現(xiàn)有的基于索引的方法還存在很多問題.首先,這些方法在建立索引過程中使用的變換方法丟失了大量信息,從而導(dǎo)致其距離函數(shù)的過濾能力較弱,整個系統(tǒng)的性能不高;其次,它們不能處理任意長度的查詢;再次,其后處理階段有大量的冗余計算,影響了系統(tǒng)的性能.針對這些問題,該文提出了一種基于N分頻率變換(N-PFT)的序列相似性查詢方法——N-P

3、FT方法.首先,我們提出了一種N分頻率變換技術(shù),將字符串變換為高維空間中的向量.這種變換比現(xiàn)有的頻率變換和小波變換保留了更多的字符串位置信息,從而使基于這種變換的距離函數(shù)有更好的過濾能力.我們還分析了長度對距離的影響,進而解決了處理任意長度查詢序列的問題.同時,我們提出了一種新的后處理技術(shù),在保證正確性的同時避免了大量的冗余計算,使系統(tǒng)的性能得到了很大的提高.我們不僅對我們的方法給出了嚴(yán)格的理論證明,而且進行了大量的實驗.實驗結(jié)果表明,