柴 欣,王建姣,閆文杰,武優(yōu)西

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

1 引 言

模式匹配作為計(jì)算機(jī)科學(xué)研究中的核心問題,一直備受研究學(xué)者的關(guān)注[1].目前,模式匹配問題已深入到生物信息學(xué)[2]、半結(jié)構(gòu)化數(shù)據(jù)查詢[3]、問答系統(tǒng)[4],特別是模式挖掘[5-7]等諸多領(lǐng)域中,并扮演著十分重要的角色.Fischer et al.最早研究了帶固定通配符的模式匹配問題[8];Aho-Corasick et al.為了避免通配符個(gè)數(shù)設(shè)定不合理[9],將Fischer et al.提出的KMP算法進(jìn)行擴(kuò)展,使其可以處理帶可變通配符的模式匹配問題,研究學(xué)者把這種具有通配符的模式匹配問題稱為間隙約束[10],這種具有間隙約束的模式匹配[11]不僅在生物信息學(xué)方面具有重要應(yīng)用,而且還是間隙約束序列模式挖掘[12-14]的核心與基礎(chǔ),因?yàn)槠淇梢杂米髂Ｊ街С侄萚13]的計(jì)算,進(jìn)而判斷模式的頻繁性[15].間隙約束下的模式匹配[11]不但更難求解,而且存在以下三種形式:無特殊條件,一次性條件[12]和無重疊條件[16,17].在間隙約束的序列模式挖掘中亦存在上述三種形式的挖掘形式.由于無特殊條件的挖掘算法可能挖掘出大量的冗余模式,從而造成效率降低;Wu et al.的提出的是一次性條件[12]的挖掘算法,由于計(jì)算一次性條件下,計(jì)算一個(gè)模式在序列中的支持度是一個(gè)NP問題,因此基于一次性條件的模式匹配很可能會(huì)丟失一些用戶感興趣的模式;Ding et al.最早提出了無重疊條件[16]的概念,在避免冗余的前提下使得求得的解更符合用戶需求,但是該挖掘方法是不完備的.Wu et al.近期提出了滿足Apriori性質(zhì)的完備性挖掘算法NOSEP算法[13],有效地解決無重疊條件序列模式挖掘問題.正如前面所述,無重疊條件序列模式挖掘的基礎(chǔ)是無重疊條件的模式匹配,Wu et al.理論證明了無重疊條件模式匹配是一個(gè)多項(xiàng)式時(shí)間內(nèi)可解的問題,并提出了完備性的NETLAP-Best[18]算法.下面舉例說明一下無重疊條件模式匹配中出現(xiàn)的計(jì)算方法.

例1.給定模式P=p1[0,2]p2[0,2]p3=A[0,2]A[0,2]C和序列S=s1s2s3s4s5=AAACC

子模式A[0,2]C的含義是:在字符A和字符C之間可以通配0到2個(gè)字符.若p2=si,p3=sj,且0≤j-i+1≤2,則表示位置為i的字符A和位置為j的字符C滿足間隙約束.

例1中滿足間隙約束的所有出現(xiàn)為{<1,2,4>,<1,2,5>,<1,3,4>,<1,3,5>,<2,3,4>,<2,3,5>},一次性條件約束規(guī)定序列中任意位置字符只能在所有出現(xiàn)中最多使用一次,因此滿足一次性條件的最大出現(xiàn)數(shù)為1,可以是6個(gè)出現(xiàn)中的任意一個(gè).無重疊約束允許序列中任意位置字符多次出現(xiàn),但是不允許任意兩個(gè)出現(xiàn)中同一位置字符相同,如<1,2,4>和<2,3,4>就不滿足無重疊條件,因?yàn)槠湓谕晃恢霉灿昧?,因此滿足無重疊約束的最大出現(xiàn)數(shù)為2,分別是<1,2,4>和<2,3,5>,盡管2 同時(shí)存在于兩個(gè)出現(xiàn)中,但處于不同的位置,所以滿足無重疊約束.

盡管間隙約束序列模式挖掘可通過設(shè)定間隙約束[19,20],以便滿足用戶的特定需要,但對于無先驗(yàn)知識的挖掘情況而言,如何設(shè)定間隙是難以解決的問題,而間隙約束序列模式挖掘的核心問題之一是模式匹配[21-23].為此本文研究在不考慮間隙約束的情況下計(jì)算無重疊條件下模式匹配問題.

