Motif discovery in biological network using expansion tree

Discovery of network motifs based on induced subgraphs using a dynamic expansion tree

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.

Protein complex prediction in interaction network based on network motif

The enormous size of Protein-Protein Interaction (PPI) networks demands efficient computational methods to extract biologically significant protein complexes. A wide variety of algorithms have been proposed to predict protein complexes from PPI networks. However, it is still a challenging task to detect protein complexes with high accuracy and manageable sensitivity. In this manuscript, a novel complex prediction algorithm based on Network Motif (CPNM) is proposed. This algorithm addresses the role of proteins in the embeddings of network motif. These roles are used to define feature vectors and feature weights of proteins. Based on these features, a neighborhood search technique predict the protein complexes that consider both the inherent organization of proteins as well as the dense regions in PPI networks. The performance of the proposed algorithm is evaluated using various evaluation metrics like Precision, Recall, F-measure, Sensitivity, PPV, and Accuracy. The research finding indicates that the proposed algorithm outperforms most of the competing algorithms like MCODE, DPClus, RNSC, COACH, ClusterONE, CMC and PROCODE over the PPI network of Saccharomyces cerevisiae and Homo sapiens.

Review of tools and algorithms for network motif discovery in biological networks

Network motifs are recurrent and over‐represented patterns having biological relevance. This is one of the important local properties of biological networks. Network motif discovery finds important applications in many areas such as functional analysis of biological components, the validity of network composition, classification of networks, disease discovery, identification of unique subunits etc. The discovery of network motifs is a computationally challenging task due to the large size of real networks, and the exponential increase of search space with respect to network size and motif size. This problem also includes the subgraph isomorphism check, which is Nondeterministic Polynomial (NP)‐complete. Several tools and algorithms have been designed in the last few years to address this problem with encouraging results. These tools and algorithms can be classified into various categories based on exact census, mapping, pattern growth, and so on. In this study, critical aspects of network motif discovery, design principles of background algorithms, and their functionality have been reviewed with their strengths and limitations. The performances of state‐of‐art algorithms are discussed in terms of runtime efficiency, scalability, and space requirement. The future scope, research direction, and challenges of the existing algorithms are presented at the end of the study.