基于塊排序索引的生物序列局部比對查詢技術(shù)參考模板

1、基于塊排序索引的生物序列局部比對查詢技術(shù)*Block Sorting Index-based Techniques for Local Alignment Searches on Biological Sequences李永光 王 鏑 王國仁 馬宜菲 (東北大學(xué)信息科學(xué)與工程學(xué)院計(jì)算機(jī)系統(tǒng)研究所 沈陽 110004)Abstract A common query against large protein and gene sequence data sets is to locate targets that are similar to an input query sequence. T

2、he current set popular search tools, such as BLAST, employs heuristics to improve the speed of such searches. However, such heuristics can sometimes miss targets, which in many cases is undesirable. The alternative to BLAST is to use an accurate algorithm, Such as Smith-Waterman(S-W) algorithm. Howe

3、ver, these accurate algorithms are computationally very expensive. Recently, a new technique, OASIS, has been proposed to improve the efficiency and accuracy by employing dynamical programming during traversing suffix tree and its speed is comparable to BLAST. But its main drawback is too much memor

4、y consuming. We propose an efficient and accurate algorithm for locally aligning genome sequences. We construct a block sorting index structure for the large sequence. The index structure is less than the suffix tree index and can be fit for large data size. Experimental results show that our algori

5、thm has better performance than OASIS.Keywords sequence; block sorting index; accuracy1 / 141. 引言隨著人類基因組計(jì)劃的不斷發(fā)展，在結(jié)構(gòu)基因?qū)W和功能基因?qū)W的研究過程中，生物序列的相似性分析成為一種有效的手段1。通常情況下，兩條DNA長序列，可能只在很小的區(qū)域內(nèi)(密碼區(qū))存在關(guān)系；不同家族的蛋白質(zhì)往往具有功能和結(jié)構(gòu)上的相同的一些區(qū)域。因而，研究序列局部相似性比研究全序列相似性往往更有意義。序列局部比對是一種關(guān)于片段相似性的定性描述1。通常的方法是通過動態(tài)規(guī)劃2進(jìn)行精確查找兩個序列的最優(yōu)局部比對，但因其代

6、價(jià)太大，對超長生物序列直接應(yīng)用這種技術(shù)是不可行的。為了提高查詢速度，啟發(fā)式算法當(dāng)前被廣泛應(yīng)用，這些算法可以分為三類：基于哈希表的算法、基于頻率空間過濾的算法、基于后綴樹索引的算法?；诠１淼牡湫退惴ㄓ蠪ASTA5和BLAST6。FASTA的核心思想是對數(shù)據(jù)庫序列中的所有模式進(jìn)行哈希索引。在查詢時基于哈希索引可以快速檢索出可能的匹配模式。然后根據(jù)這些模式的擴(kuò)展得到更長的序列。BLAST算法是建立在嚴(yán)格的統(tǒng)計(jì)學(xué)的基礎(chǔ)之上，它主要用于發(fā)現(xiàn)具有較高的相似性的局部比對。在大多數(shù)情況下，根據(jù)局部比對參數(shù)會產(chǎn)生若干個HSP(High-score Sequence Pairs)。然后把所有匹配分值大于閾值的

7、HSP作為結(jié)果。這種基于啟發(fā)式算法的過濾原理盡管在一定程度上盡量減少丟失局部比對的結(jié)果，但精確率卻不可能達(dá)到100%，一些符合條件的匹配序列可能不在查詢結(jié)果中。MRS4是基于頻率空間過濾的代表方法，它采用滑動窗口和小波變換技術(shù)，設(shè)計(jì)了一種高效的生物序列搜索方法。根據(jù)頻率距離是編輯距離的上界的過濾原理，可以節(jié)省大約50%的編輯距離計(jì)算。這種技術(shù)比較適合長的DNA序列，但不適合蛋白質(zhì)序列的比對分析。另外一些方法是基于后綴樹技術(shù)的, 該類方法一般是通過對一條序列構(gòu)建后綴樹，然后利用后綴樹快速查找到匹配的模式。對于后綴樹中的某個分支，如果完全匹配的模式的個數(shù)超過給定閾值，那么就對該分支使用BLAST作

