求解PMWOC问题的算法

• 作者: 侯宝剑 叶明全 张浩
• 来源期刊: 安徽师范大学学报（自然科学版）
• 学科: 工学
• 关键词: 模式匹配 通配符 One-Off条件
• 年，卷（期）: 2014,（3）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 242-246,251
• 页数: 6页
• 分类号: TP301
• 字数: 5024字
• 语种: 中文

摘要

带有灵活通配符和One-Off条件的模式匹配问题(Pattern Matching with flexible Wildcardsand One-off Condition,PMWOC)在生物信息学、文本检索和数据流等领域都有着广泛的应用.给定带灵活通配符的模式和文本,在one-off条件下,已有算法不能得到模式在文本中的完备解,即模式在文本中最大的出现数目.为此,设计一个求解该问题的算法:首先,利用动态规划的思想去获得模式的所有出现及匹配位置;然后,根据模式的完备解至少包含任意一次出现中的一个位置的思想获得模式解的集合.通过DNA数据进行实验,实验结果显示相对于已有的算法,该算法能够获得最多的出现解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	叶明全	皖南医学院公共基础学院	86	416	11.0	17.0
2	张浩	皖南医学院公共基础学院	15	46	3.0	6.0