本文貢獻(xiàn)如下:

1)提出了無間隙約束下的無重疊條件的模式匹配問題,該問題具有兩個(gè)重要特征,一是采用無重疊的方式計(jì)算出現(xiàn)的個(gè)數(shù);二是無需給定模式的間隙,計(jì)算該模式在特定序列中最大出現(xiàn)數(shù).

2)設(shè)計(jì)了一種高效的在線匹配算法SNGP-Best,該算法通過計(jì)算模式的長度來確立隊(duì)列的個(gè)數(shù),然后采用在線計(jì)算的方式進(jìn)行求解.

3)進(jìn)行對比性實(shí)驗(yàn),驗(yàn)證本文算法的正確性和高效性.

本文的組織結(jié)構(gòu)如下:第2節(jié)給出了模式匹配的問題定義;第3節(jié)詳細(xì)地描述算法SNGP-Best;第4節(jié)給出在數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果,并對該結(jié)果進(jìn)行分析;第5節(jié)得出本文的結(jié)論.

2 問題定義

定義1.給定序列S=s1s2s3…sn,這里的n表示序列S的長度,sj∈∑(1≤j≤n)代表一種符號集,對于不同的應(yīng)用,S可以是不同的符號集合,用|∑|來表示S中不同字符的數(shù)量.

例2.截取基因序列片段S=s1s2s3s4s5s6s7s8s9=acggcaggt,其中序列S的長度為9,S由{a,c,g,t}構(gòu)成,|∑|的值為4.

定義2.無間隙約束的模式串P可以表示為p1p2p3…pm,這里m表示模式串P的長度,pi∈∑(1≤i≤m),這里允許pi和p(i+1)之間可以匹配通配符數(shù)量為非負(fù)值.在例2中,給定模式P=agg.當(dāng)s3=g與p2成功匹配時(shí),s4=g可以與p3進(jìn)行匹配,s7、s8也可以與p3進(jìn)行匹配.

定義3.若存在一個(gè)位置索引序列I=,滿足slj=pi和ij>i(j+1),其中1≤j≤m且 1≤i≤n,則稱I是P在S中的一個(gè)出現(xiàn).

定義4.給定模式P在序列S中的兩個(gè)出現(xiàn),其分別是:I1=、I2=,滿足ik≠jk(1≤k≤m),則稱I1、I2是兩個(gè)滿足無重疊條件的出現(xiàn).

例3.給定序列S=s1s2s3s4s5=cgcgc,模式P=p1p2p3=cgc,則出現(xiàn)<1,2,3>和<3,4,5>即為滿足無重疊性質(zhì)的兩個(gè)出現(xiàn),雖然位置3被重復(fù)使用,但卻不是在模式的同一位置被使用;而<1,2,3>和<1,4,5>則不滿足無重疊出現(xiàn),因?yàn)樗鼈児蚕砹宋恢?.

定義5.集合N(S,P)表示模式P在序列S中的所有出現(xiàn),其長度用|N(S,P)|來表示.

定義6.標(biāo)志位flag有T和F 兩個(gè)值,作為判定能否在隊(duì)列i創(chuàng)建結(jié)點(diǎn)的條件之一,隊(duì)列1默認(rèn)為T,除隊(duì)列1外,當(dāng)隊(duì)列i和隊(duì)列(i-1)滿足numi

定義7.給定兩個(gè)模式P和P′,若模式P所包含的字符都存在于模式P′中,則稱P是P′的子模式,P′是P的超模式.例模式P=CAA,P′=CATA,因?yàn)镻包含于P′,則P是P′的子模式,P′是P的超模式.

為了便于理解,表1給出了本文重要符號的描述.

表1 本文主要符號的描述
Table 1 Description of the main symbols in this paper

符號描述S表示序列,由n個(gè)字符s1s2s3…sn構(gòu)成P表示模式,由m個(gè)字符p1p2p3…pm構(gòu)成nij表示隊(duì)列j的第i個(gè)結(jié)點(diǎn)N(S,P)表示模式P在序列S中的所有無重疊出現(xiàn)的集合|N(S,P)|表示N(S,P)的長度flag標(biāo)志位,有T和F兩個(gè)值

3 求解算法及分析

3.1 求解算法

算法1.SNGP-Best

輸入:模式P和序列S

輸出:無重疊出現(xiàn)集C

1:fori=1 toP的長度 step 1do

