一般間隙近似無重疊模式匹配

武優(yōu)西,陳 彤,閆文杰,高雪冬

(河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院,天津 300401) (河北省大數(shù)據(jù)重點實驗室,天津 300401)

1 引 言

模式匹配(又稱字符串匹配)是計算機(jī)科學(xué)的基礎(chǔ)問題之一[1],其在生物信息學(xué)[2]、網(wǎng)絡(luò)入侵[3]以及數(shù)據(jù)挖掘[4]等諸多領(lǐng)域具有重要應(yīng)用,其問題實質(zhì)是在一個相對長的序列串S上查找相對較短的模式P所有出現(xiàn)的位置及個數(shù),這里序列串S以及模式P必須采用相同的字母表中[5].

近年來,為了滿足實際需要,在傳統(tǒng)通配符的基礎(chǔ)上,研究者們致力于間隙約束的模式匹配,其模式串P可以表示為:P=p1[a1,b1]p2…[aj,bj]pj+1…[am-1,bm-1]pm(1≤j≤m),其中aj和bj分別為pj和pj+1之間通配符之間最小和最大通配符的個數(shù).這種間隙約束的模式在序列模式挖掘中亦有深入探索,如Min等人[6]在間隙約束下探索了序列中字符作用不均等的模式挖掘方法;Wu等人[7]采用網(wǎng)樹結(jié)構(gòu)對周期性一般間隙的序列模式挖掘問題進(jìn)行研究;Ding等人[8]在無重疊條件下探索了間隙約束的序列模式挖掘問題;文獻(xiàn)[9]中提出免預(yù)設(shè)間隔約束的對比序列模式高效挖掘算法,解決了序列數(shù)據(jù)挖掘問題;Dong等人[10]在挖掘重復(fù)模式問題上,提出了e-RNSP算法;Tan等人[11]根據(jù)位置的頻繁模式檢測,提出具有弱通配符間隙算法.在上述研究中,均需采用間隙約束模式匹配技術(shù)實現(xiàn)模式支持度的計算,從而判定模式的頻繁性,因此這種間隙約束模式匹配是序列模式挖掘的核心與基礎(chǔ)[12].

當(dāng)前研究主要在非負(fù)間隙下進(jìn)行研究,即aj≥0,但一般間隙約束能得到更多有價值的信息.因此,Fredriksson和Grabowski[13]對一般間隙約束下模式匹配問題進(jìn)行研究,柴等[14]也提出一般間隙及一次性條件的模式匹配問題,并提出了具有完備性的有效算法DNCP;文獻(xiàn)[15]中提到一種基于靈活間隙模式匹配的服務(wù)器,并提出RNAPattMatch算法.與其他多種間隙約束模式匹配相比,無重疊模式匹配具有獨特的計算性能[16],在序列模式挖掘中更容易發(fā)現(xiàn)有價值的頻繁模式[17].

然而精確匹配有時不能完全提供給我們更多有價值的信息.在實際應(yīng)用中大多數(shù)情況屬于近似模式匹配[18].近似模式匹配問題是指在模式串中其中一個字符與序列串中某個字符進(jìn)行匹配時,兩個字符位置相同,但字符可以不完全相同.按照距離計算公式,可將近似條件約束模式匹配分為Hamming距離[19]、δ距離[20,21]及編輯距離[22]等.Hu等人[23]運(yùn)用字符串相似搜索的通用Gram過濾器,提出了GFilter算法.

有鑒于此,本文提出了一般間隙近似無重疊模式匹配問題(Nonoverlapping Approximation Pattern Matching with General Gaps,簡稱NOAPMGG).該問題具有以下4個特點:它是一種嚴(yán)格的近似模式匹配問題,在匹配出現(xiàn)的過程中,不要求模式串上的字符與模式串上的字符完全相同;滿足了無重疊條件約束,允許同一字符在多個位置使用多次,但不允許在同一位置上同一字符使用多次;在模式串的設(shè)定中,允許間隙設(shè)置上出現(xiàn)多個負(fù)間隙.

2 NOAPMGG問題

定義1(序列串).序列串記為S,S=s1…si…sn(1≤i≤n),由字符組成的長度為n的信息源,其中,si∈∑,∑表示為一種符號的集合.在不同應(yīng)用當(dāng)中,∑的意義也會隨之不同.例如,在DNA基因序列中,∑由{A,C,G,T}組合而成.例如,S=s1s2s3s4s5=agcag,序列串S的長度為5.

