Network Motif Discovery Using Subgraph Enumeration and Symmetry-Breaking Export

@incollection{citeulike:2047399, abstract = {The study of biological networks and network motifs can yield significant new insights into systems biology. Previous methods of discovering network motifs – network-centric subgraph enumeration and sampling – have been limited to motifs of 6 to 8 nodes, revealing only the smallest network components. New methods are necessary to identify larger network sub-structures and functional motifs. Here we present a novel algorithm for discovering large network motifs that achieves these goals, based on a novel symmetry-breaking technique, which eliminates repeated isomorphism testing, leading to an exponential speed-up over previous methods. This technique is made possible by reversing the traditional network-based search at the heart of the algorithm to a motif-based search, which also eliminates the need to store all motifs of a given size and enables parallelization and scaling. Additionally, our method enables us to study the clustering properties of discovered motifs, revealing even larger network elements. We apply this algorithm to the protein-protein interaction network and transcription regulatory network of S. cerevisiae, and discover several large network motifs, which were previously inaccessible to existing methods, including a 29-node cluster of 15-node motifs corresponding to the key transcription machinery of S. cerevisiae.}, author = {Grochow, Joshua and Kellis, Manolis}, citeulike-article-id = {2047399}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-71681-5_7}, citeulike-linkout-1 = {http://www.springerlink.com/content/232p87x375r617m2}, doi = {10.1007/978-3-540-71681-5_7}, journal = {Research in Computational Molecular Biology}, keywords = {detection, motif, network, symmetry}, pages = {92--106}, posted-at = {2009-11-02 22:02:51}, priority = {2}, title = {Network Motif Discovery Using Subgraph Enumeration and Symmetry-Breaking}, url = {http://dx.doi.org/10.1007/978-3-540-71681-5_7}, year = {2007} }

TY - CHAP ID - citeulike:2047399 L3 - citeulike-article-id:2047399 N2 - The study of biological networks and network motifs can yield significant new insights into systems biology. Previous methods of discovering network motifs – network-centric subgraph enumeration and sampling – have been limited to motifs of 6 to 8 nodes, revealing only the smallest network components. New methods are necessary to identify larger network sub-structures and functional motifs. Here we present a novel algorithm for discovering large network motifs that achieves these goals, based on a novel symmetry-breaking technique, which eliminates repeated isomorphism testing, leading to an exponential speed-up over previous methods. This technique is made possible by reversing the traditional network-based search at the heart of the algorithm to a motif-based search, which also eliminates the need to store all motifs of a given size and enables parallelization and scaling. Additionally, our method enables us to study the clustering properties of discovered motifs, revealing even larger network elements. We apply this algorithm to the protein-protein interaction network and transcription regulatory network of S. cerevisiae, and discover several large network motifs, which were previously inaccessible to existing methods, including a 29-node cluster of 15-node motifs corresponding to the key transcription machinery of S. cerevisiae. JF - Research in Computational Molecular Biology EP - 106 TI - Network Motif Discovery Using Subgraph Enumeration and Symmetry-Breaking SP - 92 KW - detection KW - motif KW - network KW - symmetry AU - Grochow, Joshua AU - Kellis, Manolis PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-71681-5_7 ER -