带任意长度通配符的模式匹配

• 作者: 吴信东 强继朋 胡学钢 谢飞 高隽
• 来源期刊: 自动化学报
• 关键词: 通配符 模式匹配 位并行 基因序列
• 年，卷（期）: 2014,（11）
• 所属期刊栏目: 论文与报告
• 页码范围: 2499-2511
• 页数: 13页
• 字数: 13766字
• 语种: 中文
• DOI: 10.3724/SP.J.1004.2014.02499

摘要

基因序列中,许多病毒并不是简单的直接复制自己,而是相邻字符间插入或者删除序列片段,如何从序列数据中检索这些病毒具有重要的研究价值。提出了一个更普遍的问题,带任意长度通配符的模式匹配问题(Pattern matching with arbitrary-length wildcards, PMAW),这里模式中不仅可以有多个通配符约束,而且每个通配符的约束可以是两个整数,也可以从整数到无穷大。给定序列S 和带通配符的模式P,目标是从S 中检索P 的所有出现和每一次出现的匹配位置,并且要求任意两次出现不能共享序列中同一位置。为了有效地解决该问题,设计了两个基于位并行的匹配算法MOTW (Method of ocurrence then window)算法和MWTO (Method of window then ocurrence)算法。同时, MWTO 算法进行细微改动就可以满足全局长度约束。实验结果既验证了算法求解问题的正确性,又验证了比相关的模式匹配算法具有更好的时间性能。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡学钢	合肥工业大学计算机与信息学院	314	3156	27.0	39.0
2	高隽	合肥工业大学计算机与信息学院	160	1689	22.0	34.0
3	谢飞	合肥师范学院计算机科学与技术系	22	238	8.0	14.0
4	强继朋	合肥工业大学计算机与信息学院	2	10	2.0	2.0