2: 根據(jù)P[i]創(chuàng)建隊(duì)列i;

3:endfor

4:forj=1 toS的長度 step 1do

5:Bool_Pattern= B_Pattern(); //調(diào)用算法B_Pattern()判定各個(gè)隊(duì)列的標(biāo)志位

6:fori=1 toP的長度 step 1do

7:if(Bool_Pattern[i] ==true)and(S[j]==P[i])then

8: 隊(duì)列i.push(S[j]); //將S[j]放入隊(duì)列i中

9:endif

10:if(最后一個(gè)隊(duì)列不為空)then

11: 每個(gè)隊(duì)列的頭結(jié)點(diǎn)出隊(duì),組成一個(gè)出現(xiàn)occ;

12:C=C∪occ;

13:endif

14:endfor

15:endfor

16:returnC

由于算法1中需要通過各個(gè)隊(duì)列的標(biāo)志位來判斷是否可以創(chuàng)建結(jié)點(diǎn),因此,算法2建立判別數(shù)組來判定各個(gè)隊(duì)列的標(biāo)志位的值,如下.

算法2.B_Pattern

輸入:全部隊(duì)列P

輸出:判別數(shù)組Bool_Pattern

1:fori=1 toP的長度 step 1do

2:if(i==1)then

3:Bool_Pattern[i] =true;

4:elseif(隊(duì)列(i-1]的結(jié)點(diǎn)數(shù)>隊(duì)列i的結(jié)點(diǎn)數(shù))then

5:Bool_Pattern[i] =true;

6:endif

7:endfor

8:returnBool_Pattern

3.2 運(yùn)行實(shí)例

例4.給定序列S=s1s2s3s4s5s6s7s8s9s10s11=acggaaccgac,模式P=p1p2p3p4=agac.計(jì)算N(S,P)和|N(S,P)|.

由P=p1p2p3p4=agac得知,模式P中的字符數(shù)量為4,建立4個(gè)隊(duì)列,并由s1=a開始讀入,順序進(jìn)行匹配,結(jié)果如圖1所示.圖1中,第一列灰色填充的圓圈代表第一組出現(xiàn)I1=<1,3,5,7>,第二列灰色填充的圓圈代表第二組出現(xiàn)I2=<5,9,10,11>,第三列、第四列未填充的白色圓圈代表尚未匹配成功的結(jié)點(diǎn),淺灰色的虛線框代表已將該出現(xiàn)從隊(duì)列中輸出.此外,第一個(gè)矩形框代表標(biāo)志位,若為T且與si匹配成功,則創(chuàng)建結(jié)點(diǎn)成功,若為F,則創(chuàng)建結(jié)點(diǎn)失敗,第二個(gè)矩形框代表模式P中的各個(gè)字符,第三個(gè)矩形框代表該隊(duì)列中的結(jié)點(diǎn)數(shù)目.

圖1 P在S上的出現(xiàn)Fig.1 Occurrences of P in S

序列中其他位置字符的匹配過程與此相同,不再贅述.

故N(S,P)={<1,3,5,7>,<5,9,10,11>},|N(S,P)|=2.

3.3 算法復(fù)雜度分析

假設(shè)序列S的長度為n,模式P的長度為m,模式P的首字符在序列S的出現(xiàn)次數(shù)為Len.易知,SNGP-Best算法在最壞的情況下空間復(fù)雜度為O(m*Len).這是因?yàn)楣步⒘薽個(gè)隊(duì)列,每個(gè)隊(duì)列的結(jié)點(diǎn)個(gè)數(shù)最多為Len,若不存在出現(xiàn),則創(chuàng)建成功的結(jié)點(diǎn)都存在于隊(duì)列中,此時(shí)的空間復(fù)雜度為O(m*Len).

SNGP-Best 算法的時(shí)間復(fù)雜度分析如下:根據(jù)模式P的長度確定隊(duì)列的個(gè)數(shù),時(shí)間復(fù)雜度O(m),然后從左到右順序讀取序列S中的n個(gè)字符,逐一與模式P中的m個(gè)字符進(jìn)行匹配,故時(shí)間復(fù)雜度為O(n*m).綜上可知,SNGP-Best的時(shí)間復(fù)雜度為O(n*m)+ O(m).

4 實(shí)驗(yàn)結(jié)果及分析

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

