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

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

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

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