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

摘要：

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

关键词：模式匹配、通配符、剪枝、约束

所属期刊栏目：42

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金:港澳学者合作研究基金项目61229301;国家自然科学基金项目60828005;博士后面上基金项目2012M511403;安徽省自然科学基金2013AKZR0082

在线出版日期：2015-05-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：244-248