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

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

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

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

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

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