Related Experiment Video
Updated: Jul 11, 2026
10:44
Inherent Dynamics Visualizer, an Interactive Application for Evaluating and Visualizing Outputs from a Gene Regulatory Network Inference Pipeline
Published on: December 7, 2021
Graph animals, subgraph sampling, and motif search in large networks
Kim Baskerville1, Peter Grassberger, Maya Paczuski
1Perimeter Institute for Theoretical Physics, Waterloo, Canada N2L 2Y5.
Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|October 13, 2007
Summary
We developed a faster Monte Carlo algorithm to sample connected subgraphs in biological networks. This method reveals distinct network motifs in E. coli and yeast protein interaction networks, highlighting differences in their structures.
Area of Science:
- Network biology
- Computational biology
- Graph theory
Background:
- Understanding the structure of biological networks is crucial for deciphering cellular functions.
- Previous methods for analyzing connected subgraphs in networks were computationally intensive.
Purpose of the Study:
- To generalize a sampling algorithm for lattice animals to graph animals in arbitrary networks.
- To develop a faster Monte Carlo method for sampling connected subgraphs.
- To analyze the structural motifs in protein-protein interaction networks of E. coli and yeast.
Main Methods:
- Generalization of a lattice animal sampling algorithm to a Monte Carlo algorithm for graph animals.
- Development of a fast heuristic algorithm for classifying isomorphic graphs.
- Application of the algorithm to protein interaction networks from E. coli and yeast obtained via tandem affinity purification (TAP).
Main Results:
- The new algorithm provides weighted samples of subgraphs with significantly faster weight computation (linear in subgraph size).
- Analysis of E. coli and yeast networks revealed that most connected subgraphs are strong motifs or antimotifs.
- E. coli networks exhibit nearly bipartite motifs, while yeast networks show a tendency towards completeness or large cliques.
Conclusions:
- The developed Monte Carlo algorithm enables efficient sampling and analysis of complex biological networks.
- Significant structural differences exist between E. coli and yeast protein interaction networks.
- Specific complexes can disproportionately influence network motifs, particularly in dense network regions.
Related Concept Videos
02:26Protein Networks
An organism can have thousands of different proteins, and these proteins must cooperate to ensure the health of an organism. Proteins bind to other proteins and form complexes to carry out their functions. Many proteins interact with multiple other proteins creating a complex network of protein interactions.
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
02:26Protein Networks
An organism can have thousands of different proteins, and these proteins must cooperate to ensure the health of an organism. Proteins bind to other proteins and form complexes to carry out their functions. Many proteins interact with multiple other proteins creating a complex network of protein interactions.
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
01:24Sequence Networks of Rotating Machines
A Y-connected synchronous generator, grounded through a neutral impedance, is designed to produce balanced internal phase voltages with only positive-sequence components. The generator's sequence networks include a source voltage that is exclusively in the positive-sequence network. The sequence components of line-to-ground voltages at the generator terminals illustrate this configuration.
Zero-sequence current induces a voltage drop across the generator's neutral impedance and other...
Zero-sequence current induces a voltage drop across the generator's neutral impedance and other...
02:04Protein-protein Interfaces
Many proteins form complexes to carry out their functions, making protein-protein interactions (PPIs) essential for an organism's survival. Most PPIs are stabilized by numerous weak noncovalent chemical forces. The physical shape of the interfaces determines the way two proteins interact. Many globular proteins have closely-matching shapes on their surfaces, which form a large number of weak bonds. Additionally, many PPIs occur between two helices or between a surface cleft and a polypeptide...
01:20Cluster Sampling Method
Appropriate sampling methods ensure that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest.
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...