Biomolecular network motif counting and its applications in PPI network comparison

Protein-protein interaction (PPI) networks of many organisms share global topological fea- tures such as degree distribution. However, these networks can differ from one another in terms of local structures or occurrences of specific subgraphs can vary significantly among them. Previous algorithms can count induced occurrences of subgraphs with at most 7 ver- tices and no implementations can count non-induced occurrences of subgraphs with at most 7 vertices. Counting non-induced occurrences of subgraphs is not only challenging but also quite desirable as available PPI networks include several false interactions and miss many others. We provide a novel randomized approximation algorithm to count non-induced oc- currences of a query tree in an input graph for a given additive error and error probability of failure. We use our algorithm to compare PPI networks of several organisms among themselves and with emulated networks generated by random processes.