MotifCut swMATH ID: 35400 Software Authors: Eugene Fratkin, Brian T. Naughton, Douglas L. Brutlag, Serafim Batzoglou Description: MotifCut: regulatory motifs finding with maximum density subgraphs. 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. Availability: MotifCut server and other materials can be found at motifcut.stanford.edu Homepage: https://academic.oup.com/bioinformatics/article/22/14/e150/228394 Related Software: GitHub; DIMACS; SNAP; NetworkX; CIDANE; SageMath; MCODE; GAME; SVM-Prot; LFM-Pro; PRED-CLASS; BLAST; PSI-BLAST; GOtcha; SVMlight Cited in: 10 Documents all top 5 Cited by 25 Authors 3 Dondi, Riccardo 2 Hosseinzadeh, Mohammad Mehdi 1 Arrazola, Juan Miguel 1 Atalay, Volkan 1 Bromley, Thomas R. 1 Calude, Cristian S. 1 Cetin-Atalay, Rengul 1 Dinneen, Michael J. 1 Galbrun, Esther 1 Gionis, Aristides 1 Gupt, Brajesh 1 Gürsoy-Yüzügüllü, Özge 1 Hua, Richard 1 Kawase, Yasushi 1 Ma, Qianli 1 Mauri, Giancarlo 1 Miyauchi, Atsushi 1 Quesada, Nicolás 1 Sarac, Omer Sinan 1 Tatti, Nikolaj 1 Wang, Jiabing 1 Wang, Rongjie 1 Wei, Jia 1 Wen, Guihua 1 Zoppis, Italo all top 5 Cited in 8 Serials 1 Information Processing Letters 1 Information Sciences 1 Algorithmica 1 Journal of Combinatorial Optimization 1 Data Mining and Knowledge Discovery 1 Quantum Information Processing 1 Computational Biology and Chemistry 1 Journal of Membrane Computing all top 5 Cited in 6 Fields 6 Computer science (68-XX) 5 Combinatorics (05-XX) 3 Operations research, mathematical programming (90-XX) 2 Biology and other natural sciences (92-XX) 1 Statistics (62-XX) 1 Quantum theory (81-XX) Citations by Year