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

摘要：

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

关键词：模式匹配、退化模式、算法、DNA序列、生物信息

所属期刊栏目：28

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

资助基金：福建省教育厅资助项目JA08033

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

页数：共7页

页码：26-32