Discovery of Large Disjoint Motif in Biological Network using Dynamic Expansion Tree

Abstract

Network motifs play an important role in structural analysis of biological networks. Identification of such network motifs leads to many important applications, such as: understanding the modularity and the large-scale structure of biological networks, classification of networks into super-families etc. However, identification of network motifs is challenging as it involved graph isomorphism which is computationally hard problem. Though this problem has been studied extensively in the literature using different computational approaches, we are far from encouraging results. Motivated by the challenges involved in this field we have proposed an efficient and scalable Motif discovery algorithm using a Dynamic Expansion Tree (MDET). In this algorithm embeddings corresponding to child node of expansion tree are obtained from the embeddings of parent node, either by adding a vertex with time complexity O(n) or by adding an edge with time complexity O(1) without involving any isomorphic check. The growth of Dynamic Expansion Tree (DET) depends on availability of patterns in the target network. DET reduces space complexity significantly and the memory limitation of static expansion tree can overcome. The proposed algorithm has been tested on Protein Protein Interaction (PPI) network obtained from MINT database. It is able to identify large motifs faster than most of the existing motif discovery algorithms.