Back to Search Start Over

Application of dynamic expansion tree for finding large network motifs in biological networks

Authors :
Sabyasachi Patra
Anjali Mohapatra
Source :
PeerJ, Vol 7, p e6917 (2019)
Publication Year :
2019
Publisher :
PeerJ Inc., 2019.

Abstract

Network motifs play an important role in the 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, and protein function annotation. However, identification of large network motifs is a challenging task as it involves the graph isomorphism problem. Although this problem has been studied extensively in the literature using different computational approaches, still there is a lot of scope for improvement. Motivated by the challenges involved in this field, an efficient and scalable network motif finding algorithm using a dynamic expansion tree is proposed. The novelty of the proposed algorithm is that it avoids computationally expensive graph isomorphism tests and overcomes the space limitation of the static expansion tree (SET) which makes it enable to find large motifs. In this algorithm, the embeddings corresponding to a child node of the expansion tree are obtained from the embeddings of a parent node, either by adding a vertex or by adding an edge. This process does not involve any graph isomorphism check. The time complexity of vertex addition and edge addition are O(n) and O(1), respectively. The growth of a dynamic expansion tree (DET) depends on the availability of patterns in the target network. Pruning of branches in the DET significantly reduces the space requirement of the SET. The proposed algorithm has been tested on a protein–protein interaction network obtained from the MINT database. The proposed algorithm is able to identify large network motifs faster than most of the existing motif finding algorithms.

Details

Language :
English
ISSN :
21678359
Volume :
7
Database :
Directory of Open Access Journals
Journal :
PeerJ
Publication Type :
Academic Journal
Accession number :
edsdoj.8df5d643131c434ca2e185080e3e739e
Document Type :
article
Full Text :
https://doi.org/10.7717/peerj.6917