Computer Science ›› 2015, Vol. 42 ›› Issue (4): 244-248.doi: 10.11896/j.issn.1002-137X.2015.04.050

Previous Articles     Next Articles

Dynamic Pruning Algorithm for Pattern Matching with Wildcards and Length Constraints

WANG Hai-ping, DAI Wei and GUO Dan   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Recently,with the development of bioinformatics,network security and information retrieval,wildcards are playing an increasingly key role in pattern ma-tching problems.Among these,the challenging problem of pattern ma-tching with wildcards and length constraints (PMWL) further extends the flexibility of pattern matching,thus bringing convenience to the user but producing the expense of higher computational complexity.Therefore,how to get a better matching solution in polynomial time has been well studied and developed.Based on the previous work,we presented a heuristic Pawn algorithm for PMWL.After transforming the PMWL problem into path search problem,a dynamic strategy is adopted with a pruning procedure in an alternating iterative manner.Experiments demonstrate that,comparing with the state-of-the-art algorithm,Pawn algorithm can improve the number of matching occurrences in most cases of 196 artificial patterns with certain characteristic and the DNA sequences.

Key words: Pattern matching,Wildcard,Pruning,Constraints

[1] Navarro G,Raffinot M.Flexible pattern matching in strings:Practical on-line search algorithms for texts and biological sequences[M].Cambridge,UK:Cambridge University Press,2002
[2] Han J,Cheng H,Xin D,et al.Frequent pattern mining:CurrentStatus and Future Directions[J].Data Mining and Knowledge Discovery,2007,15(1):55-86
[3] Fischer M J,Paterson M S.String matching and other products[R].Complexity of computation,1974:113-125
[4] Cole J R,Chai B,Marsh T L,et al.The ribosomal database project(RDP-11):Sequences and tools for high-throughput rRNA analysis[J].Nucleic Acids Research,2005,33 (1):294-296
[5] 徐小双,冯玉才,王锋,等.路径分区编码优化小枝查询[J].计算机科学,2010,37(3):182-204
[6] Xie F,Wu X D,Hu X G,et al.Sequential Pattern Mining with Wildcards[C]∥22nd IEEE International Conference on Tools with Artificial Intelligence (ICTAI).2010:241-247
[7] Guo D,Hu X G,Xie F,et al.Pattern matching with wildcards and gap-length constraints based on a centrality-degree graph[J].Applied Intelligence,2013,39:57-74
[8] Bille P,Gortz I,Vildhoj H,et al.String matching with variable length gaps[J].Theoretical Computer Science,2012,443:25-34
[9] Chen G,Wu X D,Zhu X Q,et al.Efficient String Matching with Wildcards and Length Constraints[J].Knowledge and Information Systems,2006,10(4):399-419
[10] Min F,Wu X D,Lu Z.Pattern matching with independent wildcard gaps[C]∥Eighth IEEE International Conference on Dependable,Autonomic and Secure Computing (DASC-2009).2009:194-199
[11] Zhang M,Kao B,Cheung D,et al.Mining periodic patterns with gap requirement from sequences[C]∥Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data.2005:622-633
[12] Zhu X Q,Wu X D.Mining complex patterns across sequences with gap requirements[C]∥Proceedings of 2007 International Joint Conference on Artificial Intelligence.2007:2934-2940
[13] Guo D,Hong X L,Hu X G,et al.A Bit-Parallel Algorithm for Sequential Pattern Matching with Wildcards[J].Cybernetics and Systems,2011,42(6):382-401
[14] 王海平,胡学钢,谢飞,等.模式特征对带有通配符和长度约束的模式匹配问题的影响[J].模式识别与人工智能,2012,25(6):1013-1021
[15] 运正佳,李铁男,杨晓春.支持带有通配符的字符串匹配算法[J].计算机科学与探索,2010,4(11):984-995
[16] Muthukrishnan S,Palem K.Non-standard stringology:algo-rithms and complexity[C]∥Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing.1994:770-779
[17] Manber U,Baeza-Yates R.An algorithm for string matchingwith a sequence of don’t cares[J].Information Processing Letters,1991,37(3):133-136
[18] Zhu X Q,Wu X D.Discovering relational patterns across multiple databases[C]∥Proceedings of IEEE 23rd International Conference on Data Engineering.2007:726-735
[19] Zhang M,Kao B,Cheung D W,et al.Mining periodic patterns with gap requirement from sequences[C]∥Proceedings of ACM SIGMOD.2005:623-633

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .