一种带有通配符和长度约束模式匹配问题的动态剪枝算法

Dynamic Pruning Algorithm for Pattern Matching with Wildcards and Length Constraints

近年来,随着生物信息学、信息检索等领域的发展,串模式匹配问题被不断扩展。其中,具有代表性的是在模式中引入可变长度的通配符而形成带有通配符的模式匹配(PMWL)。该问题定义的灵活性给用户提供了方便,却也造成了求解上的困难。因此,如何在多项式时间内得到更好的匹配解成为研究的焦点。提出了一种启发式的小兵算法。小兵算法通过将PMWL问题转化为路径搜索问题,并借鉴动态剪枝思想,在算法搜索的过程中动态地将不可能的匹配位置剪枝,从而提高解的质量。实验在真实DNA序列上进行,并人工生成了196个模式。结果表明,相比于目前最有效的SAIL算法,小兵算法在绝大多数的尾部有重复字符的模式中可以获得更好的匹配解。

Recently,with the development of bioinformatics,network security and information retrieval,wildcards are playing an increasingly key role in pattern ma-tching problems.Among these,the challenging problem of pattern matching with wildcards and length constraints（PMWL）further extends the flexibility of pattern matching,thus bringing convenience to the user but producing the expense of higher computational complexity.Therefore,how to get a better matching solution in polynomial time has been well studied and developed.Based on the previous work,we presented a heuristic Pawn algorithm for PMWL.After transforming the PMWL problem into path search problem,a dynamic strategy is adopted with a pruning procedure in an alternating iterative manner.Experiments demonstrate that,comparing with the state-of-the-art algorithm,Pawn algorithm can improve the number of matching occurrences in most cases of 196 artificial patterns with certain characteristic and the DNA sequences.