基于BM方法的退化模式匹配算法

• 作者: 林劼 林舒晔
• 来源期刊: 福建师范大学学报（自然科学版）
• 学科: 工学
• 关键词: 模式匹配 退化模式 算法 DNA序列 生物信息
• 年，卷（期）: 2012,（5）
• 页码范围: 26-32
• 分类号: TP305
• 字数: 4066字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-5277.2012.05.006

摘要

退化模式匹配问题在生物信息学中具有重要应用意义,但由于该问题的计算复杂度高,现有的算法均难以在实际中应用.在分析退化模式的特点以及经典的Boyer-Moore (BM)算法的基础上,提出基于BM算法框架解决退化模式匹配问题的方法.在计算偏移数组的预处理过程中,定义兼容规则并计算偏移数组,并将其应用在查找阶段,提高退化模式的匹配速度.在平均情况下,该算法提供了线性的模式匹配速度,在实际应用中得到良好的效果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	林劼	福建师范大学软件学院	25	138	6.0	11.0
2	林舒晔	福建农林大学作物科学学院	5	7	1.0	2.0