本節(jié)采用真實(shí)的DNA序列進(jìn)行實(shí)驗(yàn),驗(yàn)證算法SNGP-Best算法在以下兩個(gè)方面的性能,其分別是:1)提出的算法SNGP-Best是否可以求得完備解;2)算法的時(shí)間性能.

在實(shí)驗(yàn)過程中采用的對比算法有以下3個(gè):INSNGP、NETNGP和SNGP-Slow,其中INSNGP是將INSgrow算法[15]中的間隙約束進(jìn)行擴(kuò)張,使其可以處理無間隙約束下的模式匹配問題;NETNGP是將NETLAP-Best算法[16]中的間隙約束處理方式進(jìn)行修改,對最小和最大間隙不加限制,使其可以在滿足無重疊條件的前提下處理不受間隙約束的模式;為了驗(yàn)證SNGP-Best算法的完備性和高效性,本文設(shè)計(jì)了SNGP-Slow算法進(jìn)行對比,SNGP-Slow算法同SNGP-Best算法類似,都采用隊(duì)列存儲(chǔ)結(jié)點(diǎn),但SNGP-Slow算法將SNGP-Best算法的第5行和第6行進(jìn)行了互換,因此在處理序列串中的字符與模式串中多個(gè)字符匹配的情況時(shí),需要多次判斷結(jié)點(diǎn)的數(shù)目,一定程度上造成了時(shí)間的增加;另外,SNGP-Slow算法將 B_Pattern算法的第4行前增加了判斷,判斷pi與p(i-1)是否相同,若相同,隊(duì)列(i-1]的結(jié)點(diǎn)數(shù)-1 > 隊(duì)列i的結(jié)點(diǎn)數(shù),隊(duì)列i標(biāo)志位為T,否則,為F;若不同,繼續(xù)執(zhí)行第4行,因此,當(dāng)相同字符相鄰時(shí),由于出現(xiàn)中的字符規(guī)定為非負(fù)間隙,因此會(huì)造成丟解的問題.例如,序列S=CAAAT,模式P=CAAT.滿足無重疊的出現(xiàn)為<1,2,3,5>或<1,2,4,5>或<1,3,4,5>,但SNGP-Slow算法找到的無重疊出現(xiàn)為0,因?yàn)镻中的第2個(gè)字符和第3個(gè)字符相同為A,因此隊(duì)列3的結(jié)點(diǎn)數(shù)小于隊(duì)列2的結(jié)點(diǎn)數(shù)減1才可以創(chuàng)建結(jié)點(diǎn),因此,當(dāng)隊(duì)列1創(chuàng)建了結(jié)點(diǎn)1,隊(duì)列2創(chuàng)建的結(jié)點(diǎn)2后,隊(duì)列3始終不滿足創(chuàng)建結(jié)點(diǎn)的條件,因此造成了丟解的問題.

實(shí)驗(yàn)運(yùn)行的操作系統(tǒng)為windows 8.1,實(shí)驗(yàn)所使用的工具為Microsoft Visual C++6.0,處理器為Inter(R)Core(TM)i5-5200,處理器為2.20GHZ,2.20GHZ,安裝內(nèi)存為4.00GB.本文選用了8個(gè)中等長度的基因序列串作為實(shí)驗(yàn)序列,這些真實(shí)的DNA序列可以從美國國家生物計(jì)算信息中心進(jìn)行下載[注]http://www.ncbi.nlm.nih.gov.

表2給定了8個(gè)實(shí)驗(yàn)序列的基本特征.

為了驗(yàn)證算法SNGP-Best的求解性能,我們選取表3中9種不同長度的模式串進(jìn)行實(shí)驗(yàn).

表2 真實(shí)生物數(shù)據(jù)片段
Table 2 Real biological data fragment

序號片段名稱位點(diǎn)片段的長度S1Segment1CY0585622299S2Segment2CY0585612286S3Segment3CY0585612169S4Segment4CY0585561720S5Segment5CY0585591516S6Segment6CY0585581418S7Segment7CY058557982S8Segment8CY058560844

其中模式串之間的關(guān)系為:P(i-1)是Pi的子模式,而Pi是P(i-1)的超模式.

表3 模式
Table 3 Pattern

序號模式串長度P1acat4P2acatt5P3aacatt6P4gaacatt7P5ggaacatt8P6ggaacattt9P7cggaacattt10P8ccggaacattt11P9cccggaacattt12

4.2 DNA序列的實(shí)驗(yàn)結(jié)果