定義2(模式串).模式串記為P,P=p1[a1,b1]p2…pj[aj,bj]pj+1…[am-1,bm-1]pm(1≤j≤m),其中,m指模式串P的長度,pj∈∑;aj、bj分別指間隙約束的下界與上界且取值必須是整數(shù),并滿足aj≤bj.若aj≥0且bj≥0,則稱此區(qū)間為非負(fù)間隙條件約束;若aj或bj至少有一個小于0,則稱此區(qū)間為一般間隙條件約束.

定義3(出現(xiàn)).出現(xiàn)記為L,如果一個位置索引L=,其中,0≤lj≤n,0≤j≤m,lj≠lj-1,且滿足si=pj且:

(1)

則稱L為模式串P在序列串S上的一個出現(xiàn).例如,模式串P=p1[a1,b1]p2[a2,b2]p3= A[0,3]T[0,2]C,則說明模式串P的長度為3;在字符A和字符T間根據(jù)間隙約束可知,兩個字符間可通配0到3個字符;而字符T和字符C間根據(jù)間隙約束可知,兩個字符間可通配0到2個字符.

定義5(Hamming距離).Hamming距離記為T,即表示兩個(相同長度)字對應(yīng)位不同的數(shù)量.例如:序列串S1=s1s2s3s4s5=abcab與序列串S2=s1s2s3s4s5=acbac,在兩個序列串中,第2、3、5位置字符不同,因此,Hamming距離為3.

3 網(wǎng)樹與NOPARLA算法

3.1 網(wǎng)樹的概念

網(wǎng)樹的數(shù)據(jù)結(jié)構(gòu)是一種樹型結(jié)構(gòu)的拓展,目前被應(yīng)用于解決多種模式匹配問題[24]、序列模式挖掘問題[25]和圖問題[26],其定義如下:

定義6(網(wǎng)樹).網(wǎng)樹是一種非線性數(shù)據(jù)結(jié)構(gòu),是由根結(jié)點與子網(wǎng)樹組成,所有相連的路徑之間用來表示雙親與孩子關(guān)系.

性質(zhì)1.網(wǎng)樹具有樹結(jié)構(gòu)的一些特點,如雙親、孩子、葉子結(jié)點、根結(jié)點、層等.此外,其具有如下獨特特點:

1)一棵網(wǎng)樹中可以存在一個或多個根結(jié)點;

2)網(wǎng)樹中非樹根結(jié)點也會存在多個雙親結(jié)點;

3)任何一個結(jié)點到它的祖先結(jié)點路徑可能不止一條;

4)給定序列中的結(jié)點可以在網(wǎng)樹的不同層上出現(xiàn);

5)一個結(jié)點的孩子結(jié)點一定在網(wǎng)樹的同一層上出現(xiàn).

定義7(樹根葉子路徑).在網(wǎng)樹中,能從樹根結(jié)點到葉子結(jié)點的一條完整的路徑.

定義9(最右雙親策略).從最后一層的最大結(jié)點開始查找,選擇最右雙親結(jié)點向樹根方向?qū)ふ覙涓倪^程.首先判斷最右雙親結(jié)點是否滿足間隙約束條件,若滿足則進(jìn)行匹配,若不滿足則判斷次右雙親結(jié)點,直至找到相匹配的雙親結(jié)點.

定義10(最左孩子策略).從第一層的最小樹根結(jié)點出發(fā),選擇最左孩子結(jié)點向葉子結(jié)點方向?qū)ふ衣窂降倪^程.首先判斷最左孩子結(jié)點是否滿足間隙約束,若滿足則進(jìn)行匹配,若不滿足則判斷次左孩子結(jié)點,直至找到與之相匹配的葉子結(jié)點.

3.2 NOPARLA算法的設(shè)計及分析

3.2.1 創(chuàng)建一般間隙近似網(wǎng)樹

在文獻(xiàn)[16]中,提出利用網(wǎng)樹的結(jié)構(gòu)特點可以有效地解決無重疊條件約束下的模式匹配問題.由于本文研究的是近似距離下的模式匹配問題,因此需要在文獻(xiàn)[16]的創(chuàng)建網(wǎng)樹問題上進(jìn)行一些修改.在修改算法的過程中會存在兩個難點:在處理結(jié)點關(guān)系時,會出現(xiàn)Hamming距離的實時更新;在創(chuàng)建父子關(guān)系前,需要進(jìn)行預(yù)判斷處理.

