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

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