| 摘 要: 模体发现是计算机科学中的一个较为重要且具有一定挑战的问题，主要用于定位DNA序列集中的保守信 号。首先，分析了已有的基于图聚类的模体发现算法MCL-WMR，讨论了它存在的两个缺陷。其次，针对这两个缺陷 提出了MCL-WMR的改进算法iMCL-WMR。实验结果表明，所提DNA模体发现算法的时间性能好于所比较的算法 MCL-WMR和qPMS9，能够在1个小时以内处理数百条输入序列，而且能够应对某些输入序列不含模体实例的测试 数据。 |
| 关键词: 保守信号；模体发现；图聚类 |
|
中图分类号: TP301.6
文献标识码: A
|
|
| A New Algorithm for Identifying Conserved Signals in Sequence Sets |
|
LIU Chang
|
( Department of Information and Communication, Qinhuangdao Branch of State Grid Jibei Electric Power Company, Qinhuangdao 066000, China)
|
| 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 |