在創(chuàng)建一般間隙近似網(wǎng)樹前,我們需提到一些與近似距離相關(guān)的定義如下.

1)計算該葉子結(jié)點到根結(jié)點之間的Hamming距離d時樹根到葉子的路徑數(shù);

(2)

1)計算該根結(jié)點到葉子結(jié)點之間的Hamming距離d的路徑數(shù).

(3)

算法1.CreateNetTree

輸入:長度為m的模式串P,長度為n的序列串S,Hamming距離閾值T

輸出:網(wǎng)樹NetTree

1.forj=1 tomstep 1do

2.fori=1 tonstep 1do

3. 依據(jù)定義11創(chuàng)建并計算結(jié)點的NHDRL值;

4.endfor

5.endfor

6.returnNetTree;

例1.給定序列串S=tgttagt,模式串P= t[-1,1]t[-1,2]a[-1,1]t,Hamming距離為1,根據(jù)CreateNetTree算法可以建立一棵近似網(wǎng)樹,如圖1所示.

該網(wǎng)樹的創(chuàng)建步驟如下:

1)當(dāng)j=1時,將序列串中所有字符一次掃描插入第一層nettree[1],根據(jù)定義13,對所有結(jié)點進(jìn)行初始值定義;

圖1 模式串P在序列串S對應(yīng)的網(wǎng)樹Fig.1 Nettree for pattern P in sequence S

3.2.2 最左孩子策略

為解決近似距離閾值問題,在創(chuàng)建一般間隙近似網(wǎng)樹為每個結(jié)點都進(jìn)行了在不同Hamming距離下路徑數(shù)量的定義與計算.若滿足近似度閾值條件,則根據(jù)樹根葉子路徑數(shù)匹配該結(jié)點的孩子結(jié)點.該方法可以有效提高匹配效率,具體過程如下:從最小根結(jié)點出發(fā),根據(jù)間隙約束條件與Hamming距離的設(shè)定,當(dāng)上一層結(jié)點與下一層結(jié)點建立關(guān)系時,根據(jù)公式(2)選擇與之匹配的最小孩子結(jié)點.其算法如算法2.

算法2.RootToLeaf

輸入:NetTree,模式串P長度為m,序列串S長度為n,閾值T,當(dāng)前結(jié)點F

輸出:occin,各層結(jié)點F[m]集合

1.occin.position[1]=t;

2.F[1]=nettree[1][t];

3.ifF[1].used=true orF[1].toleave=falsethen

4.ifp[1].start≠s[F[1]]thenapprox=1;

5.forj=1 tomstep 1do

6.fort=1 tonettree[j][i].children.size()step 1do

7.maxh=T-approx;

8.endfor

9.ifnettree[j][child].toleave=false thenapprox=

approx+1;

10.endfor

11.endif

12.returnoccinandF[m];

3.2.3 近似閾值監(jiān)測機(jī)制

根據(jù)文獻(xiàn)[17]可知,基于從最小根結(jié)點向下采用最左孩子結(jié)點找到較多的樹根葉子路徑,若模式串P的間隙約束略大或間隙條件過多時,結(jié)點的孩子結(jié)點也會成倍增加,由于近似度閾值的約束會造成該結(jié)點選擇的孩子結(jié)點并不是最小孩子結(jié)點,因此僅依靠最左孩子策略并不能找到更多的出現(xiàn),由此可見需要引入近似閾值檢測機(jī)制.具體過程如下:從網(wǎng)樹的第二層開始,若第一次檢測到si=pj,且該結(jié)點在Hamming距離0～T-1時有路徑,則重新向上根據(jù)最左雙親策略尋找與之匹配的結(jié)點.其算法如算法3.

算法3.RootToLeaf_Approx

輸入:NetTree,模式串P(長度:m),序列串S(長度:n),閾值T,當(dāng)前結(jié)點Q

輸出:occin,各層結(jié)點Q[t]集合

1.forj=1 tomstep 1do

2.if(j≤m)then

3. 采用算法2,從結(jié)點Q[t]出發(fā),采用最左孩子策略,獲得子路徑Q及對應(yīng)的Hamming距離為approx的子模式;

4.forx=jdownto 2 step-1do

5.fory=1 toNetTree[x][y].parents.size()step 1do

6.maxh=T-approx;

7.endfor

8.ifNetTree[x][child].toleave=falsethenapprox=approx+1;

9.endfor

10.endif

11.endfor

12.returnoccinandQ[t];

3.2.4 剪枝策略

