带有间隙约束的模式匹配问题是序列模式挖掘的关键问题之一.目前,大多数的研究都为非负间隙,对字符串中每个字符的出现顺序有着严格的要求.为了增加匹配的灵活性,并且考虑到在序列模式挖掘中采用one-off条件更加合理,研究一般间隙与one-off条件下的模式匹配问题.该问题为NP-Hard问题.为了有效地求解该问题,提出了MSAING(maximum sequential pattern matching with one-off and general gaps condition)算法:首先,利用Reverse策略使模式与序列达到最佳的匹配状态;然后,使用线性表的结构使匹配过程中消耗的时间和空间大幅度地降低,同时,利用回溯机制提高匹配的成功率;最后,根据inside_Checking机制判断模式串是否会产生内部重复现象,以进一步提高算法的执行效率.理论证明了MSAING算法的完备性,实验结果验证了MSAING算法匹配结果的准确性以及在时间和空间方面的高效性.
Pattern matching with gap constraints is one of the key issues of sequential pattern mining. Recently, most research work focuses on pattern matching with non-negative gaps, but the rule strictly limits the order that each character appears in the sequence. In order to increase the flexibility of matching while taking into account that it is more reasonable to use one-off condition in sequential pattern mining, this paper studies the pattern matching problem under general gap and one-off condition, which is NP-hard. To tackle this issue, an algorithm, named MSAING, is proposed. Firstly, the algorithm processes the pattern and sequence using the Reverse strategy to get the maximum number of matching results. Secondly, it significantly reduces the time and space overhead with linear table structure in the matching process, and improves the matching rate using the backtracking method. Finally, to further improve the efficiency of the algorithm, it determines whether internal repetition exists in the pattern or not, according to the inside_Checking mechanism. Completeness of the MSAING algorithm is proved in theory. Experimental results verify the accuracy of the matching results of the MSAING algorithm and its validity in terms of the time and space complexity.
随着大数据时代的到来, 模式匹配技术已被广泛应用到生物信息学[
Fischer等人首次在模式匹配中提出了通配符的概念[
上述研究讨论的均是非负间隙的模式匹配, 即在进行匹配过程中, 子模式
综上所示, 利用一般间隙与one-off条件的模式匹配进行序列挖掘, 能够发现更多有价值的信息, 更符合实际应用的需要.由于序列模式匹配是序列挖掘的关键步骤, 本文对基于一般间隙与one-off条件的序列模式匹配(sequential pattern matching with general gaps and one-off condition, 简称SPMGOO)进行研究.该问题有如下5个特点:是NP-Hard问题; 是一种精确的模式匹配; 是一种严格的模式匹配; 是基于one-off条件的模式匹配; 模式串中的间隔可以为负值.
一般间隙模式匹配通过并、或运算可以分解成非负间隙模式匹配[
(1) 提出了一般间隙与one-off条件的序列模式匹配问题SPMGOO.
在具有间隙约束的模式串中, 允许子模式串之间的间隙为负值; 同时加入了one-off条件, 允许序列串中任意位置的字符最多使用1次的精确的严格模式匹配.之后, 通过理论证明了SPMGOO问题为NP-Hard问题.
(2) 首次使用线性表解决SPMGOO问题, 并且在模式匹配的过程中首次提出对模式串结构以及符号集
(3) 提出了基于一般间隙与one-off条件的最大数目的序列模式匹配算法MSAING.
MSAING算法首先采用Reverse策略判断是否需要转置操作; 然后, 利用线性表的结构进行模式匹配, 具体分为Locate阶段、Forward阶段、Backward阶段, 使MSAING算法在模式匹配过程中消耗的时间和内存大为减少, 同时, 在Backward阶段使用回溯机制, 使匹配的成功率大幅度提高; 最后, 提出了inside_Checking机制判断模式串是否会产生内部重复现象, 以及如果产生内部重复会在模式串的哪个位置产生, 从而有效地提高了MSAING算法的运行效率.经过理论分析得出, MSAING算法的时间复杂度为
(4) 从理论上证明了MSAING算法的正确性和完备性, 并对比测试了MSAING算法的性能.
SPMGOO问题为NP-Hard问题, 本文首先从理论上证明了MSAING算法比目前已有算法具有更好的完备性, 对于不含重复的模式能够取得完备解; 其次, 本文在真实的生物数据集以及文本上, 与DCNP等多种相关的改进算法进行了对比实验, 通过实验结果验证了MSAING算法具有较高的准确性和较低的时空复杂度, 并对实验结果及其意义进行了分析.
本文第2节对相关工作进行总结.第3节给出SPMGOO问题的定义和相关理论分析.第4节介绍MSAING算法设计的过程, 并分析算法的时间和空间复杂度以及算法的正确性与完备性.第5节通过大量对比实验验证MSAING算法的性能.第6节给出结论.
目前, 对于带有间隙约束的模式匹配问题的研究可以分为以下6个方面:是周期模式匹配还是具有多个可变间隙的模式匹配; 是精确匹配还是近似匹配; 是严格模式匹配还是宽松模式匹配; 一般间隙与否; 是否具有one-off条件; 是否具有长度约束[
Fischer等人在1974年首次在模式匹配中提出了通配符的概念[
带通配符的模式匹配的发展过程
Development process of pattern matching with wildcard
近几年来, 随着带一般间隙模式匹配问题研究的深入, 人们逐渐意识到一般间隙模式匹配问题的重要性. Myers[
在文献[
几种具有间隙约束的模式匹配对比
Comparison of pattern matching with gap constraints
相关工作 | 严格/宽松 | 间隙类型 | 间隙个数 | 匹配类型 | one-off | 长度约束 |
注:宽松模式匹配下通常不考虑one-off条件和长度约束问题, 本文以"-"表示不予考虑 | ||||||
Manbe等人[ |
严格 | 非负间隙 | 一个可变 | 精确 | 否 | 无 |
Bille等人[ |
宽松 | 非负间隙 | 多个可变 | 精确 | - | - |
Fredriksso等人[ |
宽松 | 一般间隙 | 多个可变 | 否 | 无 | |
Chen等人[ |
严格 | 非负间隙 | 多个可变 | 精确 | 是 | 有 |
He等人[ |
严格 | 非负间隙 | 多个可变 | Hamming近似 | 是 | 有 |
Ding等人[ |
严格 | 非负间隙 | 多个可变 | 精确 | 否 | 有 |
武等人[ |
严格 | 一般间隙 | 多个可变 | 精确 | 是 | 无 |
本文 | 严格 | 一般间隙 | 多个可变 | 精确 | 是 | 无 |
从
本文与文献[
其中,
则称
一般间隙约束的模式匹配存在内部重复的可能, 但并不是所有的模式匹配都会出现内部重复.下面分析在哪些情况下可能出现内部重复.
(1) 非负间隙的模式串不会有内部重复的出现, 因为模式串中的字符
(2) NR模式不会有内部重复的出现, 因为模式串中的每个字符不可能在序列串中占用相同的位置, 如
(3) 只有在一般间隙约束下的R模式才可能有内部重复的出现, 即
为了避免有内部重复的出现以及提高算法的执行效率, 针对可能出现内部重复的情况, 本文提出了内部重复检测机制.引理1说明了需要进行内部重复检测的条件.
证明:给定模式串
证明:文献[
由于一般间隙与one-off条件的模式匹配的判定问题的计算复杂性为NP-Complete问题, 所以一般间隙与one-off条件的序列模式匹配的优化问题为NP-Hard问题.如何匹配出最优的完备性的解集以及大幅度地降低时空消耗, 是本文的核心任务.同时, 在一般间隙模式匹配问题中如何有效地避免出现与出现之间的重复, 判断内部重复可能产生的范围并有效地消除范围被放大的影响, 这就是本文处理SPMGOO问题中比较复杂的环节.下面将通过介绍MSAING算法给出这些问题的解决方案.
Chen等人[
SAING算法包括3个部分:Locate phase, Forward phase, Backward phase[
Forward phase主要是判断能否建立搜索表, 算法返回值是布尔型.在第1行中, 对能否成功建立搜索表的标记位进行初始化, 初值为false; 第2行计算模式串匹配的范围, 设定可达到的最大位置为
搜索表
Search table
输入:标志数组
输出:
1.
2. 计算模式串匹配的范围为[
3.
4. for
5. for
6. if (!
7.
8. else if (!
9. for
10. if (
11.
12. end if
13. end for
14. end if
15. end for
16. end for
17. if (
18.
19. end if
20. return
文献[
通过引理1的分析证明可知, 一般间隙与one-off条件的模式匹配问题需要考虑内部重复出现的情况.因此, 本文提出了内部检测机制, 通过减少重复检测的次数来提高执行效率.具体检测过程如算法2所示.本文采用线性表的结构, 并增加了一个布尔型的标志数组
输入:模式串
输出:标志数组
1.初始化
2. if (∀min
3. return
4. end if
5. if (∀
6. return
7. else
8. for
9. for
10. if
11.
12. break;
13. end if
14. end for
15. end for
16. end if
17. return
一般间隙约束的模式匹配比非负间隙约束的模式匹配更为复杂, 这是由于在非负间隙约束的模式匹配中, 模式是顺序匹配的, 即
例1:将序列串
序列
Search table for sequence
输入:
输出:出现
1.
2.
3. 计算标志数组
4. for
5. if (!
6. else
7. end if
8. for
9. if (
10. if (
11. else
12.
13.
14. break;
15. end if
16. end if
17. end for
18. if (
19. if (
20. else then
21.
22.
23. end if
24. end if
25. end for
26. return
Forward phase完成搜索表的建立后, 启动Backward phase, 按照最左优先匹配策略, 返回一个出现
● 如果
● 如果
如果超出[
SAING为主程序, 获得所有出现以及出现的个数, 具体设计如算法4所示.首先对序列串
输入:
输出:|
1. for
2. if (
3.
4. if (
5.
6. end if
7. if (
8.
9. for
10.
11. end for
12. end if
13. end if
14. end for
15. return |
SAING算法是利用线性表的结构实现一般间隙与one-off条件下的模式匹配, 为了进一步提高匹配的完备性, 本文在SAING算法的基础上, 采用Reverse策略提出了MSAING算法.该算法通过对模式串结构以及符号集
证明:给定序列串
证明:形如
证明:给定序列串
模式串
例2:给定序列串
Search table when
由于
Search table when
例2中的模式串
Pattern matching when
由例2可知, 通过对模式串
1) 模式串
2) 模式串
3) 模式串
4) 模式串
输入:
输出:最大的出现数目|
1. if (
2.
3. end if
4. if (
5.
6.
7. if (
8.
9. end if
10. if (
11. if (
12.
13. end if
14. end if
15. end if
16. if (!
17. if (
18.
19. end if
20. end if
21.调用算法4:SAING算法
22. return |
通过对以上5种算法的介绍可知, MSAING算法的时间复杂度等于SAING算法复杂度.SAING算法时间主要消耗在定位阶段、Forward阶段和Backward阶段.其中, 定位阶段时间复杂度为
证明:为了方便证明, 不妨证明其逆否命题.假设
由于MSAING算法在Forward阶段将所有满足条件的位置进行标记, Backward阶段是由
证明:利用反证法进行证明.设
●
●
●
若
所以, ∃0≤
则
因此,
下面分两种情况分别加以讨论.
1.当
2.当
(1) 当
所以, 当
(2) 当
由于
所以,
所以, 由(ⅰ)、(ⅱ)得:
所以, ∃
形式进行分析:
①
②
③
④
上述4种情况表明,
8,
实验数据集特征
Characteristic of experimental data
序列数据库 | 数据集名称 | 序列类型 | 序列个数 | 总长度 |
SDB1 | DNA片段 | DNA片段 | 12 | 327 535 |
SDB2 | WO02059377 | DNA序列 | 70 | 190 533 |
SDB3 | ASTRAL95_1_161 | 蛋白质序列 | 507 | 91 875 |
SDB4 | 文献[ |
文本字符串 | 1 | 8 191 |
SDB1真实生物数据片段
Sequences of real biological data in SDB
序号 | 位点 | 片段长度 |
CY058560 | 844 | |
CY058557 | 982 | |
CY058558 | 1 418 | |
CY058559 | 1 516 | |
CY058556 | 1 720 | |
CY058561 | 2 169 | |
CY058563 | 2 286 | |
CY058562 | 2 299 | |
AX829178 | 5 393 | |
AX829174 | 10 011 | |
AB038490 | 131 892 | |
AL158070 | 167 005 |
DNA控制RNA的转录以及遗传信息, 因此, 通过对DNA片段进行特定的模式匹配, 找出匹配解的个数, 对于致病基因以及遗传信息的检测、病毒传播的预防等起着重要的作用.一般间隙模式匹配有利于灵活地找出模式匹配个数的精确解, 通过对匹配解的数目分析, 对生物学中基因遗传的研究具有重要的价值.下面将具体介绍MSAING以及对比算法在DNA片段上的性能.为了分别对比测试MSAING算法在模式串不存在重复字符以及存在重复字符时的求解性能, 选取了
模式串
Patterns
序号 | 模式串 |
7种算法在
Comparison of the number of occurrences of
算法名称 | 模式串中不存在重复字符 | 模式串中存在重复字符 | |||||||
SAIL_Gen | 36 327 | 23 885 | 13 257 | 31 132 | 10 961 | 8 289 | 17 790 | 18 192 | 18 401 |
RSAIL_Gen | 36 327 | 23 885 | 13 257 | 31 132 | 10 961 | 8 289 | 17 790 | 18 192 | 18 342 |
SGSP_Gen | 35 876 | 23 520 | 13 238 | 30 667 | 13 548 | 10 004 | 17 766 | 18 096 | 19 033 |
SBO_Gen | 36 267 | 23 793 | 13 250 | 30 984 | 14 101 | 10 528 | 18 056 | 18 831 | 19 204 |
RBCT_Gen | 36 253 | 23 763 | 13 213 | 30 947 | 14 125 | 10 593 | 18 052 | 18 822 | 19 433 |
DCNP | 36 267 | 23 793 | 13 250 | 30 984 | 14 152 | 10 673 | 18 070 | 18 865 | 19 898 |
MSAING | 36 327 | 23 885 | 13 257 | 31 132 | 14 158 | 10 786 | 18 094 | 20 136 | 20 166 |
7种算法在
Comparison of the running time on
算法名称 | 模式串中不存在重复字符 | 模式串中存在重复字符 | |||||||
SAIL_Gen | 0.98 | 0.93 | 0.85 | 0.82 | 4.17 | 5.54 | 2.67 | 2.03 | 2.05 |
RSAIL_Gen | 1.26 | 1.17 | 1.98 | 1.89 | 4.21 | 6.36 | 3.23 | 3.18 | 3.56 |
SGSP_Gen | 640.9 | 521.9 | 491.21 | 166.3 | 2 759.1 | 3 175.2 | 1 796.7 | 1 243.8 | 868.96 |
SBO_Gen | 838.5 | 790.9 | 720.3 | 315.0 | 3 163.3 | 3 439 | 1 796.7 | 1 552.1 | 478.84 |
RBCT_Gen | 0.82 | 0.78 | 0.83 | 0.89 | 3.25 | 4.12 | 1.05 | 1.14 | 1.39 |
DCNP | 852 | 802.4 | 781.71 | 361.1 | 3 562.2 | 3 887.4 | 2 065.6 | 1 635.7 | 1 208.6 |
MSAING | 0.93 | 0.83 | 0.81 | 0.8 | 7.2 | 9.69 | 3.14 | 2.1 | 3.37 |
(1) 在模式串中不存在重复字符的情况下, MSAING, SAIL_Gen, RSAIL_Gen均属于完备算法.文献[
(2) 在模式串中有重复字符的情况下, MSAING算法性能最好, DCNP算法性能次之, SAIL_Gen算法性能最差.
(3) 根据
通过将MSAING算法与其他各种算法在SDB1数据集上进行对比可知:MSAING算法的匹配解比DCNP提高了2%, 比SAIL_Gen提高了12%.MSAING算法是通过Reverse策略提高匹配解的数目的, 下面将通过实验进一步验证Reverse机制的有效性.
为了验证Reverse机制的有效性, 在数据集SDB1上选取需要转置的模式串
Reverse机制有效性验证
Validation of effectiveness of Reverse strategy
本实验验证了Reverse策略的有效性, 使匹配解的平均数目提高了5.6%.下面将通过在序列数据库中比较算法的性能, 证明MSAING算法能够在较大规模的数据库上进行有效的模式匹配.
随着蛋白质产品在人们日常生活中应用的普及, 蛋白质检测在生物学领域得到了广泛的研究.食品中营养蛋白的检测、药物中蛋白酶以及胰岛素的检测以及蛋白质中氨基酸序列的检测等, 都需要对蛋白质序列进行某些特定的模式串匹配.一般间隙的模式匹配能够灵活地找出匹配解的数量, 在生物学中某种蛋白质含量的监测中有着重要的应用.下面的实验将比较MSAING与其他算法在DNA库以及蛋白质库中的性能.
为了更有效地对比各种算法匹配解的个数以及运行的速度, 在DNA序列库WO02059377、蛋白质序列库ASTRAL95_1_161上做了对比实验.
在DNA序列库上的模式匹配, 模式串为
DNA序列库上出现的数目对比
Comparison of the number of occurrences on DNA sequence database
DNA序列库上运行时间对比
Comparison of the running time on DNA sequence database
在蛋白质序列库上, 分别选择长度为1~6、间隙为[-2, 7]的模式串, 其中, 长度为1模式串为{
在蛋白质序列库上出现的对比
Comparison of the number of occurrences on protein sequence database
在蛋白质序列库上各算法的出现与MSAING算法的百分比
Percentage of each algorithm with MSAING on protein sequence database
蛋白质序列库中运行时间对比
Comparison of the running time on protein sequence database
在生物序列上的实验, 验证了MASING算法进行较大规模数据库模式匹配时的性能.为了进一步证明该算法解决某些实际问题的有效性, 本文把它应用在文本信息的检索中.
在文本信息检索中考虑一般间隙更具有实际意义, 例如在文献[
以文献[
非负间隙与一般间隙出现个数比较
Comparison of the number of occurrences about no-negative gap with general gap
模式 | 非负间隙 | 一般间隙 |
Data mining | 2 | 3 |
Closed subsequence | 3 | 4 |
Frequent closed subsequence | 4 | 9 |
非负间隙与一般间隙解的出现对比
Comparison of the number of occurrences about no-negative gap with general gap
本文提出了一般间隙与one-off条件约束的模式匹配问题——SPMGOO问题.该问题的研究允许用户更加灵活地设定模式串.该问题具有如下特点:间隙可以为负; 同时, 序列串中任何字符最多只能使用1次.本文把线性表应用于该问题的求解, 并基于线性表的结构提出了MSAING算法.算法首先采用Reverse策略使模式与序列达到最佳的匹配状态, 克服了某些算法容易陷入局部最优的缺点; 其次, 利用线性表的结构使匹配过程中的时间和空间消耗大为减少, 并利用回溯的方法提高匹配的成功率; 最后, 根据
本文只是对一般间隙与one-off条件的模式匹配问题进行了研究, 而模式匹配是序列模式挖掘的基础, 因此, 下一步将对一般间隙的序列模式挖掘问题进行研究.该研究将有助于挖掘更多有价值的频繁模式.此外, 在实际应用中有很多模式匹配是近似模式匹配, 这不但具有实际意义, 而且研究难度也会更大, 这些问题均是未来研究的方向.
Wu XD, Zhu XQ, He Y, Arslan AN. PMBC:Pattern mining from biological sequences with wildcard constraints. Computers in Biologyand Medicine, 2013, 43(5):481-492.[doi:10.1016/j.compbiomed.2013.02.006]
10.1145/2783258.2783394]]]>
10.1145/2783258.2783306]]]>
Chou CP, Jea KF, Liao HH. A syntactic approach to twig-query matching on XML streams. Journal of Systems and Software, 2011, 84(6):993-1007.[doi:10.1016/j.jss.2011.01.033]
Manber U, Baeza-Yates R. An algorithm for string matching with a sequence of don't cares. Information Processing Leters, 1991, 37(3):133-136.[doi:10.1016/0020-0190(91)90032-d]
10.1007/978-3-642-16321-0_40]]]>
Fischer MJ, Paterson MS. String matching and other products. In: Proc. of the String-Matching and Other Products. Cambridge: Massachusetts Institute of Technology, 1973. 113-125.
Chen G, Wu XD, Zhu XQ, Arslan AN, He Y. Efficient string matching with wildcards and length constraints. Knowledge and Information Systems, 2006, 10(4):399-419.[doi:10.1007/s10115-006-0016-8]
10.1109/ICDE.2007.367918]]]>
Liu YL, Wu XD, Hu XG, Gao J. A matching algorithm in PMWL based on CluTree. New Generation Computing, 2014, 32(2):95-122.[doi:10.1007/s00354-014-0201-3]
10.1007/11880561_22]]]>
Fredriksson K, Grabowski S. Efficient algorithms for pattern matching with general gaps, character classes, and transposition invariance. Information Retrieval, 2008, 11(4):335-357.[doi:10.1007/s10791-008-9054-z]
10.13328/j.cnki.jos.004707]]]>
http://www.jos.org.cn/1000-9825/4707.htm[doi:10.13328/j.cnki.jos.004707]]]>
Wu YX, Fu S, Jiang H, Wu XD. Strict approximate pattern matching with general gaps. Applied Intelligence, 2014, 42(3):1-15.[doi:10.1007/s10489-014-0612-3]
10.3724/SP.J.1001.2013.04381]]]>
http://www.jos.org.cn/1000-9825/4381.htm[doi:10.3724/SP.J.1001.2013.04381]]]>
Kalai A. Efficient pattern-matching with don't cares. In: Proc. of the 13th ACM-SIAM Symp. on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2002. 655-656.
10.1007/3-540-60044-2_46]]]>
Wu YX, Wang LL, Ren JD, Ding W, Wu XD. Mining sequential patterns with periodic wildcard gaps. Applied Intelligence, 2014, 41(1):99-116.[doi:10.1007/s10489-013-0499-4]
Myers EW. Approximate matching of network expressions with spacers. Journal of Computational Biology, 2009, 3(1):33-51.[doi:10.1089/cmb.1996.3.33]
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).[doi:10.3724/SP.J.1016.2011.01452]
武优西, 吴信东, 江贺, 闵帆.一种求解MPMGOOC问题的启发式算法.计算机学报, 2011, 34(8):1452-1462.[doi:10.3724/SP.J. 1016.2011.01452]
Lam H, Morchen F, Fradkin D, Calders T. Mining compressing sequential patterns. Statistical Analysis and Data Mining, 2012, 7(1):34-52.[doi:10.1002/sam.11192]
10.1109/BIBM.2007.48]]]>
10.1109/ICDE.2009.104]]]>
10.1109/GrC.2010.156]]]>
Zhou K. Mining sequential patterns with periodic general gap constraints[MS. Thesis]. Shijiazhuang: Hebei University of Technology, 2014(in Chinese with English abstract).
周坤. 一般周期间隙约束的序列模式挖掘[硕士学位论文]. 石家庄: 河北工业大学, 2014.
10.1137/1.9781611972788.28]]]>