一种基于位置信息的高效DNA序列挖掘算法

杨静欣 毛国君

(中央财经大学信息学院 北京 100081)

一种基于位置信息的高效DNA序列挖掘算法

杨静欣 毛国君

(中央财经大学信息学院 北京 100081)

类Apriori算法在产生频繁模式时需要多次扫描数据库，并且产生大量的候选集；FreeSpan和PrefixSpan等基于投影数据库的算法在产生频繁模式时会产生大量的投影数据库，占用很多内存空间，这些都造成了很大的冗余。针对以往序列挖掘算法存在的不足，提出一种高效的序列挖掘算法——基于位置信息的序列挖掘算法PBSMA(Position-Based Sequence Mining Algorithm)。PBSMA算法通过记录频繁子序列的位置信息来减少对数据库的扫描，利用位置信息逐渐扩大频繁模式的长度，并且借鉴关联矩阵的思想和PrefixSpan算法中前缀的概念，深度优先去寻找更长的关键模式。实验结果证明，无论在时间还是空间上，PBSMA算法都比PrefixSpan算法更高效。

序列挖掘 DNA序列 位置信息 关联矩阵 前缀

0 引 言

序列挖掘是数据挖掘中非常重要的一个研究领域，一般是指从序列数据库中发现蕴含在其中的，相对于时间或者其他顺序高频率出现的子序列，并称这个高频子序列为序列模式。序列挖掘的概念最早由Agrawal等在针对超市中购物篮数据的分析中提出[1]，目的是发现某一时间段内客户的购买活动规律。序列挖掘经过近20年的发展，其应用范围已经不再局限于交易数据库，在商业，消费者行为分析，股票趋势预测，生物序列分析，Web挖掘等领域都有重要的应用。商业组织利用序列模式去研究客户购买行为模式特……