Subgraph ensembles and motif discovery using an alternative heuristic for graph isomorphism

Area of Science:

• Graph theory
• Network analysis
• Bioinformatics

Background:

• Understanding complex networks like protein interactions is crucial.
• Identifying recurring structural patterns (motifs) can reveal functional units.

Purpose of the Study:

• Develop a rapid heuristic for distinguishing nonisomorphic graphs.
• Apply this method to analyze the Escherichia coli protein interaction network.
• Discover and characterize network motifs and antimotifs.

Main Methods:

• A heuristic based on vertex invariants to classify graph isomorphism.
• Statistical analysis of N-node subgraphs (N<=14) from the E. coli network.
• Zipf plot analysis to describe subgraph occurrence distributions.
• Comparison of motifs and antimotifs based on structural properties.

Main Results:

• The heuristic effectively distinguishes nonisomorphic graphs with high accuracy.
• Subgraph occurrences in the E. coli network follow robust power-law distributions (Zipf plots).
• These power laws are invariant to network rewiring that preserves degree sequences.
• Identified motifs are typically denser, bipartite, or complete graphs, while antimotifs are tree-like.

Conclusions:

• The developed heuristic provides an efficient tool for graph analysis.
• The E. coli protein interaction network exhibits distinct structural patterns related to motifs and antimotifs.
• These findings offer insights into the organization and potential function of biological networks.