一种新的序列集保守信号识别算法

刘畅

摘 要：模体发现是计算机科学中的一个较为重要且具有一定挑战的问题，主要用于定位DNA序列集中的保守信号。首先，分析了已有的基于图聚类的模体发现算法MCL-WMR，讨论了它存在的两个缺陷。其次，针对这两个缺陷提出了MCL-WMR的改进算法iMCL-WMR。实验结果表明，所提DNA模体发现算法的时间性能好于所比较的算法MCL-WMR和qPMS9，能够在1个小时以内处理数百条输入序列，而且能够应对某些输入序列不含模体实例的测试数据。

关键词：保守信号；模体发现；图聚类

中图分类号：TP301.6 文献标识码：A

Abstract：Motif discovery is an important and challenging issue in computer science，mainly used to locate conserved signals in a set of DNA sequences.At first，a graph clustering based motif discovery algorithm MCL-WMR is analyzed and its two drawbacks are discussed.Then，in order to overcome the two drawbacks，an improved algorithm of MCL-WMR，named as iMCL-WMR，is proposed.Experimental results show that，with a better time performance than the compared algorithms of MCL-WMR and qPMS9，the proposed algorithm can process hundreds of sequences within one hour and deal with any case that some input sequences do not contain motif instances.

Keywords：conserved signals；motif discovery；graph clustering

1 引言（Introduction）

序列集中保守的信号称为模体。模体发现就是在一组给定的序列集合中找出未知的模体，是很多重要的数据挖掘任务的第一步[1-3]。本文主要关注DNA序列集合中的模体发现问题[4]，可用于定位许多具有重要功能的基因区域。问题形式化描述如下[5]：

给定字符表{A，C，G，T}上的n条长为m的序列集合S={sl，s2，…，sn}，目标是找出一个长为l（0

此问题是一个NP难问题[6]，当前已涌现了许多求解算法[7]。一类算法通过穷尽所有可能的l-mer来找出潜在的模体[8，9]。另一类算法将模体视为一个位置频率矩阵（Position Frequency Matrix，PFM）[10]，一般对初始的PFM进行迭代优化来得到模体。还有一类算法将模体发现问题抽象为图聚类问题，比如MCL-WMR[11]。

由于此问题的NP难特性，目前它仍然是一个开放性的难题；此外，当前待处理的模体发现的数据规模在变大[12]，许多现有算法在时间性能上达不到实用要求。本文通过分析和改进MCL-WMR，提出了一种新的模体发现算法，它的时间性能更为高效且能够处理某些输入序列不含模体实例的情况。……