定理1.若同一網(wǎng)樹中有互不相交的兩條路徑分別為A、B,則A、B經(jīng)過的路徑上所有結(jié)點可構(gòu)成兩個無重疊出現(xiàn).

由定理1可知,同一棵網(wǎng)樹中有兩條互不相交的兩條路徑,可構(gòu)成兩個無重疊出現(xiàn).因此,根據(jù)最左孩子策略,在網(wǎng)樹上剪掉一條樹根葉子路徑后,并不會影響尋找其他的無重疊出現(xiàn).但在進(jìn)行剪枝后會出現(xiàn)一些不能到達(dá)葉子結(jié)點的結(jié)點,只需從葉子到樹根逐層檢測,將不可抵達(dá)葉子結(jié)點的結(jié)點進(jìn)行剪枝,這樣可避免回溯過程.其算法如算法4.

算法4.Pruning

輸入:NetTree,模式串P的長度m,occin

輸出:NetTree

1.fori=mdownto 1 step-1do

2.position=occin.position[i];

3.ifi

4.pos=occin.position[i+1];

5.position_b=NetTree[m+1][pos].parent[0];

6.ifposition_b

7.endif

8.forposition=1 toNetTree[i].size()step 1do

9.current=NetTree[i][position];

10.ifcurrent.used=false ¤t.child=false

thenbreak;

11. updatecurrent.used;

12.ifcurrent.used=truethenupdate NHDRL;

13.endif

14.endfor

15.endfor

16.returnNetTree;

3.2.5 求解算法NOPARLA算法

根據(jù)本文提出的問題,NOPARLA算法將作為求解算法.該算法原理:

1)根據(jù)算法1將問題轉(zhuǎn)化成一棵網(wǎng)樹并根據(jù)性質(zhì)11和公式(2)對結(jié)點進(jìn)行NHDRL值定義;

2)從下往上根據(jù)性質(zhì)12和公式(3)對結(jié)點進(jìn)行NHDLR值定義;

3)采用算法3進(jìn)行最左孩子策略和近似監(jiān)測機(jī)制;

4)當(dāng)找到一個無重疊出現(xiàn)時,采用算法4將網(wǎng)樹進(jìn)行剪枝;

5)重復(fù)第3、4步,直至找到所有無重疊出現(xiàn).

其算法如算法5:

算法5.NOPARLA

輸入:長度為m的模式串P,長度為n的序列串S,閾值T

輸出:符合條件的無重疊出現(xiàn)集合C

1. 采用算法1創(chuàng)建一棵近似網(wǎng)樹NetTree;

2.forj=m-1 downto 1 step-1do

3.fori=1 tonstep 1do

4. update NHDLR;

5.endfor

6.endfor

7.fort=1 toNetTree[1].size()step 1do

8. 采用算法3 RootToLeaf_Approx(N,Q[t]),從結(jié)點Q出發(fā),采用最左孩子策略;

9. 采用算法4 Pruning更新NetTree;

10.C=Q∪occin;

11.endfor

12.returnC;

例2.給定序列串S=tgttagt和模式串P= t[-1,1]t[-1,1]a[-1,2]t,Hamming距離為1.

計算過程如下:

1)模式串P在序列串S中所建立的對應(yīng)網(wǎng)樹,如圖1所示.

2)根據(jù)公式(3)對網(wǎng)樹重新定義NHDLR值.

根據(jù)NOPARLA算法,可以找到三個無重疊出現(xiàn),即<1,3,2,1>、<3,4,3,4>、<4,6,5,7>.

3.3 算法分析

由于網(wǎng)樹最多只有m層,每一層結(jié)點數(shù)最多只有n個結(jié)點,由此可見,每一個孩子結(jié)點最多會有W個雙親結(jié)點,即W=max(bj-aj+1),且aj為間隙約束的下界,bj為間隙約束的上界,近似閾值為T.因此,NOPARLA算法的空間復(fù)雜度為O(m*n*W*T).其中,m為模式串的長度,n為序列串的長度,W為模式串的最大間隙長度W=max(bj-aj+1),T為近似閾值.