8、進(jìn)一步的查詢。這類算法對閾值比較低的查詢處理效率太低。OASIS3通過在遍歷后綴樹的同時運(yùn)用動態(tài)規(guī)劃算法，提供了一種精確的序列局部比對的搜索方法。其實(shí)驗(yàn)結(jié)果表明，它比動態(tài)規(guī)劃算法快很多，而且可以和BLAST相提并論，但存儲后綴樹需要很大的存儲空間，其構(gòu)造過程也是復(fù)雜的。本文首先提出了一種基于塊排序索引算法來計(jì)算序列比對，我們引入基于這種索引結(jié)構(gòu)的片斷向量的概念，通過片斷向量的擴(kuò)展完成動態(tài)規(guī)劃算法，從而完成序列比對查找過程。算法采用A*8搜索策略，進(jìn)行過濾，當(dāng)計(jì)算查詢序列部分匹配時，搜索算法同時計(jì)算匹配剩余查詢所得分值的上界，根據(jù)閾值，如果上界分值小于閾值，那么該片段向量就被過濾掉，從而減少搜索

9、空間的計(jì)算。在搜索的每一步，算法首先擴(kuò)展可能產(chǎn)生最優(yōu)局部比對的片斷向量，這就能保證返回的結(jié)果按照比對的分值由達(dá)到小排序。實(shí)驗(yàn)結(jié)果表明，我們的算法在性能和過濾能力上都優(yōu)于OASIS。本文的主要貢獻(xiàn)在于通過運(yùn)用較小的索引結(jié)構(gòu)，我們提出一種精確有效的局部比對搜索算法，因而這種算法為在大的生物數(shù)據(jù)集提供了一種可行有效的精確局部比對查找策略。本文余下部分的組織結(jié)構(gòu)如下：第2部分給出了本文的背景知識；第3部分具體介紹了核心數(shù)據(jù)結(jié)構(gòu)和算法；第4部分給出了測試結(jié)果和性能分析；第5部分總結(jié)全文。2. 背景知識動態(tài)規(guī)劃算法能精確計(jì)算生物序列全局和局部比對，在這一部分，我們首先介紹生物序列的局部比對的概念，然后討論

10、動態(tài)規(guī)劃算法的相關(guān)工作，最后介紹塊排序索引結(jié)構(gòu)。2. 1 序列局部比對給定兩條字符序列Q=q1q2qm, T=t1t2tn,這兩條序列的局部比對是指通過某種方式是“排列”Q和T的子序列。圖1給出一個局部比對例子，同時給出三種類型的局部比對操作。l 替換：用相同或者不同字符進(jìn)行替換（如圖1中的1和2標(biāo)記）。l 刪除：允許在目標(biāo)序列中忽略一個字符（如圖1中的3標(biāo)記）。l 插入：允許在查詢序列中忽略一個字符（如圖1中的4標(biāo)記）。31124Target：C A B I N 1Query： D R A I N 圖1. 局部比對的樣例序列是通過三種操作所得到的分值之和來確定比對得分。每種操作可以形象描述為

11、替換操作“”，其中插入操作表示為“ ”,刪除操作表示為“ ”，操作的罰分可以標(biāo)記為S（）?？梢酝ㄟ^替換矩陣S存儲這些分值，所以“”的操作代價(jià)可以簡單表示為S,。表1給出一個通用的替換矩陣的樣例。稱為單位編輯距離矩陣（因?yàn)橥耆ヅ浞种禐?，否則為-1）。ACGTA1-1-1-1-1C-11-1-1-1G-1-11-1-1T-1-1-11-1-1-1-1-1-表1：單位編輯距離矩陣2. 2 Smith-Waterman(S-W)算法Smith-Waterman算法通過動態(tài)規(guī)劃2的方法計(jì)算兩條序列局部比對的最大的可能分值，計(jì)算過程需要O(mn)空間和時間的復(fù)雜度。算法形成一個m×n的矩陣G

