K-前綴樹全文搜索方法及其應用.pdf

1、在科學技術(shù)高速發(fā)展和信息爆炸式膨脹的時代，如何快速和有效的從海量信息中獲取有用信息是信息檢索技術(shù)主要的研究課題。當前應用廣泛的后綴樹和后綴數(shù)組全文搜索方法在搜索速度和計算空間方面各有特點和局限，本文正是針對此問題提出了K-前綴樹全文搜索方法。 K-前綴樹全文搜索方法是一種基于前綴樹且能夠?qū)?nèi)容長度不大于K的字串進行搜索的文本全文搜索方法，其主要特點是使用K子串來構(gòu)建前綴樹，使得最大空間復雜度為O(Zk+1)，并具有折中后綴數(shù)和

2、后綴數(shù)組在計算空間和搜索速度上的優(yōu)點。通過與廣泛應用的后綴樹和后綴數(shù)組兩種全文搜索方法的計算比較，說明了K-前綴樹全文搜索方法在計算空間和搜索速度上具有良好的綜合性能。 載體識別是生物信息學中一項基礎(chǔ)而重要的任務，對去除EST序列中的污染和提取cDNA inset具有重要作用。本文針對植物EST序列的載體識別問題，基于EST序列期望結(jié)構(gòu)給出了EST序列的載體結(jié)構(gòu)描述，由此結(jié)合K-前綴樹全文搜索方法提出了基于K-前綴樹的EST序列