在分析本文算法時間復(fù)雜度之前,先分析CreateNetTree算法、RootToLeaf算法、RootToLeaf_Approx算法以及Pruning算法的時間復(fù)雜度.易知CreateNetTree算法創(chuàng)建一棵一般間隙近似網(wǎng)樹的時間復(fù)雜度為O(m*n*W*T);在RootToLeaf算法中,每個結(jié)點最多有W個孩子結(jié)點,網(wǎng)樹共有m層,近似閾值為T,所以RootToLeaf算法的時間復(fù)雜度為O(m*W*T);RootToLeaf_Approx算法的時間復(fù)雜度為O(m2*W*T);根據(jù)Pruning算法可知,該算法的時間復(fù)雜度為O(m3*W*T).由于NOPARLA算法最多運(yùn)行n-m次剪枝算法,由此本文算法的時間復(fù)雜度為O(m3*n*W*T).

4 實驗結(jié)果及分析

4.1 實驗環(huán)境及實驗數(shù)據(jù)

本文中實驗運(yùn)行的軟、硬件環(huán)境為:Inter(R)Core(TM)i5-3210處理器、2.50GHz主頻、4.00GB內(nèi)存、Windows8.1 專業(yè)版操作系統(tǒng)的計算機(jī).完成實驗工具為Microsoft Visual C++6.0.本文所使用的測試序列串均為真實的生物數(shù)據(jù),DNA序列均來自美國國家生物計算信息中心網(wǎng)站1.為體現(xiàn)模式串的間隙約束具有一般性規(guī)律,在本文中設(shè)計了九個具有一般性的模式串. 表1和表2分別給出了實驗中使用的序列串和模式串的特征.

表1 真實生物序列
Table 1 Sequences of real biological data

序號片段名稱位點片段長度S1Segment 1CY0585632286S2Segment 2CY0585622299S3Segment 3CY0585612169S4Segment 4CY0585561720S5Segment 5CY0585591516S6Segment 6CY0585581418S7Segment 7CY058557982S8Segment 8CY058560844

4.2 實驗結(jié)果

為了測試本文NOPARLA算法的性能,我們又提出了三種對比算法,即NOPALR算法、NOPARL算法和NOPALRA算法.這三種對比算法均采用網(wǎng)樹結(jié)構(gòu)進(jìn)行求解,其中NOPALR算法采用最右雙親策略,當(dāng)找到一個無重疊出現(xiàn)時將網(wǎng)樹進(jìn)行剪枝;NOPARL算法采用最左孩子策略,當(dāng)找到一個無重疊出現(xiàn)時將網(wǎng)樹進(jìn)行剪枝;NOPALRA算法采用最右雙親策略,再采用近似閾值檢測,當(dāng)找到一個無重疊出現(xiàn)時將網(wǎng)樹進(jìn)行剪枝.

本文選取表2中P1～P9中的9個模式串與表1中S1～S8中的8個序列串作為本文的對比實驗數(shù)據(jù),在選取近似閾值T=1與T=2進(jìn)行對比實驗,并對這四種算法的求解質(zhì)量與求解速度進(jìn)行對比.表3和表4分別給出了近似閾值T=1與T=2情況下,模式串P1～P9在序列串S1～S8上的出現(xiàn)總數(shù).

表2 模式串
Table 2 Patterns

表3T=1時,序列S1～S8在模式P1～P9上的出現(xiàn)總數(shù)
Table 3 Total results ofS1～S8 inP1～P9 whenT=1

出現(xiàn)數(shù)P1P2P3P4P5P6P7P8P9NOPALR341045303193255514581725123027493199NOPARL353244143452268818821905161629303218NOPARLA351843573382273016791882140030943450NOPARLA360345563445265819722016169331473508

表4T=2時,序列S1～S8在模式P1～P9上的出現(xiàn)總數(shù)
Table 4 Total results ofS1～S8 inP1～P9 whenT=2

出現(xiàn)數(shù)P1P2P3P4P5P6P7P8P9NOPALR6468100866216499126192500211843604469NOPARL6575101236389533826012524227143604445NOPARLA6438101126220520427662713226846684828NOPARLA6664101976442508727882753240548044971

為了能更清晰的反映出四種算法分別在近似閾值T=1與T=2情況下,模式串P1～P9在序列串S1～S8上的時間性能,四種算法的平均運(yùn)行時間見表5和表6.

4.3 實驗結(jié)果分析

1)在求解性能方面,NOPARLA算法整體比NOPARL算法、NOPALR算法與NOPALRA算法較好.