12、，Gi,j保存查詢序列和目標(biāo)序列分別結(jié)束在qi和tj的最大比對分值。每一個Gi,j是通過下面的公式(1)計(jì)算出來的： （1）2. 3塊排序索引結(jié)構(gòu)對于長度為n的序列S（我們的應(yīng)用中，S以非序列中出現(xiàn)的字符作為結(jié)束字符，我們選用結(jié)束字符$，并規(guī)定$的字典序小于序列中的所有其它字符），進(jìn)行塊排序時對序列S循環(huán)移動0n-1位，得到一個n行列表，將各行按升序排序，就得到了矩陣M，如圖2所示，左側(cè)是對序列AGTACGCCTAG$的塊排序結(jié)果, 這里我們不詳細(xì)說明構(gòu)造的過程，細(xì)節(jié)可看見7等文獻(xiàn)。圖2：序列AGTACGCCTAG的塊排序索引結(jié)構(gòu)下面我們描述基于塊排序的索引結(jié)構(gòu)。為了描述的方便我們將矩陣M的第

13、一列稱為F列，最后一列成為L列。Fi和Lj分別表示F列中的第i個字符和L列中的第j個字符。另外，我們引入函數(shù)count (F,i)在F列的前i個字符中，F(xiàn)i出現(xiàn)的次數(shù)。類似的，我們也定義count (L,j)。現(xiàn)在，我們給出在塊排序結(jié)構(gòu)中一個字符的后繼字符的表達(dá)。對于一個字符Fi，如果Fi=Lj并且count（F，i）=count（L，j），則Fj是Fi在給定序列中的后繼字符。塊排序結(jié)構(gòu)由F列和T列構(gòu)成，Ti是一個整數(shù)，它表示Fi的后繼字符在F列中的位置，即FTi是Fi在原序列中的后繼字符。例如，圖2給出序列AGTACCGCCTAG$的塊排序結(jié)果。F3的后繼字符是FT3，即F5。塊排序索引就有

14、如下的保序性：性質(zhì)1對于F中的任意字符Fi和Fj，如果Fi=Fj并且i<j，則Ti<Tj。證明：令si是矩陣M中的第i行代表的序列，則Fi是si的第一個字符。對于兩個序列si和sj，它們的先后關(guān)系是由兩序列中的第一個不相同的字符決定的。如果Fi=Fj，則si和sj的順序與sTi和sTj的順序是相同的。因此，若i<j，則Ti<Tj。例如，在圖2中 F1=F2=F3=A，則（T1=3）< (T2=5) < (T3=7)。在這邊文章中，我們對DNA序列建立索引，因此序列的字符集為A，C，G，T，$。令s是一長度為n的DNA序列，l1，l2，l3，l4分別代表A，C

15、，G，T在F列中的首個字符的位置。則索引中的F列具有如下性質(zhì)： 因此，根據(jù)塊排序索引的性質(zhì)，我們僅需要存儲5個整數(shù)和T列作為索引就可以完成任意子序列的查找過程，因而基于該索引，我們能完成局部比對的查找過程。3. 基于塊排序索引（Block Sorting）局部比對查找的算法根據(jù)塊排序索引結(jié)構(gòu)特點(diǎn)，本部分首先給出有關(guān)定義，然后根據(jù)問題的定義，給出算法的具體實(shí)現(xiàn)過程，最后給出算法的削減策略。3. 1 定義定義1 (片斷向量) 根據(jù)索引結(jié)構(gòu)中的T列，我們會得到一組向量，其中每一個向量保存某個字符在索引中的位置信息，該向量稱為片斷向量。例如，在圖2中 10，11 代表字符T在索引中的第10和11位置上

16、，1 ，2代表在索引第一次擴(kuò)展后，字符T的后繼字符在索引中的位置為1和2。定義2（根向量）根據(jù)塊排序索引，我們首先會得到每個字符在索引中的范圍，根據(jù)這個范圍我們會得到每個字符初始狀態(tài)的位置向量，該向量成為根向量例如，在圖2中，1，2，3 為字符A的根向量，4，5，6 為字符C的根向量。定義3（后繼向量和前驅(qū)向量）根據(jù)索引結(jié)構(gòu)中的T列，片斷向量frag1的后繼產(chǎn)生的向量稱為frag1的后繼向量，frag1稱為前驅(qū)向量。例如，在圖2中，1，2 為 10，11 的后繼向量，3 和5 是1，2的后繼向量，同時 10，11 為 1，2 的前驅(qū)向量，1，2 為 3 和 5 的前驅(qū)向量。定義4（向量擴(kuò)展）假