4.2.1 正確性分析

為了驗(yàn)證本文所提出的解決無間隙約束下無重疊的模式匹配的在線算法SNGP-Best解的正確性以及求解的性能,本文將SNGP-Best與其他三種對比性算法進(jìn)行了對比,并將9個(gè)模式在8個(gè)序列上的出現(xiàn)進(jìn)行求和,如圖2所示.

圖2 匹配結(jié)果Fig.2 Results of matching

由上述實(shí)驗(yàn)結(jié)果可以得到如下結(jié)論:

1)NETNGP、SNGP-Best兩個(gè)算法是完備的,INSNGP 、SNGP-Slow兩個(gè)算法是不完備的.在圖2中,NETNGP和SNGP-Best算法的結(jié)果相同,且大于或等于INSNGP 、SNGP-Slow兩個(gè)算法的出現(xiàn),例如,模式P8在8個(gè)序列上的匹配結(jié)果顯示,NETNGP和SNGP-Best算法的出現(xiàn)數(shù)都為2349,而SNGP-Slow和INSNGP 的出現(xiàn)數(shù)分別為2330和710,因此在生物序列上的這些實(shí)驗(yàn)驗(yàn)證了NETNGP、SNGP-Best兩個(gè)算法求解的正確性,同時(shí)了也驗(yàn)證了算法INSNGP 與SNGP-Slow的不完備性.

2)由于INSNGP和SNGP-Slow兩個(gè)算法都會(huì)出現(xiàn)丟解的問題,因此算法 INSNGP和SNGP-Slow均是不完備性算法.盡管如此,SNGP-Slow算法的解的質(zhì)量優(yōu)于INSNGP算法.主要是因?yàn)?INSNGP 算法是從樹根層開始向下尋找出現(xiàn),但是樹根層中很多根結(jié)點(diǎn)是不可以抵達(dá)葉子結(jié)點(diǎn)的,因此會(huì)對一些樹根產(chǎn)生錯(cuò)誤判定.而SNGP-Slow 算法則采用隊(duì)列的形式存儲(chǔ)結(jié)點(diǎn),優(yōu)先選擇最先出現(xiàn)的結(jié)點(diǎn)構(gòu)成滿足條件的結(jié)點(diǎn),雖然在相鄰字符相同的情況下會(huì)出現(xiàn)結(jié)點(diǎn)誤判的風(fēng)險(xiǎn),從而造成丟解,但丟掉的解的數(shù)量是比較少的.例如圖2,模式P6在8個(gè)序列上的匹配結(jié)果顯示,SNGP-Slow和INSNGP的結(jié)果分別為2415和906,因此上述實(shí)驗(yàn)驗(yàn)證了算法SNGP-Slow優(yōu)于INSNGP算法的解的質(zhì)量.

3)INSNGP、NETNGP 、SNGP-Slow、SNGP-Best算法在同一系列集中,P1-P9的模式長度以公差為1的速度增長,且模式間存在Pi是P(i-1)的超模式的關(guān)系.匹配結(jié)果表明,隨著模式長度的增加,出現(xiàn)個(gè)數(shù)大致呈降低趨勢,偶爾有相同的現(xiàn)象,以SNGP-Best為例,P1-P9在8個(gè)序列上的結(jié)果分別為:2511,2505,2501,2437,2429,2423,2355,2349和2342,主要因?yàn)榻o定序列的長度是固定的,要在序列中提取特定的模式,因此長度越長,提取的模式越少.同樣的,就同一模式而言,隨著序列長度依次增長,產(chǎn)生的出現(xiàn)大致呈逐漸減少的趨勢,主要因?yàn)榻o定的模式是固定的,在序列中尋找模式,通常而言,序列越長,尋找到的模式數(shù)量越多.

4.2.2 模式匹配算法的時(shí)間性能

本節(jié)主要對比了INSNGP、NETNGP 、SNGP-Slow、SNGP-Best四個(gè)算法的時(shí)間性能,考慮了模式長度和序列長度兩個(gè)因素進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)序列和模式分別是表2和表3中的數(shù)據(jù),分別求上面幾個(gè)算法的運(yùn)行時(shí)間,每個(gè)模式在同一序列上運(yùn)行50次,實(shí)驗(yàn)結(jié)果采用運(yùn)用公式(1)求取平均值,并將每個(gè)模式在8個(gè)序列上的運(yùn)行時(shí)間求和,結(jié)果如圖3所示.

