Discovery of network motifs based on induced subgraphs using a dynamic expansion tree. (August 2021)

• Record Type: Journal Article
• Authors: Patra, Sabyasachi
• Is Part Of: Computational biology and chemistry. Volume 93(2021)
• Publication Date: 2021-08
• Subjects: Biological network -- Network motif -- Induced subgraph -- Subgraph isomorphism -- Static expansion tree -- Dynamic expansion tree; Chemistry -- Data processing -- Periodicals; Biology -- Data processing -- Periodicals; Biochemistry -- Data processing; Biology -- Data processing; Molecular biology -- Data processing; Periodicals; Electronic journals; 542.85
• DOI: 10.1016/j.compbiolchem.2021.107530
• Languages: English
• ISSNs: 1476-9271

Abstract

Graphical abstract: Highlights: A novel network motif discovery algorithm based on a dynamic expansion tree (DET) is proposed to discover network motifs in biological networks. DET reduces the space requirement of static expansion tree significantly. Two optimized module tree census and graph census are used to reduce subgraph isomorphism checks. Properties of induced subgraphs help to define pruning criterion during graph census. The research findings indicate that the proposed algorithm outperforms most of the competing algorithms like FANMOD, MODA and Elhesha-Kahveci over the PPI network of six species taken from the MINT database. Abstract: Biological networks are powerful representations of topological features in biological systems. Finding network motifs in biological networks is a computationally hard problem due to their huge size and abrupt increase of search space with the increase of motif size. Motivated by the computational challenges of network motif discovery and considering the importance of this topic, an efficient and scalable network motif discovery algorithm based on induced subgraphs in a dynamic expansion tree is proposed. This algorithm uses a pruning strategy to overcome the space limitation of the static expansion tree. The proposed algorithm can identify large network motifs up to size 15 by significantly reducing the computationally expensive subgraph isomorphism checks. Further, the present work avoids the unnecessary growth of patterns that do not have any statistical significance. The runtime performance of the proposed algorithm outperforms most of the existing algorithms for large network motifs.