17、設(shè)frag1為一片斷向量，我們得到frag1所有后繼向量的過程稱為向量frag1的擴(kuò)展。例如，在圖2中，我們開始得到字符T的根向量 10，11，然后我們根據(jù)索引結(jié)構(gòu)中的T列信息就會得到其后繼向量 1，2，依次類推，我們通過擴(kuò)展就能得到所有以字符T開始的所有子序列。圖3：向量10，11擴(kuò)展過程定義5（擴(kuò)展路徑）從根向量開始，片段向量擴(kuò)展過程會產(chǎn)生一些路徑，其中每一條路徑對應(yīng)于目標(biāo)序列中的某一子序列，該子序列的長度即為路徑的長度，該路徑稱為擴(kuò)展路徑。例如，在圖3中，10158和11270稱為索引擴(kuò)展路徑，分別代表子序列TACG和TAC$。3.2算法描述算法核心為在局部比對的搜索過程中執(zhí)行優(yōu)者為先A

18、*算法。在塊排序索引結(jié)構(gòu)擴(kuò)展過程中完成動態(tài)規(guī)劃算法，描述如算法1所示，其中輸入?yún)?shù)如下：l BS：目標(biāo)序列的塊排序（Block Sorting）索引結(jié)構(gòu)；l Q：查詢序列，q1q2qm；l S：任意的一個替換矩陣；l minScore：比對要求的最小值；這些參數(shù)同時也是初始化函數(shù)的輸入?yún)?shù)，所有分值大于minScore的比對按分值由大到小返回。算法1：局部比對搜索過程（）Search Process ( )輸入：目標(biāo)序列的塊排序索引BS；查詢序列Q；打分矩陣S；閾值minScore輸出：目標(biāo)尋列中與查詢序列相似的子序列；算法描述：1: H,PQ= Initialize(BS,Q,S,minSc

19、ore);2: while ( !Empty(PQ ) ) do3: SearchVector PQ.Pop();4: if ( SearchVector.tag = Viable ) then5: for ( successor Successors(SearchVector) do6: newBlock Expand(SearchVector,successor,H,Q,S,minScore);7: if ( newBlock.tag = Accepted newBlock.tag=Viable);8: PQ.Push(newBlock);9: end if10: end for11: e

20、lse if ( SearchVector.tag=Accepted) then12: Return subsequence containing Path ( SearchVector.vec);13: end if14: end while在算法中，每個SearchVector與塊排序索引擴(kuò)展過程中的片斷向量一一對應(yīng)，如圖4表示圖2索引結(jié)構(gòu)一步擴(kuò)展后，得到片段向量1,2對應(yīng)的SearchVector。SearchVector表示部分目標(biāo)序列與查詢序列的比對，即查詢序列和目標(biāo)序列結(jié)束在對應(yīng)于其片斷向量的路徑對應(yīng)的子序列的比對。每個SearchVector存儲查詢序列從開始到每個字符比對得分，

21、同時計(jì)算計(jì)算匹配查詢序列剩余部分的最大的可能比對得分。這些得分的總和用來在優(yōu)先級隊(duì)列PQ中組織這些SearchVector。算法總是選擇優(yōu)先級隊(duì)列中的首個元素然后擴(kuò)展它的后繼向量。因?yàn)樗惴偸菙U(kuò)展在隊(duì)列首部的SearchVector，所以可以近似看成優(yōu)者為先的A*算法。算法中SearchVector為核心數(shù)據(jù)結(jié)構(gòu)，現(xiàn)簡要說明一下它包含以下數(shù)據(jù)域：Vec：擴(kuò)展過程中的片斷向量，其擴(kuò)展路徑與目標(biāo)序列中子序列一一對應(yīng)。Z：為某一向量 Z0,Z1.,Zm，其中Zi 記錄對應(yīng)與從根向量擴(kuò)展到片段向量Vec的擴(kuò)展路徑所對應(yīng)序列與查詢序列Q結(jié)束在qi的子序列之間的最好局部比對得分。如果當(dāng)前的比對被削減（削減

