An Algorithm Based On Statistical Model For Detecting Biological Network Motifs

In 2003, the Human Genome Project has been completed, and we have entered the post-genomic era. Interaction networks are of central importance in post-genomic molecular biology, with increasing amount of data becoming available by high-throughput methods. Examples are gene regulatory networks or protein interaction maps. The main challenge in the analysis of these data is to read off biological functions from the topology of the network. Topological motifs, i.e, patterns occurring repeatedly at different positions in the networkhave recently been identified as basic modules of molecular information processing. In this paper, we discuss motifs derived from families of mutually similar but not necessarily identical patterns. We establish a statistical model for the occurrence of such motifs, from which we derive a scoring fuction for their statistical significance. The algorithm is to start with a method that efficiently enumerates all size-k nontreelike graphs. Then based on the scoring function, we derive the topological motifs. Experimental evaluation on real biological networks data from various domains shows that our algorithm achieves good performance.