%0 Journal Article
%T 带任意长度通配符的模式匹配
%A 强继朋
%A 谢飞
%A 高隽
%A 胡学钢
%A 吴信东
%J 自动化学报
%P 2499-2511
%D 2014
%R 10.3724/SP.J.1004.2014.02499
%X ？基因序列中,许多病毒并不是简单的直接复制自己,而是相邻字符间插入或者删除序列片段,如何从序列数据中检索这些病毒具有重要的研究价值.提出了一个更普遍的问题,带任意长度通配符的模式匹配问题(Patternmatchingwitharbitrary-lengthwildcards,PMAW),这里模式中不仅可以有多个通配符约束,而且每个通配符的约束可以是两个整数,也可以从整数到无穷大.给定序列S和带通配符的模式P,目标是从S中检索P的所有出现和每一次出现的匹配位置,并且要求任意两次出现不能共享序列中同一位置.为了有效地解决该问题,设计了两个基于位并行的匹配算法MOTW(Methodofocurrencethenwindow)算法和MWTO(Methodofwindowthenocurrence)算法.同时,MWTO算法进行细微改动就可以满足全局长度约束.实验结果既验证了算法求解问题的正确性,又验证了比相关的模式匹配算法具有更好的时间性能.
%K 通配符
%K 模式匹配
%K 位并行
%K 基因序列
%U http://www.aas.net.cn/CN/abstract/abstract18526.shtml