22、策略將會后面討論），則Zi被設(shè)為-。向量Z，粗略的講，是和表2中S-W算法矩陣中的某一列對應(yīng)的。maxScore：沿當(dāng)前路徑所得到的最大比對得分。這個分值是是對應(yīng)于當(dāng)前路徑的序列與查詢序列的任何子序列的最好的比對得分。maxf：通過進(jìn)一步擴(kuò)展該Vec所能得到的最大的可能比對得分。tag：標(biāo)記當(dāng)前SearchVector的狀態(tài)，可能的取值為Accepted、Viable、Unviable，如果查詢序列與當(dāng)前路徑的序列比對最好得分已經(jīng)得到，并且達(dá)到閾值的要求，則該SearchVector被標(biāo)記為Accepted，當(dāng)該SearchVector在優(yōu)先隊(duì)列PQ的首部時，我們就會得到該查詢的最好的局部比對

23、結(jié)果。如果tag標(biāo)記為Viable，則說明在當(dāng)前路徑上還可能得到更好的比對得分。如果當(dāng)前路徑無論怎么擴(kuò)展所得到的最好局部比對得分都比都達(dá)不到閾值的要求，則tag標(biāo)記為Unviable，對應(yīng)的片斷向量也就被削減掉。標(biāo)記為Accepted和Viable的SearchVector被放入優(yōu)先級隊(duì)列。優(yōu)先隊(duì)列是以maxf的值進(jìn)行組織的，所以首先擴(kuò)展的SearchVector必須保證隊(duì)比隊(duì)列中的其它SearchVector可能產(chǎn)生更高比對得分。通過優(yōu)先隊(duì)列的排序，算法擴(kuò)展隊(duì)列首部的SearchVector的后繼向量，如算法3所示。擴(kuò)展過程會增加隊(duì)列中的元素，搜索結(jié)束的條件是隊(duì)列為空（具體看算法1）。圖4：

24、對應(yīng)于片斷向量1，2的SearchVector結(jié)構(gòu)3.2.1初始化過程算法開始計(jì)算一個啟發(fā)式向量H，同時根據(jù)索引結(jié)構(gòu)中的根向量初始化優(yōu)先隊(duì)列。具體步驟如算法2所示。H中的每個元素hi代表qi+1qi+2qm與任意目標(biāo)最大的可能比對得分（假設(shè)Q=q1q2qm）。因此，計(jì)算H是比較簡單的。假設(shè)插入和刪除操作的罰分都為非正值，hm可設(shè)為0，因?yàn)椴樵冃蛄凶蟛糠謺r空字符串，然后我們就能逐步計(jì)算H中其它元素的值：hi-1=hi + 替換qi-1的最大得分。每個RootVector對應(yīng)于索引結(jié)構(gòu)的根向量，其路徑長度為1。因?yàn)楸葘Ψ种当４嬖赯向量中，如果分值設(shè)為-則這部分比對可以過濾掉。被過濾掉的意思即當(dāng)H中

25、的hi比給定的閾值小，這意味繼續(xù)計(jì)算也不可能得到一個更有意義的序列局部比對。算法2：初始化（H , PQ）Initialize( )輸入：目標(biāo)序列的塊排序索引SA；查詢序列Q；打分矩陣S；閾值minScore；輸出：啟發(fā)式向量H；優(yōu)先隊(duì)列PQ；算法描述：1: hi hi+1 + max S(qi );2: for ( every RootVector ) do3. compute Zi , maxScore, maxf, tag;3: if ( RootVector.tag=Accepted RootVector.tag= Viable ) then4: PQ.Push (RootVector

26、);5: end if6: end for7: return H,PQ;3.2.2擴(kuò)展過程算法3給出了完整的塊排序索引擴(kuò)展算法。輸入當(dāng)前的片斷向量和其后繼片斷向量，算法開始時初始化Successor（為一SearchVector結(jié)構(gòu)）的Vec和maxScore。其中矩陣M的各個元素根據(jù)S-W算法得到的，稍微不同的是，每個元素不會設(shè)為0。在S-W算法中,0代表重新進(jìn)行一個新的比對。在我們的算法中不需要這種設(shè)定，因?yàn)閺乃饕械母蛄块_始，所有目標(biāo)序列的子序列都會找到，繼續(xù)設(shè)為0意味著在別的地方重復(fù)以前的工作。因?yàn)榕c查詢所有的比對都會在計(jì)算M時考慮到，并且根據(jù)塊排序的重要性質(zhì)，每條子序列都對應(yīng)于索引