(1)

其中,maxi、mini分別代表最長、最短的運(yùn)行時(shí)間,k代表試驗(yàn)次數(shù),k=50.

圖3 運(yùn)行時(shí)間結(jié)果Fig.3 Results of running times

根據(jù)圖3的運(yùn)行結(jié)果,我們可以得到以下幾點(diǎn)結(jié)論:

1)SNGP-Best算法求解速度遠(yuǎn)遠(yuǎn)快于NETNGP算法.圖3中,P1在8個(gè)序列上的運(yùn)行結(jié)果顯示,NETNGP算法和SNGP-Best算法的運(yùn)行時(shí)間分別為28673ms和3296ms,主要是因?yàn)镹ETNGP運(yùn)用網(wǎng)樹的結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)結(jié)點(diǎn)并在相鄰層建立結(jié)點(diǎn)關(guān)系,占據(jù)了大量的空間,在求解時(shí)需要通過結(jié)點(diǎn)關(guān)系進(jìn)行判斷,因此加大了時(shí)間開銷,因此SNGP-Best算法相對于NETNGP算法而言是高效的.

2)SNGP-Best算法求解速度快于INDNGP算法.圖3中,P3在8個(gè)序列上的運(yùn)行結(jié)果顯示,INDNGP算法和SNGP-Best算法運(yùn)行時(shí)間分別為13650ms和8642ms,這是因?yàn)镮NDNGP 算法同NETNGP算法類似,都運(yùn)用網(wǎng)樹結(jié)構(gòu)建立結(jié)點(diǎn)之間的父子關(guān)系,導(dǎo)致存儲(chǔ)空間被大量占用,求解效率降低,但是INDNGP的求解速率又優(yōu)于NETNGP算法,主要因?yàn)镮NDNGP在求解過程中會(huì)造成丟解,而SNGP-Best算法求得的是完備解,因此,SNGP-Best算法較INDNGP算法而言,性能更優(yōu).

3)SNGP-Best算法求解速度也比SNGP-Slow算法快.圖3中,P9在8個(gè)序列上的運(yùn)行結(jié)果顯示,SNGP-Slow算法和SNGP-Best算法的運(yùn)行時(shí)間分別8782ms和8642ms,實(shí)驗(yàn)數(shù)據(jù)可以得出雖然兩個(gè)算法的運(yùn)行時(shí)間相差較少,但SNGP-Best算法略快,這是因?yàn)殡m然SNGP-Slow算法同SNGP-Best算法都運(yùn)用了在線的方式來處理實(shí)驗(yàn)數(shù)據(jù),但SNGP-Slow算法在進(jìn)行結(jié)點(diǎn)判斷時(shí)需要考慮相鄰且相同字符所對應(yīng)的隊(duì)列層之間的結(jié)點(diǎn)情況,然后再進(jìn)行匹配,因此一定程度上時(shí)間消耗會(huì)相應(yīng)地增加.

4)SNGP-Best的時(shí)間開銷相對于其他三個(gè)算法而言是效果最優(yōu).圖3的實(shí)驗(yàn)結(jié)果均表明SNGP-Best求解時(shí)運(yùn)行時(shí)間是最少的.這是因?yàn)镾NGP-Best采用在線計(jì)算方式進(jìn)行計(jì)算,很大程度上節(jié)省了存儲(chǔ)空間,提高了求解效率.

在DNA數(shù)據(jù)集上,SNFP-Best算法既具備了求解速度快的特點(diǎn),還保證了解的完備性.實(shí)驗(yàn)結(jié)果充分驗(yàn)證了SNGP-Best算法的正確性和有效性.

5 結(jié) 論

針對無先驗(yàn)知識情況下設(shè)定間隙難的問題,提出了無間隙約束下無重疊模式匹配問題,并給出了高效的在線求解算法SNGP-Best,該算法在保證順序?qū)?yīng)的前提下,允許連續(xù)兩個(gè)模式子串匹配的序列字符串可以不必連續(xù),且采用無重疊方式統(tǒng)計(jì)出現(xiàn)個(gè)數(shù).該算法采用在線計(jì)算的方式,能夠及時(shí)計(jì)算出滿足條件的出現(xiàn)并輸出.大量對比性實(shí)驗(yàn),充分地驗(yàn)證了SNGP-Best算法求解的完備性以及性能的高效性.