A Heuristic Cluster-Based EM Algorithm for the Planted (L, d) Problem
A Heuristic Cluster-Based EM Algorithm for the Planted (L, d) Problem
复制标题
DOI：
10.1142/s0219720013500091
复制
发表时间：
2013-07
影响因子：
1
通讯作者：
Yipu Zhang;Hongwei Huo;Qiang Yu
中科院分区：
文献类型：
--
作者：
Yipu Zhang;Hongwei Huo;Qiang Yu
植入基序搜索问题源于定位转录因子结合位点（TFBS），这对于理解基因调控关系至关重要。过去，许多使用期望最大化来发现 TFBS 的尝试都取得了成功。然而，识别高度简并的主题并减少局部最优的影响仍然是一项艰巨的任务。为了减轻 EM 对局部最优捕获的脆弱性，我们提出了一种基于启发式聚类的 EM 算法 CEM，它细化 EM 方法中的聚类子集以探索最佳的局部最优解。基于使用合成数据集和真实数据集的实验，我们的算法在识别主题实例方面表现出显着的改进，并且比当前广泛使用的算法表现得更好。 CEM是一种新颖的植入式主题查找算法，由于求解每个簇子集的过程是独立的，因此能够解决具有挑战性的实例并且易于并行。
The planted motif search problem arises from locating the transcription factor binding sites (TFBSs) which are crucial for understanding the gene regulatory relationship. Many attempts in using expectation maximization for TFBSs discovery are successful in past. However, identifying highly degenerate motifs and reducing the effect of local optima are still an arduous task. To alleviate the vulnerability of EM to local optima trapping, we present a heuristic cluster-based EM algorithm, CEM, which refines the cluster subsets in EM method to explore the best local optimal solution. Based on experiments using both synthetic and real datasets, our algorithm demonstrates significant improvements in identifying the motif instances and performs better than current widely used algorithms. CEM is a novel planted motif finding algorithm, which is able to solve the challenging instances and easy to parallel since the process of solving each cluster subset is independent.