近似文本比對技術(shù)及其優(yōu)化方法.pdf

1、目前大部分信息以無結(jié)構(gòu)文本的形式存在，所以基于文本的信息檢索技術(shù)，如近似子串查詢技術(shù)，受到格外關(guān)注。同時，隨著測序技術(shù)的進步，現(xiàn)今進行基因測序無論從速度還是花費等方面都變得十分容易。測序技術(shù)的長足進步對基因數(shù)據(jù)分析技術(shù)，如生物序列局部比對技術(shù)，提出了更高的挑戰(zhàn)。無論是基于文本的信息檢索還是對基因數(shù)據(jù)的分析，其核心都是近似文本比對技術(shù)，而本文主要研究如何優(yōu)化近似文本比對技術(shù)以更有效的解決近似子串查詢問題和生物序列局部比對問題。
　　

2、目前，經(jīng)典的子串查詢算法，如BM(Boyer-Moore)和KMP(Knuth-Morris-Pratt)算法，都是針對精確子串查詢的。而且，目前的字符串近似查詢算法也都是先給定編輯距離的閾值k，然后然后計算那些與查詢串的編輯距離小于或等于k的結(jié)果。但是對于近似子串查詢，這樣的結(jié)果中有很多是交疊的并且是無意義的，因此如何優(yōu)化文本比對技術(shù)，以便高效地獲得有價值的近似子串查詢結(jié)果很具有挑戰(zhàn)性。對于局部比對問題，目前已經(jīng)存在一些非常經(jīng)典的局部

3、比對工具，但都存在效率或準(zhǔn)確度方面的問題。如SW(Smith-Waterman)算法雖然能夠找到完全解但是由于時間和空間上消耗都太大，以至于很少在實際中應(yīng)用。BLAST(Basic Local Alignment Search Tool)是一種經(jīng)典并且目前非常流行的進行生物序列局部比對的工具，雖然擁有很高的效率但并不能保證找到全部結(jié)果。最近提出的BWT-SW算法能夠保證找到完全解，并且有較高的效率，但相比于BLAST還是慢很多。如何能夠

4、在保證完全解的情況下有效地提高比對效率對人們提出了更高的挑戰(zhàn)。
　　針對近似子串查詢問題中存在的問題，本文首先提出了一種局部最優(yōu)化匹配的概念，以解決結(jié)果交疊的問題。然后分析了子串近似匹配過程中的規(guī)律，分別給出了針對局部最優(yōu)化匹配的邊界限定和過濾策略，并且結(jié)合本文提出的基于gram索引的局部最優(yōu)化近似子串查詢算法給出了過濾優(yōu)化的局部最優(yōu)化近似子串查詢算法，提高了查詢效率。針對局部比對問題，本文以動態(tài)規(guī)劃算法為基礎(chǔ)并提出了一系列過濾和

5、重用技術(shù)，首先分析了采用動態(tài)規(guī)劃方法計算的過程中的規(guī)律，提出了一系列過濾方法來避免進行不必要的計算，然后針對查詢序列中存在的重復(fù)子序列設(shè)計了重用技術(shù)，避免了重復(fù)計算。結(jié)合本文提出的一系列過濾和重用技術(shù)，給出了解決局部比對問題的ALAE(Accelerating Local Alignment with Affine Gap Exactly)算法，不僅能夠保證得到完全解并且擁有很高的效率。最終在實際數(shù)據(jù)集上的測試證明本文提出的算法都有很高