2015, Vol. 26
2 大连理工大学 软件学院, 辽宁 大连 116621;
3 合肥工业大学 计算机科学与信息工程学院, 安徽 合肥 230009;
4 Department of Computer Science, University of Vermont, Burlington, USA
2 School of Software, Dalian University of Technology, Dalian 116621, China;
3 School of Computer Science and Information Engineering, Hefei University of Technology, Hefei 230009, China;
4 Department of Computer Science, University of Vermont, Burlington, USA
模式匹配是许多问题的研究基础,如信息检索[1]、数据存储与管理[2]以及网络安全[3]等多方面.近年来,人们更加关注带通配符的模式匹配问题,特别是具有多个可变间隙的模式P可以描述为
p0[a0,b0]p1…[aj-1,bj-1]pj…[am-1,bm-2]pm-1,
其中,aj-1和bj-1是指pj-1和pj之间可以通配的最小和最大间隙.由于允许用户指定不同长度的约束,具有更高的灵活性,这使得其在现实世界中有很多重要的应用.在生物信息学领域,TATA通常出现在CAATCT之后,间隔30~50个字符[4],因此,利用带通配符的模式匹配技术可以在DNA序列中提取很多有价值的信息;在音乐信息检索方面,Crochemore等人[5]提出了(d,a)-近似匹配,并指出,这种匹配方法可以应用于音乐信息检索等领域;在序列模式挖掘中,具有间隙约束的模式匹配技术应用更加广泛.Zhang等人[6]提出了周期间隙的序列模式挖掘问题,之后,文献[7]采用模式匹配技术对此问题进行了研究,提高了原有问题的挖掘速度;Ding等人[8]采用INSgrow的模式匹配算法,对无重叠约束的序列模式挖掘问题进行了研究;鉴于在序列模式挖掘中,通常每个位置的字符只能使用一次,为此,Chen等人[9]最早提出了具有一次性条件的模式匹配问题,文献[10]采用网树结构构造了启发式算法SBO,提高了问题的求解质量;之后,Guo等人[11]建立了更为有效的WOW算法.Wu等人[12]对具有一次性条件的序列模式挖掘问题进行了研究,其核心技术依然是模式匹配技术.Lam等人[13]也是在一次性条件下对压缩的序列模式的挖掘进行了研究.由于序列的有序性,因此,采用非负间隙的模式匹配技术无疑禁止了子模式串次序颠倒现象的发生.为此,Fredriksson和Grabowski[14,15]开展了间隙可以为负的一般间隙模式匹配研究,但是其研究仅仅关心在序列串中的何位置能够产生出现,而不关心具体如何产生的出现,因此,这种匹配方式被称为宽松匹配.文献[16]开展了一般间隙的严格匹配,在其研究中,具体衡量了每个模式子串是如何匹配序列中的字符的.但是在其研究中允许任意位置字符多次使用,其算法的计算复杂性为P.若采用非负间隙进行模式挖掘,当序列数据库发生扰动时就会漏掉一些有价值的信息,因此,利用一般间隙进行模式挖掘更能够发现更多有用的信息.
由于模式匹配问题是序列模式挖掘的重要基础,因此,本文对具有一次性条件的一般间隙严格模式匹配问题(strict pattern matching with general gaps and one-off condition,简称SPANGOO)进行研究.该问题具有如下4个特点:各个子模式串之间的间隙可以为负;序列串中任意位置的字符最多能使用一次;是一种严格的模式匹配;是一种精确的模式匹配.对上述特点举例进行说明.
例1:给定字符串序列S=s0s1s2s3s4s5=abaaba,模式串P=p0[a0,b0]p1[a1,b1]p2=a[0,1]b[0,1]a.
子模式a[0,1]b的含义是:在字符a和字符b之间可以通配0到1个字符,0称为最小间隙约束,1称为最大间隙约束.即,若p0=si,p1=sj,且0≤j-i-1≤1,则表示位置为i的字符a和位置为j的字符b满足间隙约束.
例1中的子模式串之间的最小间隙约束均大于等于0,我们称这样的间隙约束为非负间隙约束;若最大间隙和最小间隙至少有一个小于0,我们称这样的间隙约束为一般间隙约束.
例1中满足间隙约束的所有出现为{á0,1,2ñ,á0,1,3ñ,á2,4,5ñ,á3,4,5ñ}.若规定字符串中任意位置字符只能在所有出现中最多使用一次,则称为一次性条件约束[9].在一次性条件约束下,例1的最大出现数为2,分别为{á0,1,2ñ,á3,4,5ñ}或者{á0,1,3ñ,á2,4,5ñ}.若允许任意位置字符多次出现,但是不允许两个出现中的相同位置字符一样,则称为无重叠约束,如出现á0,1,2ñ和出现á0,1,3ñ就不满足无重叠约束条件.á0,1,2ñ和á2,4,5ñ虽然两个出现中都有2,但是出现在不同的位置,所以满足无重叠约束[8].
文献[16]最早对模式匹配的类型进行了分类,分为严格模式匹配[9,10,11,16]和宽松模式匹配[14,15].其中,严格模式匹配是指用一组值来描述一个出现,这组值由模式串中对应的字符在满足间隙约束的情况下在序列串中的位置组成的.若按严格模式匹配,例1中有4个出现,分别是á0,1,2ñ,á0,1,3ñ,á2,4,5ñ,á3,4,5ñ.而宽松模式匹配是采用模式串中最后一个位置的字符在序列串中的位置来表示出现,若按照宽松模式匹配,例1中有3个出现,分别为2,3,5.
在匹配类型方面,有精确模式匹配与近似模式匹配之分.精确模式匹配是指出现中pj和si必须相同,如文献[9,10,11,16]都是对精确模式匹配进行的研究.与精确模式匹配相对应的是近似模式匹配,近似模式匹配按照距离计算公式的不同分为Hamming距离下的近似匹配[17]、编辑距离下的近似匹配[4]和d近似匹配[14,15]等.而本文的研究属于精确匹配.本文贡献如下:
(1) 提出了具有一般间隙的一次性条件下的严格模式匹配问题SPANGOO.
在具有间隙约束的模式串中允许子模式串之间的间隙为负值,并且加入了一次性条件的约束,是一种序列串中任意位置字符最多使用一次的严格精确模式匹配.
(2) 提出了动态更新结点信息的启发式求解算法(dynamically changing node property,简称DCNP).
DCNP算法采用DSGSP策略和SRMP-Gen策略相结合的方法选择最优出现.在DSGSP策略中采用了动态更新结点属性的策略,通过动态更新共同祖先集的树根路径数、树叶路径数及位置相关数来消除内部重复现象.由于动态更新结点属性会大幅度提高算法的复杂性,因而提出Checking机制对模式串进行预处理,来判断出现内部是否会产生内部重复的现象.若不会产生重复,则不触发动态更新,从而提高了DCNP算法的运行效率.理论分析指出,DCNP算法的空间复杂度和时间复杂度分别为O(mxnxMaxGap)和O(nxMaxGapx(m2+n)).这里,m,n和MaxGap分别是模式串长度、序列串长度以及模式串的最大间隙(MaxGap=max(bi-ai-1)).
(3) 对DCNP算法的求解性能进行了对比测试.
本文在大量真实生物数据上,与多种相关算法的改进算法进行了对比性实验,通过实验结果验证了本文算法的有效性,并对实验结果进行了分析.
本文第1节对相关工作进行总结.第2节给出SPANGOO问题的定义.第3节介绍网树的定义和性质,在此基础上给出DCNP算法,分析算法的空间复杂度和时间复杂度,并且通过实例来说明动态更新结点属性的过程.第4节通过大量对比性实验测试DCNP算法的性能.第5节得出本文的结论.
1 相关工作目前,具有间隙约束的模式匹配问题可以从以下6个方面进行划分:是否具有多个可变间隙、一般间隙模式串与否、宽松模式匹配还是严格模式匹配、精确匹配还是近似匹配、是否具有一次性条件、是否具有长度约束.
Manber等人[18]最早开展了具有可变间隙约束的模式匹配问题的研究,在其研究中,将通配符描述为[0,g]形式,其中,g表示一个可变长度.但是,其研究的是单个可变间隙约束的模式匹配.伴随研究的不断深入发展,模式匹配技术由之前的单个可变间隙约束逐步发展为多个可变间隙约束,如Navarro和Raffinot[19]在2003年运用具有多个可变间隙约束的模式匹配技术进行蛋白质查找.具有多个可变间隙的模式匹配技术具有更高的灵活性,在现实世界中更具实用意义.
Fredriksson[14]和Grabowski[15]先后在2006年和2008年对一般间隙模式匹配进行了研究,并在音乐检索和序列蛋白质匹配等问题中进行了应用.文献[16]利用子网树对具有长度约束的一般间隙下的严格模式匹配进行了研究.一般间隙约束的模式匹配允许子模式串之间的间隙约束为负,应用在模式挖掘中能够发现更多有价值的信息.
Bille等人[20]不但在2010年对具有多个可变非负间隙约束的宽松模式匹配问题进行了研究,而且在2012年分别对具有多个可变非负间隙约束的宽松匹配和严格匹配进行了研究[21].此外,在音乐信息检索中多使用宽松模式匹配[5],而在生物信息计算中多采用严格模式匹配[9].
由于在序列模式挖掘中很多情况下任意位置字符通常都使用1次,为此,Chen等人[9]提出了具有一次性条件的模式匹配问题,利用一次性条件过滤掉大量冗余信息,提高匹配效率.Lam等人[13]在一次性条件下对压缩的序列模式挖掘问题进行了研究,表 1给出了几种具有间隙约束的模式匹配对比.
|
Table 1 Comparison of pattern matching with gap constraints 表 1 几种具有间隙约束的模式匹配对比 |
由表 1可以看出:本文与文献[16]的主要区别在于,文献[16]研究不具有一次性条件的模式匹配问题,而本文是对具有一次性条件的模式匹配问题进行研究.文献[16]中,只需要考虑各个子模式间的间隙约束与长度约束即可,并且该问题计算复杂性为P;而本文不仅要考虑子模式间的间隙约束,还要考虑出现是否满足一次性条件.本文理论证明了一般间隙及一次性条件下模式匹配问题的计算复杂性为NP-Hard(证明详见第2节的定理1),因此求解难度更大.为此,本文构建合理的策略,形成了启发式算法DCNP,使得在满足一次性条件的情况下找出更多的出现.
本文的研究工作与文献[11]的区别在于:文献[11]是对非负间隙的严格模式匹配进行研究,而本文是对间隙约束可以为负的一般间隙模式匹配问题进行研究.在负间隙的作用下,匹配过程中会出现字符回溯的情况,使得子模式串pj+1可能出现在子模式串pj之前,从而使得一个出现中可能会出现位置重复的现象.因此,一般间隙下的一次性条件的模式匹配不仅要避免出现与出现之间的位置重复,而且还要避免出现内部存在重复的情况.在这个过程中,我们要判定内部重复在何处产生以及内部重复涉及的范围,并且构造合理的策略有效地消除内部重复.因而,本文研究的问题是比非负间隙下一次性条件的模式匹配更为复杂的研究.在应用方面,文献[12,22]都是在非负间隙下基于一次性条件的序列模式挖掘,但这样的序列模式挖掘潜在地约定了事件发生次序.尽管Zhang等人[23]的伴随关系挖掘可以解决事件发生的次序问题,但是这类研究不具有间隙约束.而在一般间隙下的基于一次性条件的序列模式挖掘将既可以解决事件发生次序问题,也同时具有了间隙约束.而模式匹配技术是序列模式挖掘中核心任务,因此,一般间隙的模式匹配要比非负间隙的模式匹配更具有实际意义.
2SPANGOO问题定义 2.1 问题定义定义1. 序列串S=s0s1…si…sn-1,这里,n表示S的长度,siÎS代表一种符号集.对于不同的应用,S可以是不同的符号集合,例如在DNA序列中,S是由{A,T,G,C}构成的.
定义2. 具有间隙约束的模式串P可以表示为p0[a0,b0]p1…[aj,bj]pj+1…[am-2,bm-2]pm-1,这里,m表示模式串P的长度,pjÎS,aj和bj是给定整数值,代表子模式pj和pj+1之间可以匹配通配符的最小和最大长度,这里,aj≤bj.如果所有的aj和bj均大于等于0,则称为非负间隙约束,间隙约束都为非负的模式串称为非负间隙模式串;若aj和bj至少有一个小于0,则称为一般间隙约束,包含一般间隙约束的模式串称为一般间隙模式串.MaxGap= max(bj-aj+1)称为模式串P的最大间距.
定义3. 给定模式串P=p0[a0,b0]p1…[aj,bj]pj+1…[am-2,bm-2]pm-1,若存在pi=pj,其中i¹j,0≤i≤m-1,0≤j≤m-1,则称模式串为包含重复字符的模式串;否则称为不包含重复字符的模式串.
定义4. 若一个位置索引序列I=ái0,...,ij,...,im-1ñ,其中,0≤ij≤n-1,0≤j≤m-1,且ij¹ij-1,服从${s_{{i_j}}} = {p_j}$且
$\left\{ {\begin{array}{*{20}{l}} {{a_{j - 1}} \le {i_j} - {i_{j - 1}} - 1 \le {b_{j - 1}},{\rm{ if }}{i_{j - 1}} < {i_j}}\\ {{a_{j - 1}} \le {i_j} - {i_{j - 1}} \le {b_{j - 1}},{\rm{ if }}{i_{j - 1}} > {i_j}} \end{array}} \right.{\rm{,}}$
则称I是模式串P在模式串S中满足间隙约束的一个出现.
由于一次性条件下一般间隙的模式匹配问题的特殊性,即,在一般间隙模式串中,子模式pj+1可能出现在子模式pj之前,如果存在pj+k+1=pj(这里,0<k≤m-2),就有可能产生pj+k+1与pj匹配相同位置字符的出现.显然,这样的出现并不是我们想要的.为了将这样的出现加以区分,我们给出如下定义:
定义5. 给定一个出现I=ái0,...,ij,...,im-1ñ,如果存在ik=ig的情况(k¹g,0≤k≤m-1,0≤g≤m-1),则称为内部有重复的出现;否则,称为内部无重复的出现.
例2:给定序列串S=s0s1s2s3=agag,模式串P=p0[a0,b0]p1[a1,b1]p2=g[-1,1]a[0,2]g.
由于s1=g,因此p0=g可以与s1匹配.在间隙[-1,1]的作用下,p1=a可以与s0匹配;而在间隙[0,2]的作用下,p2不但可以与s3匹配,而且可以与s1匹配.若与s1匹配就形成了出现á1,0,1ñ.这种情况就属于内部有重复的出现.
定义6. 令集合OCC(S,P)代表模式串P在序列串S中的所有出现,集合OCC(S,P)的长度用|OCC(S,P)|来 表示.
定义7. 给定两个内部无重复的出现C=ác0,…,ck,…,cm-1ñ和D=ád0,…,dj,…,dm-1ñ,如果存在ck=dj(0≤k≤m-1且0≤j≤m-1),则称出现C和出现D不满足一次性条件;否则,称出现C和出现D满足一次性条件.
定义8. 若OCC(S,P)的子集OCC1(S,P)中任何两个内部无重复的出现都满足一次性条件,则称子集OCC1(S,P)是具有一次性条件的一般间隙的模式匹配.具有一般间隙和一次性条件的严格模式匹配(SPANGOO)的判定问题是给定序列串S和模式串P,判定模式P在序列S是否存在t个满足一次性条件的出现.而SPANGOO的优化问题在给定序列串S和模式串P中,最多存在多少个满足一次性条件的出现.本文的任务是求解OCC(S,P)中任何两个内部无重复的出现都满足一次性条件的最大子集OCCMAX(S,P).
例3:给定序列串S=s0s1s2s3s4s5s6s7=baaccbaa和模式串P=p0[a0,b0]p1[a1,b1]p2=a[-1,2]b[-1,2]a.
根据给定条件可知,模式串P在序列串S中的所有出现OCC(S,P)为{á1,0,1ñ,á1,0,2ñ,á2,5,7ñ,á2,5,6ñ,á6,5,6ñ,á6,5,7ñ},可知|OCC(S,P)|为6,依据定义7和定义8可知,具有一次性条件的一般间隙的最大模式匹配问题的解OCCMAX(S,P)是{á1,0,2ñ,á6,5,7ñ}.
由例3可以看出,一般间隙严格模式匹配(SPANGOO)是比文献[10]的MPMGOOC问题更为复杂的问题.这是因为在一般间隙的作用下,会存在出现内部有重复的现象,如á1,0,1ñ和á6,5,6ñ这两个出现都是出现内部有重复的出现.而MPMGOOC问题中都是非负间隙,所以不会产生诸如á1,0,1ñ的出现.由于在SPANGOO中存在á1,0,1ñ的出现,在求解过程中不仅要增加一个是否有内部重复判定,更为重要的是:位置的重复使用会放大这些位置的实际作用,进而影响到问题的求解.为了消除这样的影响,在求解过程中需要注意如下3件事情:
(I) 如何通过模式串预先判定是否会出现内部重复,如果会出现内部重复,具体是哪个子模式产生的.在例1中是不会产生重复的,因为模式串是非负间隙的;但是即使是包含负间隙的模式串,也不一定会产生出现内部有重复的现象,例如模式串a[-1,2]b[1,2]c中,因为模式串是不包含重复字符的,所以不会产生内部重复;若模式串包含重复字符并且包含负间隙,也不一定会产生内部重复的现象,例如模式串a[-1,2]b[1,2]a,尽管该模式中字符a有2个,假定b可以匹配的字符位置为k,第1个a在子模式“a[-1,2]b”的作用下,a可以匹配的字符位置最大为k+1,但是第2个a在子模式“b[1,2]a”的作用下,a可以匹配的字符位置最小为k+2,这样就不会产生有重复的出现.因此,需要有效地依据模式串判定是否会产生内部重复以及内部重复产生的位置.
(II) 如果通过模式串预先判定会有出现内部产生重复的问题,需要在相应位置建立检查,以避免这样的出现.例如在例3中,在找到子出现á1,0ñ时,存在两种选择á1,0,1ñ和á1,0,2ñ.此时,需要建立检查机制,最终选择á1,0,2ñ.而在找到子出现á1ñ时,无需对子出现á1,0ñ开展检查机制,因为在子模式p1位置处,就不会产生有重复的现象.因此需要有效的机制,仅在可能产生重复的位置建立检查.
(III) 如何判定重复可能产生的范围并有效地消除被放大的影响,这也是SPANGOO处理中最为复杂的过程.依然以例3为例进行说明,在选择了á1ñ以后,由于á1ñ存在作用被放大的现象,这需要消除á1ñ的影响,如果在整个序列上消除,就会产生被扩大化的现象,进而导致算法性能的下降,因为á1ñ仅仅作用在局部位置,仅仅会在á1,0,1ñ和á1,0,2ñ两个出现中产生影响.那么,如何高效地找出á1ñ可能影响的区域,并在该区域内部消除影响呢?
2.2 计算复杂性分析定义9(迭代洗牌). 给定一个字符集S及两个均属于S*且长度为k的字符串V=v0v1…vk-1和W=w0w1…wk-1,用“VQW”表示洗牌V和W,VQW可以定义为:VQW={v0w0v1w1…vk-1wk-1|对于任意0≤j<k都有vjÎS且wjÎS}.迭代洗牌X就是其可以表示为eÈ{V}È{VQV}È{VQVQV}È…这里,e表示空集.迭代洗牌的判定问题是:给定一个字符串X,判定其是否由字符串V迭代洗牌构成的[24].
引理1. 判定一个字符串X是否由字符V迭代洗牌构成的,其计算复杂性为NP-Complete问题.
证明:文献[24]给出了这个问题的计算复杂性证明.
例4:给定字符串X=ataatt和字符串V=at.
X是对字符串V迭代洗牌的结果,因为XÎ{VQVQV};但是X¢=atatta不是对V迭代洗牌的结果,因为子串“atta”不是对V迭代洗牌的结果.
引理2. 具有非负间隙及一次性条件约束的模式匹配的判定问题计算复杂性为NP-Complete问题.
证明:显然,判定序列串S是由t次对模式串P迭代洗牌和判定模式串P在序列串S中出现次数是否为t个的计算复杂性是一致的.这里,模式串P是非负间隙的[9].
定理1. 具有一般间隙及一次性条件约束的模式匹配的判定问题计算复杂性为NP-Complete问题.
证明:由于非负间隙模式可以看成是一般间隙模式的特殊形式,因此,一般间隙及一次性条件约束的模式匹配问题是比非负间隙及一次性条件约束的模式匹配问题更具一般性的问题.故,具有一般间隙及一次性条件约束的模式匹配的判定问题计算复杂性为NP-Complete问题.
由于具有一般间隙及一次性条件约束的模式匹配的判定问题计算复杂性为NP-Complete问题,因此,具有一般间隙及一次性条件约束的模式匹配这个优化问题的计算复杂性为NP-Hard问题.
3 网树与DCNP算法 3.1 网树的概念文献[25]最早提出了网树的概念,为了求解SPANGOO问题,本节在网树定义的基础上给出了网树的一些新的概念和性质,并对这些概念和性质进行了解释.
定义10. 网树具有结点、树根、叶子、层、双亲、孩子等概念的树的拓展结构,其与树结构的区别在于:一棵网树可以有多个根结点;除根结点之外,网树的其他结点可以有多个双亲结点;网树的不同层上结点的标签可以相同,并用$n_j^i$表示第j层的结点i.由于一个结点具有多个双亲,因此,一个结点到达根结点的路径数为多个.
定义11. 文献[10]最早给出了树根路径数RPN、树叶路径数LPN及树根-树叶路径数的定义RLPN,这里再做一个简单的说明.从网树第1层所有的树根结点到结点$n_j^i$的路径数称为结点$n_j^i$的树根路径数RPN(root path number),用${N_r}(n_j^i)$来表示,第1层结点的树根路径数为1;从网树第m层所有叶子结点到结点$n_j^i$的路径数称为结点$n_j^i$的树叶路径数LPN(leaf path number),用${N_l}(n_j^i)$来表示,第m层叶子结点的树叶路径数为1,其余层叶子结点的树叶路径数为0,这里,m是网树的深度;从网树所有根结点到第m层所有叶子结点中的所有路径中,包含结点$n_j^i$的路径数称为该结点的树根-叶子路径数RLPN(root-leaf path number),用${N_f}(n_j^i)$表示.
性质1. 结点$n_j^i$的树根路径数是其所有双亲结点的树根路径数之和;结点$n_j^i$的叶子路径数是其所有孩子结点的叶子路径数之和;结点$n_j^i$的树根-叶子路径数是其树根路径数与其树叶路径数之积[10],即
${N_f}(n_j^i) = {N_r}(n_j^i) \times {N_l}(n_j^i).$
性质2. 位置i的位置相关数RP(i)是网树中所有结点名称是i的结点的树根-叶子路径数之和[10],即
$RP(i) = \sum\nolimits_{j = 1}^m {{N_f}(n_j^i)} .$
这里,m是网树的深度.
定义12. 结点$n_b^c$到达根结点的所有路径上的所有结点的集合称作结点$n_b^c$的祖先集,用$A(n_b^c)$表示.祖先集中任何一个结点都称作结点$n_b^c$的祖先,结点$n_b^c$是自身的一个祖先结点.
定义13. 给定一个结点集合D={d0,d1,…,dl-1},集合D中所有元素的祖先集的交集称为集合D的共同祖先集,用C(D)表示.位置i在集合D的共同祖先集中的所有树根路径数称为位置i在集合D的路径分支数,用pb(i,D)表示[10].
定义14. 一条从树根结点到达叶子结点的路径称为树根叶子路径.网树在移除一条树根叶子路径后,在新的网树上第m层所有叶子结点的树根路径数之和称为网树的剩余出现数.
定义15. 我们将结点的双亲结点中位置相关数较小的结点作为该结点的最优双亲结点OPP,若两个双亲结点的位置相关数相同,则选择在已有路径的共同祖先集中路径分支数最大的双亲结点作为当前结点的OPP.根结点没有OPP.
3.2 DCNP算法分析及设计 3.2.1 建立一般间隙网树的方法由于DCNP算法是基于网树结构设计的,这里先给出建立一般间隙网树的方法.建立非负间隙网树的规则最早由文献[25]给出,在非负间隙条件下,只需要扫描一遍字符串就可以建立网树.但是在一般间隙下,在存在字符回溯的情况下,若仍然按照非负间隙的规则建立网树,就会漏掉一部分结点和父子关系,因此,一般间隙下应该逐层建立网树.这里重新给出一般间隙情况下建立网树的方法.首先从网树的第1层开始建立,逐个扫描字符串S中的字符si,若p0=sj(0≤j<n),则在第1层建立结点$n_1^j$;建立第i(1<i≤m)层结点时,逐个扫描字符串S中的字符si,若pi-1=sj(0≤j<n),并且若这个结点j与第i-1层某结点$n_{i - 1}^e$(e¹j)满足局部间隙约束,则建立结点$n_i^j{\rm{,}}$并且在结点$n_{i - 1}^e$与$n_i^j$间建立父子关系,再检查结点$n_i^j$与i-1层其他结点是否满足间隙约束,若满足也建立父子关系.具
体算法如下:
算法1. CreNetTree.
输入:字符串S,模式串P.
输出:网树NetTree.
1. for i=1 to m step 1
2. start=1;
3. for j=0 to n-1 step 1
4. if (pi-1=sj) then
5. if (i=1) then
6. 建立结点$n_1^j$;
7. else
8. for k=start to 第i-1层的结点个数
9. if (j与第i-1层的第k个结点的间隙>bi-2) then
10. start++;
11. continue;
12. end if
13. if (j与第i-1层的第k个结点的间隙<ai-2) then break;
14. if (不存在结点$n_1^j$) then 建立结点$n_1^j$;
15. 在结点$n_1^j$与第i-1层的第k个结点之间建立父子关系;
16. start++;
17. end for
18. end if
19. end if
20. end for
21. end for
3.2.2 出现内部重复检测机制引理3. 在一般间隙模式串中,在模式串长度大于等于3的情况下,如果存在pj=pj+k+1的情况,其中,0≤j≤m-3,0<k≤m-2,并且满足$\sum\nolimits_{t = 0}^k {{a_{j + t}}} $+k≤0,则可能会在pj处产生内部有重复的出现;否则不会产生内部有重复的出现.
证明:给定模式串P=p0[a0,b0]p1…[aj-1,bj-1]pj…[am-2,bm-2]pm-1,设pj的出现位置为h,pj到pj+k+1之间的间隙约束为[aj,bj]…[aj+k,bj+k],则pj+k+1的最小位置为$\sum\nolimits_{t = 0}^k {{a_{j + t}}} $+k+h($\sum\nolimits_{t = 0}^k {{a_{j + t}}} $≤0时)或$\sum\nolimits_{t = 0}^k {{a_{j + t}}} $+k+h+1($\sum\nolimits_{t = 0}^k {{a_{j + t}}} $>0时).显然,$\sum\nolimits_{t = 0}^k {{a_{j + t}}} $>0时,pj+k+1只能出现在pj之后,不会发生重复的可能;若$\sum\nolimits_{t = 0}^k {{a_{j + t}}} $≤0,则pj+k+1的最小位置为$\sum\nolimits_{t = 0}^k {{a_{j + t}}} $+k+h;当$\sum\nolimits_{t = 0}^k {{a_{j + t}}} $+k≤0成立时,则pj+k+1的最小出现位置会小于等于h,所以pj会有和pj+k+1重合的可能.因此,若pj=pj+k+1并且满足$\sum\nolimits_{t = 0}^k {{a_{j + t}}} $+k<=0,则在pj处可能会产生内部有重复的出现.若$\sum\nolimits_{t = 0}^k {{a_{j + t}}} $+k>0,则pj+k+1只会出现在pj之后,pj不可能会和pj+k+1产生重复.
因算法本身采用网树结构,因此查找出现时,是从最后一层叶子结点依次往前查找.因此在判断哪些子模式串会产生重复时,采用从后往前的查找方式.并且增加一个布尔型标志数组needrep来标示某子模式是否会和它之后的某个子模式存在重复的可能,needrep的初始值为false.当模式串为非负间隙模式或者为不包含重复字符时,不会出现内部重复的情况;否则,从pm-3依次往前查找,检查子模式pm-3是否会和它之后的模式发生重复.
若找到pm-3+k+1=pm-3,并且满足$\sum\nolimits_{t = 0}^k {{a_{j + t}}} $+k≤0,则将pm-3的needrep设置为true;若不存在这样的模式,则pm-3的needrep值保持false不变,继续找pm-2是否会和它之后的模式发生重复.依照上述过程检查,直到检查完p0为止.具体算法给出如下:
算法2. Checking.
输入:模式串P.
输出:标志数组needrep.
1. 初始化标志数组needrep使得其全为false;
2. if (模式串中间隙都为非负) then return needrep
3. if (P不包含重复字符) then return needrep
4. else
5. for i=m-3 downto 0 step-1
6. for j=i+2 to m-1 step 1
7. if (pi=pj and $\sum\nolimits_{t = 0}^{j - i - 1} {{a_{j + t}}} $+j-i-1<=0) then
8. needrep[i]=true;
9. break;
10. end if
11. end for
12. end for
13. end if
14. return needrep
3.2.3 DSGSP算法DSGSP算法与MPMGOOC问题[10]中的SGSP算法不同的是,在SGSP算法中,无需考虑出现内部重复的情况;但是在DSGSP算法中,由于负间隙的作用,我们要对可能产生重复的位置进行处理,并且要尽量缩小重复所影响的范围.我们通过动态更新已有路径中共同祖先集结点属性这一策略来解决这个问题,因此,DSGSP算法的核心思想是:从第m叶子结点依次往上查找当前结点的OPP,在查找之前先判定当前结点的上一层的needrep是否为true:若为true,则更新已有路径共同祖先集结点的属性;若为false,则不用更新.然后,选择双亲结点中位置相关数较小的结点作为当前结点的OPP,若位置相关数相同,则选择已有路径的共同祖先集中路径分支数较大的结点作为当前结点的OPP,直到根结点.下面给出具体的DSGSP算法.
算法3. DSGSP.
输入:标志数组needrep和叶子结点f.
输出:出现A.
1. 计算每个结点的树根路径数、树叶路径数、位置相关数;
2. A[m-1]=f;
3. for j=m-2 downto 0 step-1 do
4. if (needrep[j]=true) then 更新已有路径共同祖先集结点的树根路径数、树叶路径数和位置相关数;
5. 计算每个结点i在已有路径A下的路径分支数pb(i,A);
6. n=A[j+1].number_of_parents;
7. A[j]=A[j+1].parent[n-1];
8. for k=n-2 downto 0 step-1 do
9. if (RP(A[j]>RP(A[j+1].parent[k])) then A[j]=A[j+1].parent[k];
10. if (RP(A[j])=RP(A[j+1].parent[k]) and (pb(A[j+1].parent[k],A)>=pb(A[j],A)))
then A[j]=A[j+1].parent[k];
11. end for
12. end for
13. return A
3.2.4 SRMP-Gen算法SRMP-Gen选择当前结点的最右双亲结点作为OPP,但是在一般间隙模式匹配中,SRMP-Gen策略要避免á1,0,1ñ现象的出现.当选择第i层结点的OPP时,若pi-2的needrep为true,则需要判断当前最右结点是否和已有路径中的结点重复:若重复,则选择次右结点作为第i层的OPP.若pi-2的needrep为false,则无需判断是否和已有路径中的结点重复.下面给出SGMP-Gen算法.
算法4. SRMP-Gen.
输入:标志数组needrep和叶子结点f.
输出:一个出现A.
1. A[m-1]=f;
2. for j=m-2 downto 0 step-1 do
3. n=A[j+1].number_of_parents;
4. for k=n-1 downto 0 do
5. if (used[A[j+1].parent[k]]=false) then
6. if (needrep[j]=false) then //不存在重复可能
7. A[j]=A[j+1].parent[k];
8. break;
9. end if
10. if (A[j+1].parent[k]存在已有路径之中) then //存在重复可能,且存在已有路径中
11. k--;
12. continue;
13. end if
14. A[j]=A[j+1].parent[k]; //虽然存在重复可能,但是不在已有路径中,赋值跳出
15. break;
16. end if
17. k--; //标志位为true,已经用过
18. end for
19. end for
20. return A
3.2.5 DCNP算法将DSGSP算法和SRMP-Gen算法相结合,便得到了DCNP算法.DCNP算法选择两者中剩余出现数大的出现作为最优出现.下面给出DCNP算法.
算法5. DCNP.
输入:P=p0[a0,b0]p1…[am-2,bm-2]pm-1,S=s0s1…sn-1.
输出:解C.
1. 调用算法1,依据P和S建立一棵网树;
2. 调用算法2,依据P建立标志数组needrep;
3. for k=第m层叶子结点数downto 1 step-1
4. if (used[第k个叶子结点]=true) then continue;
5. B1=DSGSP(needrep,第k个叶子结点); //算法3
6. y1=剩余出现数(B1);
7. B2=SRMP-Gen(needrep,第k个叶子结点); //算法4
8. y2=剩余出现数(B2);
9. if (y1<y2) then B=B2 else B=B1;
10. C=CÈB;
11. next k
12. return C
3.3 复杂度分析通过以上算法分析可知,DCNP算法的空间复杂度为O(mxnxMaxGap).这是因为网树最多有m层,每层最多有n个结点,每个结点最多有MaxGap个双亲结点或者孩子结点,其中,m为模式串的长度,n为序列串长度,MaxGap为P的最大间隙.
首先分析SRMP-Gen算法的时间复杂度,可知SRMP-Gen算法的时间复杂度为O(m2xMaxGap);再分析DSGSP算法的时间复杂度,DSGSP算法更新网树的树根路径数、树叶路径数的时间复杂度为O(mxnxMaxGap),更新位置相关数的时间复杂度为O(mxn),DSGSP更新祖先集的树根路径数、树叶路径数、位置相关数的时间复杂度为O(m2xMaxGap),计算pb(i,A)的时间复杂度为O(m2xMaxGap),第3行~第11行的时间复杂度为O(m3xMaxGap),DSGSP的时间复杂度为O(mxMaxGapx(m2+n)).
下面分析DCNP的时间复杂度.建立一棵网树的时间复杂度为O(mxnxMaxGap),DSGSP算法的时间复杂度为O(mxMaxGapx(m2+n)),SRMP-Gen的时间复杂度为O(m2xMaxGap),计算出现相关数的时间复杂度为O(mxnxMaxGap).当字符串长度为n模式串长度为m时,最多会有n/m个出现,因此,DCNP算法的时间复杂度为O(nxMaxGapx(m2+n)).
3.4 运行实例通过之前的Checking机制我们可以知道在哪个子模式处会产生内部重复,若已经知道某位置子模式存在重复的可能,即pi的needrep标志位true,在DSGSP算法中,为了消除重复并且缩小重复所影响的范围,我们更新已有路径的共同祖先集结点的树根路径数RPN、树叶路径数LPN以及位置相关数RP.将共同祖先集中存在于已有路径中结点的RPN,LPN,RP更新为0,从而消除内部重复的情况.下面以实例来说明动态更新共同祖先集属性的过程,首先要将实例问题转化为一棵网树.
例5:给定字符串序列S=s0s1s2s3s4s5s6s7s8s9=aabaaabaab,模式串P=p0[a0,b0]p1[a1,b1]p2[a0,b0]p3=a[-1,2]a[-1,3]a[-1,3]b,通过对模式串的预处理可知,p0和needrep标志位为true,p1,p2和p3的needrep为false.
(1) 依据一般间隙网树的建立规则,可将模式匹配问题转化为图 1(a),并且依据性质1计算树根路径数及树叶路径数如图 1(b)所示,树根路径数及树叶路径数在结点左方给出.
 | Fig. 1 The nettree transformed from the pattern matching problem图 1 模式匹配问题转化成网树 |
(2) 首先从最后一层的最后一个叶子结点开始往上查找双亲结点.选择结点$n_4^9$后,选择$n_4^9$的OPP,由于p2的needrep为false,因此不对网树进行更新.结点$n_4^9$有3个双亲结点$n_3^5,n_3^7$和$n_3^8$,根据图 2计算得知:
$\begin{array}{c} RP(5) = {N_f}(n_3^5) + {N_f}(n_2^5) + {N_f}(n_1^5) = 7 \times 2 + 2 \times 4 + 1 \times 10 = 32,\\ RP(7) = {N_f}(n_3^7) + {N_f}(n_2^7) + {N_f}(n_1^7) = 10 \times 2 + 3 \times 1 + 1 \times 2 = 25,\\ RP(8) = {N_f}(n_3^8) + {N_f}(n_2^8) + {N_f}(n_1^8) = 8 \times 1 + 2 \times 2 + 1 \times 1 = 13. \end{array}$
因此,选择位置相关数较小的结点$n_3^8$作为OPP结点.继续选择$n_3^8$的OPP,由于p1的needrep为flase,因此不需要对已有路径的共同子集进行属性的更新;结点$n_3^8$有3个双亲结点$n_2^4,n_2^5$和$n_2^7$,通过计算可知:
$\begin{array}{c} RP(4) = {N_f}(n_3^4) + {N_f}(n_2^4) + {N_f}(n_1^4) = 7 \times 1 + 3 \times 7 + 1 \times 10 = 38,\\ RP(5) = 32,\\ RP(7) = 25. \end{array}$
因此,选择结点$n_2^7$作为$n_3^8$的OPP.再找$n_2^7$的OPP,因为p0的needrep为true,因此要更新已有路径$\{ n_2^7,n_3^8,n_4^9\} $
的共同祖先集.
(3) 依据性质定义12和定义13可得已有路径$n_2^7,n_3^8$和$n_4^9$的共同祖先集如图 2(a)所示,共同祖先集的每层的开始位置和结束位置分别用a[i]和b[i]来表示,其中,i表示所在层,curnode表示当前结点.
(4) 更新共同祖先集中结点的属性.
更新树根路径数从第1层开始,若该结点没有被使用,并且不存在已有路径中,则该结点树根路径数为1,否则为0;若不为第1层,该结点若没有被使用且不存在已有路径中,则该结点的树根路径数等于所有双亲结点的树根路径数之和,否则为0.
更新树叶路径数从第i-1层开始,其中,i为已有路径到达的层数.若该结点没有被使用并且不存在已有路径中,则该结点的树叶路径数为1,否则为0;若不为第i-1层,该结点没有被使用且不存在已有路径中,则该结点的树叶路径数等于所有孩子结点的树叶路径数之和,否则为0;
更新位置相关数,依据性质2计算共同祖先集中位置为i的位置相关数.
图 2(b)为更新共同祖先集属性后的树根路径数、树叶路径数的值.结点左方分别为为树根路径数和树叶路径数.因为位置8已经存在于已有路径中,所以更新后结点$n_1^8$的树叶路径数、树根路径数都为0,以后进行选择都不会选择结点8,从而有效地避免了内部重复情况的出现.综上所述,我们通过更新共同祖先集属性的方法可以有效地避免内部重复情况的发生,并且尽可能地缩小了更新结点属性的范围.
 | Fig. 2 The common ancestor nodes of the current path图 2 当前路径的共同祖先集 |
本节采用真实生物数据来对比SAIL-Gen,SGSP-Gen,SRMP-Gen,SBO-Gen和DCNP算法的性能.其中,SAIL-Gen,SGSP-Gen,SRMP-Gen,SBO-Gen分别为在一般间隙条件下对文献[9,10]的改进算法,这些算法的源程序可以在http://wuc.scse.hebut.edu.cn/nettree/dcnp-2/处下载.实验运行的软、硬件环境为:酷睿双核T4200,主频2.0GHZ,内存1.0GB,Windows 7操作系统的笔记本.本文采用文献[10]的所使用的真实数据作为测试序列,这些真实DNA序列可以从美国国家生物计算信息中心的网站下载(http://www.ncbi.nlm.nih.gov/-genomes/FLU/ SwineFlu.html).表 2给出了的这8个序列串的特征.
|
|
Table 2 Sequences of real biological data 表 2 真实生物数据片段 |
为了测试在模式串中不存在重复字符和存在重复字符时算法的求解性能,我们选取了P1~P4模式为不存在重复字符的4种模式,P5~P9模式为存在重复字符的5种模式,具体模式串在表 3中给出.这5种算法在模式串中不存在重复字符的测试结果见表 4,在模式串中存在重复字符的测试结果见表 5,每种情况的最好解都用加粗方式显示.
|
|
Table 3 Patterns 表 3 模式串 |
|
|
Table 4 Number of occurrences of non-repetitive patterns in sequences S1~S8 表 4 无重复模式串在S1~S8序列串下的出现个数 |
|
|
Table 5 Number of occurrences of repetitive patterns in sequences S1~S8 表 5 有重复模式在S1~S8序列串上的出现个数 |
为了清晰地反映这5种算法在P1~P9模式在8种不同序列上的性能,表 6给出了不同算法在不同模式下计算出现数的总和.
|
|
Table 6 Comparison of the number of occurrences of P1~P9 (No.) 表 6 5种算法在P1~P9上的出现个数(个) |
为了清晰地反映这5种算法在P1~P9模式在8种不同序列上的时间性能,表 7给出了不同算法在不同模式下的平均运行时间.
|
|
Table 7 Comparison of the running time on P1~P9 (ms) 表 7 5种算法在P1~P9上的运行时间(ms) |
(1) 在模式串中没有重复字符的情况下,SAIL-Gen和SRMP-Gen属于完备性算法,尽管DCNP属于近似算法,但它的解极其接近完备解.
由表 3可知,P1~P4中各个字符均不同.而文献[9]证明了在此情况下,SAIL算法是完备性算法.由于各个子模式彼此不同,因此即使在一般间隙下,也不会存在两个子模式匹配同一位置字符的现象.因此,SAIL-Gen依然是完备性算法.SAIL-Gen可以看成是从第1个叶子结点开始采用最左双亲策略进行求解,而SRMP-Gen是从最后一个叶子结点开始,采用最右双亲策略进行求解,因此二者算法原理相同,故而,SRMP-Gen也可以在模式串中字符不同的情况下获得完备解.
通过表 4和表 6可以清晰地看到,DCNP算法在P1~P4模式均可达到或接近完备解.通过表 6可以看出: SAIL-Gen算法在模式P1下8个序列上出现总个数为1 795,而DCNP算法在8个序列上找到了1 791个出现.在这个实例上,DCNP算法的近似度高达99.7+%.同理,我们可以看到:DCNP算法在模式P2和8个序列上近似度为99.6+%,而在P3和P4的近似度则更高,充分地说明了当模式串中没有重复字符的情况下,DCNP的解极其接近完毕解.
(2) 在模式串中具有重复的字符情况下,SAIL-Gen算法的性能最差,而DCNP算法的性能最好,SBO-Gen算法的性能次之.
由于P5~P9中模式串中具有重复的字符,从表 5可以清晰看到,SAIL-Gen不但不能在任何实例上取得最好的结果;而且从表 6可以看到,在P5~P9这5种模式在全部8个序列的出现数总和计算中,SAIL-Gen算法均取得了最小值.更为重要的是,SAIL-Gen算法的解性能相距DCNP算法解的差异显著.例如,SAIL-Gen算法在模式P5和8个序列上仅仅找到了545个出现,而DCNP算法则找到了665个出现,SAIL-Gen算法解性能在这组实例上仅仅达到DCNP算法的81%.这些实验结果充分说明:在求解模式串中具有重复的字符情况下这种一般性问题时,不宜采用SAIL-Gen算法进行求解.
而通过表 5可以清晰地看出,SBO-Gen算法和DCNP算法在大多数情况下都取得了最好的结果;并且通过表 6可以进一步发现,SBO-Gen算法在P5~P9这5组模式上均取得了次好结果,而最好结果均由DCNP算法获得.充分地说明了DCNP算法的性能最好,SBO-Gen算法的性能次之.产生这种现象的原因是:SBO-Gen算法采用了SGSP-Gen与SRMP-Gen相结合的策略,每次选择出现相关数较少的策略,因而其可以很好地解决一次性条件下一般间隙的模式匹配问题.但是由于一般间隙下祖先结点的标号可能存在与子孙结点标号相同的情况,这需要动态更新各个结点的属性,而DCNP算法正是采用了这一原理,因而获得了比SBO-Gen算法更好的效果.
(3) 从表 7的时间消耗上看,DCNP算法最长,而SAIL-Gen算法最短.
SAIL是文献[9]提出的一种在线算法,因此具有最好的时间性能来解决这个问题.SAIL-Gen继承了这一特点,但是如前所述,当面对一般性问题时,SAIL-Gen的求解性能很差,因此不宜采用SAIL-Gen算法进行求解.SBO- Gen算法由于综合使用了SGSP-Gen算法和SRMP-Gen算法的核心策略,因此,SBO-Gen算法求解时间比SGSP- Gen算法和SRMP-Gen算法的求解时间均长.DCNP算法由于需要动态更新结点属性,因此其时间消耗比SBO- Gen算法略长.但是如前所述,DCNP算法解的性能优于SBO-Gen算法.
综上所述,与其他4种算法相比,DCNP算法的解的质量最好,但是时间消耗最长.
5 结 论本文对目前具有间隙约束的模式匹配问题进行了分析和总结,针对目前的模式匹配大多只能按照模式串中规定的模式子串次序进行匹配问题进行研究,提出了一般间隙和一次性的模式匹配问题,而该问题的研究允许用户更加灵活地设定模式串.该问题具有如下一些特点:其间隙是可以为负值的一般间隙,序列中任何字符最多只能使用一次的限制,在匹配的过程中,仔细地考虑了各个模式子串所匹配的位置,因而是一种严格模式匹配,并且该问题是一种精确模式匹配.在理论证明了该问题的计算复杂性为NP-Hard的基础上,采用网树结构建立了求解算法DCNP.该算法采用动态更新结点属性的方法,实现问题的求解.为了减少不必要的动态计算,本文提出了检测机制,仅对可能会造成出现内部产生重复的现象进行动态更新,以便提高DCNP算法的求解性能.之后,本文理论分析了DCNP算法的时间复杂度和空间复杂度.在大量真实数据集上验证了DCNP算法的性能.
模式匹配是序列模式挖掘的基础,本文仅对一般间隙和一次性条件的模式匹配问题进行了研究.下一步将对一般间隙的序列模式挖掘进行研究,该研究将有助于发现更多有价值的频繁模式.此外,在实际应用中,更多模式匹配是近似模式匹配,而本文所研究的问题依然属于精确模式匹配.而这些研究不但具有实际意义,而且研究难度也将更大,这些均属于未来研究的方向.
| [1] | Chou C, Jea K, Liao H. A syntactic approach to twig-query matching on XML streams. Journal of Systems and Software, 2011, 84(6):993-1007 . |
| [2] | Wang M, Zhou JL, Le JJ. A data reusing strategy in column-store data warehouse. Chinese Journal of Computers, 2013,36(8): 1626-1635 (in Chinese with English abstract) . |
| [3] | Song T, Li DN, Wang DS, Xue YB. Memory efficient algorithm and architecture for multi-pattern matching. Ruan Jian Xue Bao/ Journal of Software, 2013,24(7):1650-1665 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4314.htm |
| [4] | Akutsu T. Approximate string matching with variable length don’t care characters. IEICE Trans. on Information and Systems, 1996, E79-D(9):1353-1354. |
| [5] | Crochemore M, Iliopoulos C, Makris C, Rytter W, Tsakalidis A, Trichlas K. Approximate string matching with gaps. Nordic Journal of Computing, 2002,9(1):54-65. |
| [6] | Zhang M, Kao B, Cheung D, Yip K. Mining periodic patterns with gap requirement from sequence. ACM Trans. on Knowledge Discovery from Data, 2007,1(2):Article 7 . |
| [7] | Wu Y, Wang L, Ren J, Ding W, Wu X. Mining sequential patterns with periodic wildcard gaps. Applied Intelligence, 2014,41(1): 99-116 . |
| [8] | Ding B, Lo D, Han J, Khoo SC. Efficient mining of closed repetitive gapped subsequences from a sequence database. In: Ioannidis YE, Lee DL, Ng RT, eds. Proc. of the IEEE 25th Int’l Conf. on Data Engineering (ICDE). IEEE, 2009. 1024-1035 . |
| [9] | Chen G, Wu X, Zhu X, Arslan AN, He Y. Efficient string matching with wildcards and length constraints. Knowledge and Information Systems, 2006,10(4):399-419 . |
| [10] | Wu YX, Wu XD, Jiang H, Min F. A heuristic algorithm for MPMGOOC. Chinese Journal of Computers, 2011,34(8):1452-1462 (in Chinese with English abstract) . |
| [11] | Guo D, Hu X, Xie F, Wu X. Pattern matching with wildcards and gap-length constraints based on a centrality-degree graph. Applied Intelligence, 2013,39(1):57-74 . |
| [12] | Wu X, Zhu X, He Y, Araslan A. PMBC: Pattern mining from biological sequences with wildcard constraints. Computers in Biology and Medicine, 2013,43(5):481-492 . |
| [13] | Lam H, Morchen F, Fradkin D, Calders T. Mining compressing sequential patterns. Statistical Analysis and Data Mining, 2012,7(1): 34-52 . |
| [14] | Fredriksson K, Grabowski S. Efficient algorithms for pattern matching with general gaps and character classed. In: Crestani F, Ferragina P, Sanderson M, eds. Proc. of the Int’l Conf. on String Processing and Information Retrieval. Springer-Verlag, 2006. 267-278 . |
| [15] | Fredriksson K, Grabowski S. Efficient algorithms for pattern matching with general gaps, character classes, and transposition invariance. Information Retrieval, 2008,11(4):335-357 . |
| [16] | Wu YX, Liu YW, Guo L, Wu XD. Subnettrees for strict pattern matching with general gaps and length constraints. Ruan Jian Xue Bao/Journal of Software, 2013,24(5):915-932 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4381.htm |
| [17] | He D, Wu X, Zhu X. SAIL-APPROX: An efficient on-line algorithm for approximate pattern matching with wildcards and length constraints. In: Proc. of the 2007 IEEE Int’l Conf. on Bioinformatics and Biomedicine (BIBM 2007). IEEE Computer Society, 2007. 151-158 . |
| [18] | Manber U, Baeza-Yates R. An algorithm for string matching with a sequence of don’t cares. Information Processing Letters, 1991, 37(3):133-136 . |
| [19] | Navarro G, Raffinot M. Fast and simple character classes and bounded gaps pattern matching, with applications to protein searching. Journal of Computational Biology, 2003,10(6):903-923 . |
| [20] | Bille P, Gørtz I, Vildhøj H, Wind D. String matching with variable length gaps. In: Chávez E, Lonardi S, eds. Proc. of the 17th Int’l Conf. on String Processing and Information Retrieval (SPIRE 2010). Mexico: Springer-Verlag, 2010. 385-394 . |
| [21] | Bille P, Gørtz I, Vildhøj H, Wind D. String matching with variable length gaps. Theoretical Computer Science, 2012,443:25-34 . |
| [22] | Wu XD, Xie F, Huang YM, Hu XG, Gao J. Mining sequential patterns with wildcards and the one-off condition. Ruan Jian Xue Bao/Journal of Software, 2013,24(8):1804-1815 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/4422.htm |
| [23] | Zhang S, Zhang J, Zhu X, Huang Z. Identifying follow-correlation itemset-pairs. In: Proc. of the Int’l Conf. on Data Mining (ICDM). IEEE Computer Society, 2006. 765-774 . |
| [24] | Warmuth M, Haussler D. On the complexity of iterated shuffle. Journal of Computer and System Sciences, 1984,28(3):345-358 . |
| [25] | Wu Y, Wu X, Min F, Li Y. A nettree for pattern matching with flexible wildcard constraints. In: Proc. of the 2010 IEEE Int’l Conf. on Information Reuse and Integration (IRI 2010). IEEE Systems, Man, and Cybernetics Society, 2010. 109-114 . |
| [2] | 王梅,周娇玲,乐嘉锦.一种列存储数据仓库中的数据复用策略.计算机学报,2013,36(8):1626-1635 . |
| [3] | 嵩天,李冬妮,汪东升,薛一波.存储有效的多模式匹配算法和体系结构.软件学报,2013,24(7):1650-1665. http://www.jos.org.cn/ 1000-9825/4314.htm |
| [10] | 武优西,吴信东,江贺,闵帆.一种求解MPMGOOC问题的启发式算法.计算机学报,2011,34(8):1452-1462 . |
| [16] | 武优西,刘亚伟,郭磊,吴信东.子网树求解一般间隙和长度约束严格模式匹配.软件学报,2013,24(5):915-932. http://www.jos.org. cn/1000-9825/4381.htm |
| [22] | 吴信东,谢飞,黄咏明,胡学钢,高隽.带通配符和one-off条件的序列模式挖.软件学报,2013,24(8):1804-1815. http://www.jos.org. cn/1000-9825/4422.htm |