Pattern Matching with Flexible Wildcards

• Published in: Journal of computer science and technology 2014-09, Vol.29 (5), p.740-750
• Main Author: 吴信东 强继朋 谢飞
• Format: Article
• Language: English
• Subjects: Algorithms; Artificial Intelligence; Bioinformatics; Computer Science; Counting; Data mining; Data Structures and Information Theory; Flexibility; Information retrieval; Information Systems Applications (incl.Internet); Matching; Pattern analysis; Pattern matching; PMW; Software Engineering; State of the art; Survey; Theory of Computation; 不确定性; 信息检索; 匹配使用; 模式匹配; 模式挖掘; 生物信息学; 通配符
• ISSN: 1000-9000; 1860-4749
• DOI: 10.1007/s11390-014-1464-3

Pattern matching with wildcards（PMW） has great theoretical and practical significance in bioinformatics,information retrieval, and pattern mining. Due to the uncertainty of wildcards, not only is the number of all matches exponential with respect to the maximal gap flexibility and the pattern length, but the matching positions in PMW are also hard to choose. The objective to count the maximal number of matches one by one is computationally infeasible. Therefore,rather than solving the generic PMW problem, many research efforts have further defined new problems within PMW according to different application backgrounds. To break through the limitations of either fixing the number or allowing an unbounded number of wildcards, pattern matching with flexible wildcards（PMFW） allows the users to control the ranges of wildcards. In this paper, we provide a survey on the state-of-the-art algorithms for PMFW, with detailed analyses and comparisons, and discuss challenges and opportunities in PMFW research and applications.