Biomolecular network motif counting and discovery by color coding

Area of Science:

• Bioinformatics
• Systems Biology
• Network Science

Background:

• Protein-protein interaction (PPI) networks exhibit conserved global topological features but vary in local structures like network motifs.
• Accurate counting of network motifs is crucial for comparing biomolecular networks, yet existing algorithms struggle with non-induced occurrences and larger subgraph sizes (k > 7).
• Current PPI network data contains inaccuracies (false positives and negatives), necessitating methods that account for non-induced subgraph occurrences.

Purpose of the Study:

• To present a novel algorithm for counting non-induced occurrences of subgraph topologies in biological networks.
• To apply this algorithm to analyze and compare the local structures of PPI networks from different organisms.
• To investigate the robustness of network motif distributions against data sparsification.

Main Methods:

• Adaptation of the 'color coding' technique to count non-induced occurrences of tree and bounded treewidth subgraphs.
• Development of an algorithm with polynomial time complexity in network size (n) for motif size k = O(log n).
• Analysis of PPI networks from Saccharomyces cerevisiae, Escherichia coli, Helicobacter pylori, and Caenorhabditis elegans.

Main Results:

• The algorithm successfully counted non-induced subgraph occurrences (treelets) for k <= 10 in PPI networks.
• Unicellular organisms (yeast, E. coli, H. pylori) displayed similar treelet distributions, distinct from the multicellular organism (C. elegans).
• Treelet distributions of unicellular organisms aligned with the 'duplication model' but not the 'preferential attachment model'.

Conclusions:

• The developed algorithm provides a practical solution for counting non-induced network motifs, advancing comparative network biology.
• Significant differences in local network structures (treelet distributions) exist between unicellular and multicellular organisms.
• The treelet distribution is a robust feature of PPI networks, maintaining statistical significance even with moderate data sparsification (70% coverage).