Efficient updates of network motif instances in the extended protein-protein interaction network

A network motif is defined as an over-represented subgraph pattern in a network and has been widely applied in analyses of biological networks. The detection of network motifs involves the computationally expensive enumeration of subgraphs, NP-complete graph isomorphism testing, and significance testing through the generation of many random graphs to determine the statistical uniqueness of a given subgraph. These computational obstacles make the analysis of network motifs unfeasible for many real-world applications. From some biological network databases, we observe that the fast advancement of biotechnology has led to the rapid growth of existing biological network databases. Even with a small percentage of additions, updated networks will have a large number of differing network motif instances. Currently, no algorithms exist that can efficiently recalculate motif instances in `updated´ networks. In this paper, we introduce an algorithm to efficiently recalculate motif instances by performing motif enumeration from only updated vertices and edges. Preliminary experimental results show that it greatly reduces computational time by eliminating the regeneration of overlapped subgraph instances from earlier versions of the network.