福建师范大学学报（自然科学版）
福建師範大學學報（自然科學版）
복건사범대학학보（자연과학판）
JOURNAL OF FUJIAN TEACHERS UNIVERSITY (NATURAL SCIENCE EDITION)
2012年
5期
26-32
,共7页
模式匹配%退化模式%算法%DNA序列%生物信息
模式匹配%退化模式%算法%DNA序列%生物信息
모식필배%퇴화모식%산법%DNA서렬%생물신식
退化模式匹配问题在生物信息学中具有重要应用意义,但由于该问题的计算复杂度高,现有的算法均难以在实际中应用.在分析退化模式的特点以及经典的Boyer-Moore (BM)算法的基础上,提出基于BM算法框架解决退化模式匹配问题的方法.在计算偏移数组的预处理过程中,定义兼容规则并计算偏移数组,并将其应用在查找阶段,提高退化模式的匹配速度.在平均情况下,该算法提供了线性的模式匹配速度,在实际应用中得到良好的效果.
退化模式匹配問題在生物信息學中具有重要應用意義,但由于該問題的計算複雜度高,現有的算法均難以在實際中應用.在分析退化模式的特點以及經典的Boyer-Moore (BM)算法的基礎上,提齣基于BM算法框架解決退化模式匹配問題的方法.在計算偏移數組的預處理過程中,定義兼容規則併計算偏移數組,併將其應用在查找階段,提高退化模式的匹配速度.在平均情況下,該算法提供瞭線性的模式匹配速度,在實際應用中得到良好的效果.
퇴화모식필배문제재생물신식학중구유중요응용의의,단유우해문제적계산복잡도고,현유적산법균난이재실제중응용.재분석퇴화모식적특점이급경전적Boyer-Moore (BM)산법적기출상,제출기우BM산법광가해결퇴화모식필배문제적방법.재계산편이수조적예처리과정중,정의겸용규칙병계산편이수조,병장기응용재사조계단,제고퇴화모식적필배속도.재평균정황하,해산법제공료선성적모식필배속도,재실제응용중득도량호적효과.
