戴胜冬，杨　昆

(杭州电子科技大学计算机学院，浙江 杭州 310018)

摘要：分析了DNA序列特征计算过程中的特殊性，提出了一种基于“空间换时间”的模式匹配算法，设计了以map数据结构来存储中间结果的方案，使得扫描DNA序列一次即可同时计算所有元组模式在该序列中出现的次数。实验结果及分析表明，算法提升了DNA序列模式特征计算的效率，较好地解决了计算DNA序列模式特征的问题。

关键词：算法；生物信息学；DNA序列；模式匹配

DOI: 10.13954/j.cnki.hdu.2015.01.018

计算DNA序列模式特征的匹配算法

戴胜冬，杨昆

(杭州电子科技大学计算机学院，浙江 杭州 310018)

摘要：分析了DNA序列特征计算过程中的特殊性，提出了一种基于“空间换时间”的模式匹配算法，设计了以map数据结构来存储中间结果的方案，使得扫描DNA序列一次即可同时计算所有元组模式在该序列中出现的次数。实验结果及分析表明，算法提升了DNA序列模式特征计算的效率，较好地解决了计算DNA序列模式特征的问题。

关键词：算法；生物信息学；DNA序列；模式匹配

DOI:10.13954/j.cnki.hdu.2015.01.018

收稿日期：2014-06-26

基金项目：国家自然科学基金资助项目(60903086)

通信作者：

作者简介：戴胜冬(1990-)，男，安徽巢湖人，在读研究生，表观遗传数据分析和挖掘.杨昆副教授，E-mail: yangkun@hdu.edu.cn.

中图分类号：TP311.1

文献标识码：：A

文章编号：：1001-9146(2015)01-0088-05

Abstract:This paper analyzed the specificity of DNA feature calculation， proposed an algorithm based on “space for time” idea， which designed a scheme of using map data structure to store the intermediate calculation results， so that each DNA sequence needs to be scanned just once to calculate all pattern features. Experiment results and analysis show that the algorithm can effectively improve the efficiency of calculating DNA feature， and better solve the problems common pattern calculating algorithms have in calculating DNA feature.

0引言

DNA序列特征的计算在生物信息学的研究中具有着重要的基础性地位，具体的序列特征有很多类型，而元组模式是其中一个重要且常见的类别[1-4]。对DNA甲基化状态预测就需要计算DNA序列中元组模式出现的次数[5-10]。……