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

作者：强继朋; 谢飞; 高隽; 胡学钢; 吴信东

来源：自动化学报, 2014, (11): 2499-2511.

• 通配符
• 模式匹配
• 位并行
• 基因序列 Wildcard
• pattern matching
• bit-parallel
• genetic sequence

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

• 出版日期2014
• 单位合肥工业大学; 合肥师范学院; 佛蒙特大学