27、擴(kuò)展中的每一條路徑，所以所有從查詢序列開始的比對都會考慮，因而不會丟失任何比對的結(jié)果。算法3：基于塊排序過濾的比對擴(kuò)展算法 Expand ()輸入：當(dāng)前的片斷向量；后繼片斷向量；輸出：可能產(chǎn)生結(jié)果的后繼向量算法描述：1: Successor.Vec the first successor SearchVector;2: Successor.maxScore SearchVector.maxScore;3: for ( i 1.m ) do4: Mi,0 the current SearchVector.Zi; 5: Mi,1 max( Mi-1,0 + S( qi c), Mi-1,1 + S

28、( qi -), Mi,0 + S( - c)6: if ( Mi,1 > Successor.maxScore ) then7: Successor.maxScore Mi,1;8: Successor.maxf max (Mi,1 + hi );9: end if10: end for11: if (Successor.maxScore >= Successor.maxf) && (Successor.maxScore> minScore ) ) then 12: Successor. tag Accepted;13: return Successor;

29、14: else if (Successor.maxScore < minScore) 15: Successor. tag Unviable;16: return Successor;17: end if18: if ( IsEnd (Successor) then19: if (minScore Successor.maxScore) then 20: Successor.tag Accepted;21: Successor.maxf Successor.maxScore;22: else 23: Successor.tag Viable;24: Successor.Z Mi,1;2

30、5: end if26: return Successor;3.3削減策略計(jì)算mi,j后，算法進(jìn)行比對計(jì)算削減，在不能繼續(xù)擴(kuò)展的比對位置上設(shè)置比對得分-。這個過程允許算法丟棄一些SearchVector，因?yàn)檫@些SearchVector或者不能繼續(xù)擴(kuò)展，或者被其它擴(kuò)展路徑包含。在下列三種情況下執(zhí)行削減策略：1. 比對得分為非正數(shù)（mi,j 0）：為了避免重復(fù)工作，所有比對得分為負(fù)數(shù)的片斷向量就被消減掉。考慮一部分查詢qaqa+1qb和一部分目標(biāo)序列tctc+1td進(jìn)行局部比對，如果開始位置位qatc，結(jié)束位置為qbtd的最大比對得分為負(fù)數(shù)，那么我們就能保證任何關(guān)于qaqb和tctd的比對得分會

31、比qb+1和td+1比對得分小，而第二個比對會在另外的擴(kuò)展路徑得到。所以沒有必要保存第一個比對，更沒必要擴(kuò)展第一個比對結(jié)果。2. 存在的比對已經(jīng)是最優(yōu)的（mi，j+hiblock.maxScore）：基于良好的啟發(fā)性，在當(dāng)前的擴(kuò)展路徑上，對比對進(jìn)行擴(kuò)展不會得到比當(dāng)前結(jié)果更好的結(jié)果，即當(dāng)前片斷向量的后繼向量不會產(chǎn)生更好的比對。3. 閾值限制（mi，j+hi minScore）：當(dāng)前比對即使繼續(xù)擴(kuò)展也不會產(chǎn)生一個能大于閾值的比對得分。在這些條件的限制下，算法就能在某條擴(kuò)展路徑上停止繼續(xù)擴(kuò)展，通過啟發(fā)式向量H，我們能夠確定作進(jìn)一步擴(kuò)展的最大可能比對得分的上界，即maxf的數(shù)值。如果當(dāng)前的擴(kuò)展路徑的比

32、對得分不小于這個商界（maxf maxScore），算法就停止繼續(xù)擴(kuò)展，然后根據(jù)是否達(dá)到minScore的限制，返回一個Accepted或者Unviable的結(jié)果。當(dāng)比對得分還能進(jìn)一步提高（maxf > maxScore）,則要看有無必要在該路徑上作進(jìn)一步擴(kuò)展：如果maxf小于minScore，則返回標(biāo)記為“Unviable”的SearchVector，否則標(biāo)記為“Viable”。 4. 性能測試和分析為了測試基于塊排序過濾器的局部比對搜索算法的性能，我們在同樣的平臺上實(shí)現(xiàn)了我們的算法和基于后綴樹的算法（OASIS），所有的測試都是在一臺Intel Pentium 4 *2.0GHz C

