close
Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2008 Jul 1;24(13):i241-9.
doi: 10.1093/bioinformatics/btn163.

Biomolecular network motif counting and discovery by color coding

Noga Alon  1 , Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, S Cenk Sahinalp
Affiliations

Biomolecular network motif counting and discovery by color coding

Noga Alon et al. Bioinformatics. .

Abstract

Protein-protein interaction (PPI) networks of many organisms share global topological features such as degree distribution, k-hop reachability, betweenness and closeness. Yet, some of these networks can differ significantly from the others in terms of local structures: e.g. the number of specific network motifs can vary significantly among PPI networks. Counting the number of network motifs provides a major challenge to compare biomolecular networks. Recently developed algorithms have been able to count the number of induced occurrences of subgraphs with k < or = 7 vertices. Yet no practical algorithm exists for counting non-induced occurrences, or counting subgraphs with k > or = 8 vertices. Counting non-induced occurrences of network motifs is not only challenging but also quite desirable as available PPI networks include several false interactions and miss many others. In this article, we show how to apply the 'color coding' technique for counting non-induced occurrences of subgraph topologies in the form of trees and bounded treewidth subgraphs. Our algorithm can count all occurrences of motif G' with k vertices in a network G with n vertices in time polynomial with n, provided k = O(log n). We use our algorithm to obtain 'treelet' distributions for k < or = 10 of available PPI networks of unicellular organisms (Saccharomyces cerevisiae Escherichia coli and Helicobacter Pyloris), which are all quite similar, and a multicellular organism (Caenorhabditis elegans) which is significantly different. Furthermore, the treelet distribution of the unicellular organisms are similar to that obtained by the 'duplication model' but are quite different from that of the 'preferential attachment model'. The treelet distribution is robust w.r.t. sparsification with bait/edge coverage of 70% but differences can be observed when bait/edge coverage drops to 50%.

PubMed Disclaimer

Figures

Fig. 1.
Fig. 1.
Comparison between the output of our algorithm and the actual occurrences for subtrees of size k=8.
Fig. 2.
Fig. 2.
List of treelets for k=8.
Fig. 3.
Fig. 3.
List of treelets with k=9.
Fig. 4.
Fig. 4.
List of treelets with k=10.
Fig. 5.
Fig. 5.
A comparison of treelet distributions of five networks (a) size 8, (b) size 9 and (c) size 10 generated from the Yeast PPI network with both the bait and edge sampling probability equal to 0.7.
Fig. 6.
Fig. 6.
A comparison of the treelet distributions of five networks (a) size 8, (b) size 9 and (c) size 10 generated from the Yeast PPI network with both the bait and edge sampling probability equal to 0.5.
Fig. 7.
Fig. 7.
Normalized treelet distribution (a) size 8, (b) size 9 and (c) size 10 of the Yeast PPI network (Red), E.coli (Green) and H.pylori (Blue).
Fig. 8.
Fig. 8.
Normalized treelet (a) size 8, (b) size 9 and (c) size 10 distribution of the Yeast PPI network (Red), E.coli (Green), H.pylori (Blue) and C.elegans (Pink).
Fig. 9.
Fig. 9.
Normalized treelet distribution (a) size 8, (b) size 9 and (c) size 10 of the Yeast (Red), H.pylori (Blue), E.coli (Green) PPI networks and Preferential Attachment model (Pink), Duplication model (Cyan).
See this image and copyright information in PMC

References

    1. Alon N, Gutner S. Proc. ICALP. 2007. Balanced families of perfect hash functions and their applications; pp. 435–446.
    1. Alon N, et al. Color-coding. J. ACM. 1995;42:844–856.
    1. Arvind V, Raman V. In Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC'02) 2002. Approximation algorithms for some parameterized counting problems; pp. 453–464.
    1. Barabási AL, Albert R. Emergence of scaling in random networks. Science. 1999;286:509–512. - PubMed
    1. Bebek G, et al. The degree distribution of the generalized duplication model. Theor. Comput. Sci. 2006;369:239–249.