通過表3～表4,即T=1和T=2時,序列串S1～S8在模式P1～P9上的出現(xiàn)總數(shù).從兩張表中,清晰看出NOPARLA算法從總體來說,求解性能優(yōu)于其他三種算法.在模式串P3上,NOPARL算法求解性能優(yōu)于NOPARLA算法;在模式串P4上,NOPALRA算法與NOPARLA算法均沒有NOPARL算法的求解性能好;產(chǎn)生這樣的原因一是由于序列串的長短會造成這樣的原因,由于在NOPARL算法與NOPALR算法并沒有判斷近似監(jiān)測機(jī)制,因此,對網(wǎng)樹造成較小的影響;二是因為當(dāng)序列串足夠長的時候,為了能找到能多有價值的出現(xiàn),算法對近似距離做檢測,當(dāng)滿足一定條件時,會觸發(fā)近似監(jiān)測機(jī)制,使得產(chǎn)生的新無重疊出現(xiàn)比原有無重疊出現(xiàn)對網(wǎng)樹的影響減小,因而提高了算法的求解性能.

表5T=1時,序列S1～S8在模式P1～P9上的平均運(yùn)行時間
Table 5 Average running time ofS1～S8 inP1～P9 whenT=1

平均時間P1P2P3P4P5P6P7P8P9NOPALR4392844394141164171714579301424NOPARL52235052548814332145176711331660NOPARLA50634052548613522029168410781625NOPARLA53937354351014812271183411491735

表6T=2時,序列S1～S8在模式P1～P9上的平均運(yùn)行時間
Table 6 Average running time ofS1～S8 inP1～P9 whenT=2

平均時間P1P2P3P4P5P6P7P8P9NOPALR74041277955128116184369120244986NOPARL83846790877731316840409422405250NOPARLA77143880361130686908410222425521NOPARLA86449493477232747387429523855855

2)在求解性能方面,通常情況下NOPARLA算法比NOPALRA算法可以發(fā)現(xiàn)更多的出現(xiàn).

從表3～表4可以看出,在模式串P1～P9上,當(dāng)T=1時,NOPARLA算法有七次獲得了最多出現(xiàn)數(shù),當(dāng)T=2時,NOPARLA算法有八次獲得了最多出現(xiàn)數(shù).

3)在時間運(yùn)行方面,改進(jìn)后的NOPARLA算法與NOPALRA算法運(yùn)行時間總體比未改進(jìn)的NOPARL算法與NOPALR算法較長.

從表5～表6可以看出,即T=1和T=2時,序列串S1～S8在模式P1～P9上的平均運(yùn)行時間下,NOPARLA算法在運(yùn)行時間上總體來說消耗最多,NOPALR算法消耗的時間最少,并且可以看出NOPARLA算法與NOPALRA算法消耗的時間,從整體來說均比NOPARL算法與NOPALR算法時間長,造成這種現(xiàn)象別的主要原因是在處理無重疊出現(xiàn)時,對近似距離做檢測,通過檢測可以找到更多有價值的出現(xiàn),因此會增加時間的運(yùn)行.

4)隨著近似閾值T的增加,找到的出現(xiàn)數(shù)與運(yùn)行時間也會隨之增加.

通過表3～表4,即T=1和T=2時,序列串S1～S8在模式P1～P9上的出現(xiàn)總數(shù).換言之,當(dāng)T從0到2逐漸增大時,出現(xiàn)數(shù)也會隨之增加,產(chǎn)生這樣現(xiàn)象的原因是由于近似閾值T可轉(zhuǎn)換為近似距離為T-approx及近似距離為approx問題.從表5～表6可以看出,即T=1、T=2時,序列串S1～S8在模式串P1～P9上的平均運(yùn)行時間也會隨之增加,這與上一章中提高的算法時間復(fù)雜度與空間復(fù)雜度分析一致.

通過本章做的大量實驗進(jìn)行分析可知,與其他3種算法相比,NOPARLA算法從整體來說性能最好.

5 結(jié) 論

本文提出了一般間隙近似無重疊模式匹配問題,即NOAPMGG問題.該問題需要滿足無重疊模式的條件約束,為增加模式串的一般性而提出近似模式匹配,為進(jìn)一步增加模式串的靈活性而提出一般間隙模式匹配問題,來解決NOAPMGG問題.本文提出NOPARLA算法,該算法根據(jù)網(wǎng)樹的結(jié)構(gòu)特點,采用最左孩子策略,使用近似閾值機(jī)制找到一個無重疊出現(xiàn).該算法的空間復(fù)雜度與時間復(fù)雜度分別為O(m*n*W*T)和O(m3*n*W*T),其中m為模式串的長度,n為序列串的長度,W為模式串的最大間隙長度,T為近似閾值.通過大量實驗證明了,NOPARLA算法具有較高的可行性與高效性.