MotifCut: regulatory motifs finding with maximum density subgraphs
MotifCut: regulatory motifs finding with maximum density subgraphs
复制标题
DOI：
10.1093/bioinformatics/btl243
复制
发表时间：
2006-07-01
期刊：
影响因子：
5.8
通讯作者：
Batzoglou, Serafim
中科院分区：
文献类型：
--
作者：
Fratkin, Eugene;Naughton, Brian T.;Batzoglou, Serafim
动机：DNA基序发现是计算生物学的核心问题之一，为此已经开发了几种概率和离散方法。大多数现有的方法将基序查找作为一个棘手的优化问题，并依赖于期望最大化（EM）或局部启发式搜索。另一个挑战是基序模型的选择：简单的模型，如位置特定评分矩阵（PSSM）强加了生物学上不现实的假设，如基序位置的独立性，而更复杂的模型更难参数化和学习。结果：我们提出了MotifCut，这是一种图论方法来寻找基序，导致一个多项式时间解的凸优化问题。我们建立了一个图，其中顶点表示输入序列中的所有k-mer，边表示成对k-mer相似度。在这个图中，我们寻找一个基序作为最大密度子图，这是一组k-mers，表现出大量的成对相似性。我们的公式没有对基序的结构做出强有力的假设，并且在实践中，适合PSSM模型的基序和那些在位置对之间表现出强烈依赖性的基序都被发现为密集子图。我们在合成和真实酵母基序上对MotifCut进行了基准测试，发现它比现有的流行方法更有利。MotifCut检测图案的能力似乎随着输入大小的增加而增加。此外，我们发现的基序与其他方法发现的基序不同。
Motivation: DNA motif finding is one of the core problems in computational biology, for which several probabilistic and discrete approaches have been developed. Most existing methods formulate motif finding as an intractable optimization problem and rely either on expectation maximization ( EM) or on local heuristic searches. Another challenge is the choice of motif model: simpler models such as the position-specific scoring matrix (PSSM) impose biologically unrealistic assumptions such as independence of the motif positions, while more involved models are harder to parametrize and learn.Results: We present MotifCut, a graph-theoretic approach to motif finding leading to a convex optimization problem with a polynomial time solution. We build a graph where the vertices represent all k-mers in the input sequences, and edges represent pairwise k-mer similarity. In this graph, we search for a motif as the maximum density subgraph, which is a set of k-mers that exhibit a large number of pairwise similarities. Our formulation does not make strong assumptions regarding the structure of the motif and in practice both motifs that fit well the PSSM model, and those that exhibit strong dependencies between position pairs are found as dense subgraphs. We benchmark MotifCut on both synthetic and real yeast motifs, and find that it compares favorably to existing popular methods. The ability of MotifCut to detect motifs appears to scale well with increasing input size. Moreover, the motifs we discover are different from those discovered by the other methods.