Department of Computer Science and Engineering, Chinese University of Hong Kong, Hong Kong.
IEEE/ACM Trans Comput Biol Bioinform. 2010 Oct-Dec;7(4):654-68. doi: 10.1109/TCBB.2009.25.
Finding Transcription Factor Binding Sites, i.e., motif discovery, is crucial for understanding the gene regulatory relationship. Motifs are weakly conserved and motif discovery is an NP-hard problem. We propose a new approach called Cluster Refinement Algorithm for Motif Discovery (CRMD). CRMD employs a flexible statistical motif model allowing a variable number of motifs and motif instances. CRMD first uses a novel entropy-based clustering to find complete and good starting candidate motifs from the DNA sequences. CRMD then employs an effective greedy refinement to search for optimal motifs from the candidate motifs. The refinement is fast, and it changes the number of motif instances based on the adaptive thresholds. The performance of CRMD is further enhanced if the problem has one occurrence of motif instance per sequence. Using an appropriate similarity test of motifs, CRMD is also able to find multiple motifs. CRMD has been tested extensively on synthetic and real data sets. The experimental results verify that CRMD usually outperforms four other state-of-the-art algorithms in terms of the qualities of the solutions with competitive computing time. It finds a good balance between finding true motif instances and screening false motif instances, and is robust on problems of various levels of difficulty.
发现转录因子结合位点，即基序发现，对于理解基因调控关系至关重要。基序是弱保守的，基序发现是一个 NP 难问题。我们提出了一种新的方法，称为 motif 发现的聚类精炼算法（CRMD）。CRMD 采用了灵活的统计基序模型，允许基序和基序实例的数量可变。CRMD 首先使用一种新颖的基于熵的聚类方法，从 DNA 序列中找到完整且良好的起始候选基序。然后，CRMD 采用有效的贪婪精炼方法，从候选基序中搜索最优基序。这种精炼方法速度很快，并且根据自适应阈值来改变基序实例的数量。如果每个序列只有一个基序实例的问题，则可以进一步提高 CRMD 的性能。通过适当的基序相似性测试，CRMD 也能够找到多个基序。CRMD 已经在合成和真实数据集上进行了广泛的测试。实验结果验证了，在计算时间有竞争力的情况下，CRMD 通常在解决方案的质量方面优于其他四种最先进的算法。它在寻找真实基序实例和筛选虚假基序实例之间找到了良好的平衡，并且对各种难度级别的问题具有鲁棒性。
