Bioinformatics Advance Access originally published online on March 4, 2004
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Bioinformatics 20(11) © Oxford University Press 2004; all rights reserved.
Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs
1 Department of Molecular Cell biology, 2 Department of Physics of Complex Systems and 3 Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel
Received on July 22, 2003; revised on December 2, 2003; accepted on January 8, 2004
Advance Access Publication March 4, 2004
Summary: Biological and engineered networks have recently been shown to display network motifs: a small set of characteristic patterns that occur much more frequently than in randomized networks with the same degree sequence. Network motifs were demonstrated to play key information processing roles in biological regulation networks. Existing algorithms for detecting network motifs act by exhaustively enumerating all subgraphs with a given number of nodes in the network. The runtime of such algorithms increases strongly with network size. Here, we present a novel algorithm that allows estimation of subgraph concentrations and detection of network motifs at a runtime that is asymptotically independent of the network size. This algorithm is based on random sampling of subgraphs. Network motifs are detected with a surprisingly small number of samples in a wide variety of networks. Our method can be applied to estimate the concentrations of larger subgraphs in larger networks than was previously possible with exhaustive enumeration algorithms. We present results for high-order motifs in several biological networks and discuss their possible functions.
Availability: A software tool for estimating subgraph concentrations and detecting network motifs (mfinder 1.1) and further information is available at http://www.weizmann.ac.il/mcb/UriAlon/
Contact: urialon{at}weizmann.ac.il
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  N. Alon, P. Dao, I. Hajirasouliha, F. Hormozdiari, and S. C. Sahinalp Biomolecular network motif counting and discovery by color coding Bioinformatics, July 1, 2008; 24(13): i241 - i249. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C.-Y. Lin, C.-H. Chin, H.-H. Wu, S.-H. Chen, C.-W. Ho, and M.-T. Ko Hubba: hub objects analyzer--a framework of interactome hubs identification for network biology Nucleic Acids Res., July 1, 2008; 36(suppl_2): W438 - W443. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 G. Ciriello and C. Guerra A review on models and algorithms for motif discovery in protein-protein interaction networks Brief Funct Genomic Proteomic, April 28, 2008; (2008) eln015v1. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. Fusco, B. Bassetti, P. Jona, and M. Cosentino Lagomarsino DIA-MCIS: an importance sampling network randomizer for network motif discovery and other topological observables in transcription networks Bioinformatics, December 15, 2007; 23(24): 3388 - 3390. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. Przulj Biological network comparison using graphlet degree distribution Bioinformatics, January 15, 2007; 23(2): e177 - e183. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 T. Aittokallio and B. Schwikowski Graph-based methods for analysing networks in cell biology Brief Bioinform, September 1, 2006; 7(3): 243 - 255. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Wernicke and F. Rasche FANMOD: a tool for fast network motif detection Bioinformatics, May 1, 2006; 22(9): 1152 - 1153. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. Przulj, D. G. Corneil, and I. Jurisica Efficient estimation of graphlet frequency distributions in protein-protein interaction networks Bioinformatics, April 15, 2006; 22(8): 974 - 980. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 N. Kashtan and U. Alon From the Cover: Spontaneous evolution of modularity and network motifs PNAS, September 27, 2005; 102(39): 13773 - 13778. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Ma'ayan, S. L. Jenkins, S. Neves, A. Hasseldine, E. Grace, B. Dubin-Thaler, N. J. Eungdamrong, G. Weng, P. T. Ram, J. J. Rice, et al. Formation of Regulatory Patterns During Signal Propagation in a Mammalian Cellular Network Science, August 12, 2005; 309(5737): 1078 - 1083. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
H.-W. Ma, B. Kumar, U. Ditges, F. Gunzer, J. Buer, and A.-P. Zeng An extended transcriptional regulatory network of Escherichia coli and analysis of its hierarchical structure and network motifs Nucleic Acids Res., December 16, 2004; 32(22): 6643 - 6649. [Abstract] [Full Text] [PDF]
|
|