無間隙約束下無重疊模式匹配的在線求解算法

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

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

1 引 言

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

例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個字符.若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個出現(xiàn)中的任意一個.無重疊約束允許序列中任意位置字符多次出現(xiàn),但是不允許任意兩個出現(xiàn)中同一位置字符相同,如<1,2,4>和<2,3,4>就不滿足無重疊條件,因為其在同一位置共用了4,因此滿足無重疊約束的最大出現(xiàn)數(shù)為2,分別是<1,2,4>和<2,3,5>,盡管2 同時存在于兩個出現(xiàn)中,但處于不同的位置,所以滿足無重疊約束.

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

本文貢獻如下:

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

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

3)進行對比性實驗,驗證本文算法的正確性和高效性.

本文的組織結(jié)構(gòu)如下:第2節(jié)給出了模式匹配的問題定義;第3節(jié)詳細地描述算法SNGP-Best;第4節(jié)給出在數(shù)據(jù)集上的實驗結(jié)果,并對該結(jié)果進行分析;第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ù)量為非負值.在例2中,給定模式P=agg.當s3=g與p2成功匹配時,s4=g可以與p3進行匹配,s7、s8也可以與p3進行匹配.

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

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

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

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

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

定義7.給定兩個模式P和P′,若模式P所包含的字符都存在于模式P′中,則稱P是P′的子模式,P′是P的超模式.例模式P=CAA,P′=CATA,因為P包含于P′,則P是P′的子模式,P′是P的超模式.

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

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

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

3 求解算法及分析

3.1 求解算法

算法1.SNGP-Best

輸入:模式P和序列S

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

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

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

3:endfor

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

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

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

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

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

9:endif

10:if(最后一個隊列不為空)then

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

12:C=C∪occ;

13:endif

14:endfor

15:endfor

16:returnC

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

算法2.B_Pattern

輸入:全部隊列P

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

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

2:if(i==1)then

3:Bool_Pattern[i] =true;

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

5:Bool_Pattern[i] =true;

6:endif

7:endfor

8:returnBool_Pattern

3.2 運行實例

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

由P=p1p2p3p4=agac得知,模式P中的字符數(shù)量為4,建立4個隊列,并由s1=a開始讀入,順序進行匹配,結(jié)果如圖1所示.圖1中,第一列灰色填充的圓圈代表第一組出現(xiàn)I1=<1,3,5,7>,第二列灰色填充的圓圈代表第二組出現(xiàn)I2=<5,9,10,11>,第三列、第四列未填充的白色圓圈代表尚未匹配成功的結(jié)點,淺灰色的虛線框代表已將該出現(xiàn)從隊列中輸出.此外,第一個矩形框代表標志位,若為T且與si匹配成功,則創(chuàng)建結(jié)點成功,若為F,則創(chuàng)建結(jié)點失敗,第二個矩形框代表模式P中的各個字符,第三個矩形框代表該隊列中的結(jié)點數(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).這是因為共建立了m個隊列,每個隊列的結(jié)點個數(shù)最多為Len,若不存在出現(xiàn),則創(chuàng)建成功的結(jié)點都存在于隊列中,此時的空間復(fù)雜度為O(m*Len).

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

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

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

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

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

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

表2給定了8個實驗序列的基本特征.

為了驗證算法SNGP-Best的求解性能,我們選取表3中9種不同長度的模式串進行實驗.

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

序號片段名稱位點片段的長度S1Segment1CY0585622299S2Segment2CY0585612286S3Segment3CY0585612169S4Segment4CY0585561720S5Segment5CY0585591516S6Segment6CY0585581418S7Segment7CY058557982S8Segment8CY058560844

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

表3 模式
Table 3 Pattern

序號模式串長度P1acat4P2acatt5P3aacatt6P4gaacatt7P5ggaacatt8P6ggaacattt9P7cggaacattt10P8ccggaacattt11P9cccggaacattt12

4.2 DNA序列的實驗結(jié)果

4.2.1 正確性分析

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

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

由上述實驗結(jié)果可以得到如下結(jié)論:

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

2)由于INSNGP和SNGP-Slow兩個算法都會出現(xiàn)丟解的問題,因此算法 INSNGP和SNGP-Slow均是不完備性算法.盡管如此,SNGP-Slow算法的解的質(zhì)量優(yōu)于INSNGP算法.主要是因為 INSNGP 算法是從樹根層開始向下尋找出現(xiàn),但是樹根層中很多根結(jié)點是不可以抵達葉子結(jié)點的,因此會對一些樹根產(chǎn)生錯誤判定.而SNGP-Slow 算法則采用隊列的形式存儲結(jié)點,優(yōu)先選擇最先出現(xiàn)的結(jié)點構(gòu)成滿足條件的結(jié)點,雖然在相鄰字符相同的情況下會出現(xiàn)結(jié)點誤判的風險,從而造成丟解,但丟掉的解的數(shù)量是比較少的.例如圖2,模式P6在8個序列上的匹配結(jié)果顯示,SNGP-Slow和INSNGP的結(jié)果分別為2415和906,因此上述實驗驗證了算法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)個數(shù)大致呈降低趨勢,偶爾有相同的現(xiàn)象,以SNGP-Best為例,P1-P9在8個序列上的結(jié)果分別為:2511,2505,2501,2437,2429,2423,2355,2349和2342,主要因為給定序列的長度是固定的,要在序列中提取特定的模式,因此長度越長,提取的模式越少.同樣的,就同一模式而言,隨著序列長度依次增長,產(chǎn)生的出現(xiàn)大致呈逐漸減少的趨勢,主要因為給定的模式是固定的,在序列中尋找模式,通常而言,序列越長,尋找到的模式數(shù)量越多.

4.2.2 模式匹配算法的時間性能

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

(1)

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

圖3 運行時間結(jié)果Fig.3 Results of running times

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

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

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

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

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

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

5 結(jié) 論

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