Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs
Nadav Kashtan, Shalev Itzkovitz, Ron Milo et al. · Bioinformatics · 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/
Cited by 537 works. doi:10.1093/bioinformatics/bth163 Open-access PDF
Authors
References
- Emergence of Scaling in Random Networks
- Principles of Neurodynamics.
- A Learning Algorithm for Boltzmann Machines*
- Introduction to the theory of neural computation
- The structure of the nervous system of the nematode Caenorhabditis elegans
- Network Motifs: Simple Building Blocks of Complex Networks
- Introduction to the Theory of Neural Computation
- Simple rules yield complex food webs
- REGULAR PARTITIONS OF GRAPHS
- YPDTM, PombePDTM and WormPDTM: model organism volumes of the BioKnowledgeTM Library, an integrated resource for protein information