2015 · 15 citations · 24 references
Life SciencesBioinformaticsBiologyComputational BiologyGene Regulatory NetworksNetwork BiologyBiological NetworksMolecular Interaction NetworksMotif DiscoveryNetwork InferenceNetwork MotifsProtein-protein Interaction NetworksBiological Network InferenceInteraction Network Motif AnalysisMotif Counting AlgorithmsMotif Detection AlgorithmsNetwork Connectivity PatternsProbabilistic ComputationProbabilistic Motif ModelsUnderrepresented Motifs
Studying the distribution of motifs in biological networks provides valuable insights about the key functions of these networks. Finding motifs in networks is however a computationally challenging task. This task is further complicated by the fact that inherently, biological networks have uncertain topologies. Such uncertainty is often described using probabilistic network models. In this study we tackle this challenge. We present the exact computation of the expected value and variance of the number of occurrences of key motifs in probabilistic networks, as well as a specialized sampling approximate method for computing the variance for very large networks. Our method is generic, and easily extends to arbitrary motif topologies. Our experiments demonstrate that our method scales to large protein interaction networks as well as synthetically generated networks with different connectivity patterns. Using our method, we identify over-represented motifs in protein-protein interaction networks of five different organisms, as well as in human transcription regulatory networks of different human cells with different lineages.
24
Collective dynamics of ‘small-world’ networks
Duncan J. Watts, Steven H. Strogatz · Nature · 1998 · 43.2K citations
Emergence of Scaling in Random Networks
Albert-Ĺaszló Barabási, Réka Albert · Science · 1999 · 36.4K citations · Full text
Network Motifs: Simple Building Blocks of Complex Networks
Ron Milo, Shai S. Shen-Orr, Shalev Itzkovitz et al. · Science · 2002 · 7.5K citations
Network motifs in the transcriptional regulation network of Escherichia coli
Shai S. Shen-Orr, Ron Milo, Shmoolik Mangan et al. · Nature Genetics · 2002 · 3.1K citations