带通配符的模式匹配问题及其解空间特征分析

摘要：

随着生物信息学、信息检索等领域的发展,带有通配符和长度约束的模式匹配问题引起了广泛关注.该问题扩展了精确模式匹配问题,使匹配更加灵活,同时也增加了匹配的复杂性,极大地提高了非线性匹配算法的复杂度.求解该问题的匹配算法的效率与问题的解空间密切相关,而目前针对该问题的解空间及其特征尚缺乏系统的研究.鉴于此,描述了该问题的解空间,并分析了解空间的可分性.之后,提出解空间划分算法SPLIT,并分析了SPLIT的时间复杂性.实验部分以3个匹配算法为对照,在真实DNA数据集下,使用了5109组模式.实验结果表明,SPLIT不影响匹配解的结构,且可以有效降低非线性匹配算法的时间消耗.

关键词：解空间、分割、模式匹配、通配符

所属期刊栏目：41

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

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

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

页数：共6页

页码：269-273,310