33、PU，2G內(nèi)存，1T硬盤IBM x Series 345服務(wù)器上進(jìn)行的。我們使用比較流行的人類染色體chr22 和chr18的片斷和Drosophila melanogeneses作為測試數(shù)據(jù)，使用當(dāng)前比較流行的單位編輯距離替代矩陣進(jìn)行比對分值計(jì)算。系統(tǒng)使用的操作系統(tǒng)為Windows 2003，使用Microsoft Visual Studio.2003編譯器編譯。4.1閾值minScore對算法性能的影響OASIS 是基于后綴樹技術(shù)進(jìn)行精確局部比對查詢的算法，在實(shí)驗(yàn)中，我們算法與OASIS性能比較，我們通過minScore 參數(shù)控制查詢的敏感度。公式（2）給出期望得到的比對個數(shù)E與比對得分S

34、的關(guān)系： （2） 其中，m是查詢序列的長度，n為數(shù)據(jù)庫的大小，K和是通過BLAST計(jì)算的常數(shù)，所以算法中的minScore可以用公式（3）進(jìn)行計(jì)算： （3） 圖 5 給出根據(jù)minScore的影響下，兩種算法的比較。對于查詢序列，我們用Drosophila melanogenetic chromosome NT_033778 的子序列（TAAACTTGGCCTGCTT）,用Drosophila melanogenetic chr4 全序列作為目標(biāo)序列。查詢時間在圖中是取以2為底數(shù)的對數(shù)數(shù)值，查詢序列的長度為16，minScore的范圍412，因?yàn)槲覀兯惴ǖ膯l(fā)性比較好，所以從圖中不難看出，mi

35、nScore對我們的算法的影響比較小。圖5：閾值minScore對查詢性能的影響4.2 查詢長度和數(shù)據(jù)庫數(shù)據(jù)大小對算法性能的影響我們根據(jù)查詢序列的長度和目標(biāo)序列的大小進(jìn)行性能比較。圖6說明了不同查詢長度對查詢性能的影響，圖7給出不同目標(biāo)序列大小對查詢性能的影響。我們使用8M的目標(biāo)序列，目標(biāo)序列是人類的基因序列chr22片段，查詢序列為隨機(jī)截取chr18的子序列。因?yàn)樵谖覀儗?shí)驗(yàn)機(jī)器的內(nèi)存限制下，OASIS無圖6：查詢長度對查詢性能的影響法為這些數(shù)據(jù)集大于10M的目標(biāo)序列構(gòu)建后綴樹索引，而Block Sorting (BS)我們可以為17M的數(shù)據(jù)構(gòu)造索引結(jié)構(gòu)。所以在圖6中我們的目標(biāo)序列大小為8M的

36、數(shù)據(jù)，圖7中OASIS算法我們最大的目標(biāo)序列為9M的數(shù)據(jù)，BS算法則測試到17M的數(shù)據(jù)。擴(kuò)展對于OASIS算法對于返回的Accepted 結(jié)果，如果為未非葉子節(jié)點(diǎn)，則必須通過遍歷后綴樹后，然后根據(jù)得到的葉子節(jié)點(diǎn)才能得到子序列在目標(biāo)序列中的位置，而基于Block Sorting（BS）算法中，返回Accepted結(jié)果的Vec中就已經(jīng)保存了子序列的位置信息。所以在一定程度上提高了速度。圖7： 目標(biāo)長度對查詢性能的影響4.3過濾效率的性能比較我們同時計(jì)算所要求擴(kuò)展的列，即目標(biāo)序列中需要進(jìn)行動態(tài)規(guī)劃計(jì)算的部分，從而反映出兩種算法的過濾效率。圖8給出兩種算法的過濾能力比較，對于Block Sorting（BS）算法每次擴(kuò)展一步后就會加以判斷當(dāng)前可能的最優(yōu)擴(kuò)展的片段向量，然后對此片段向量進(jìn)行繼續(xù)擴(kuò)展，而對于OASIS，根據(jù)后綴樹結(jié)構(gòu)，需要根據(jù)節(jié)點(diǎn)的對應(yīng)的子序列的長度進(jìn)行多步擴(kuò)展后才能對當(dāng)前的所有可擴(kuò)展后綴樹節(jié)點(diǎn)做出最優(yōu)的判斷，而算法所有擴(kuò)展步數(shù)之和即為動