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

Complex Prediction in Large PPI Networks Using Expansion and Stripe of Core Cliques

The widespread availability and importance of large-scale protein-protein interaction (PPI) data demand a flurry of research efforts to understand the organisation of a cell and its functionality by analysing these data at the network level. In the bioinformatics and data mining fields, network clustering acquired a lot of attraction to examine a PPI network's topological and functional aspects. The clustering of PPI networks has been proven to be an excellent method for discovering functional modules, disclosing functions of unknown proteins, and other tasks in numerous research over the last decade. This research proposes a unique graph mining approach to detect protein complexes using dense neighbourhoods (highly connected regions) in an interaction graph. Our technique first finds size-3 cliques associated with each edge (protein interaction), and then these core cliques are expanded to form high-density subgraphs. Loosely connected proteins are stripped out from these subgraphs to produce a potential protein complex. Finally, the redundancy is removed based on the Jaccard coefficient. Computational results are presented on the yeast and human protein interaction dataset to highlight our proposed technique's efficiency. Predicted protein complexes of the proposed approach have a significantly higher score of similarity to those used as gold standards in the CYC-2008 and CORUM benchmark databases than other existing approaches.

Introduction to the Class of Prefractal Graphs

Fractals are already firmly rooted in modern science. Research continues on the fractal properties of objects in physics, chemistry, biology and many other scientific fields. Fractal graphs as a discrete representation are used to model and describe the structure of various objects and processes, both natural and artificial. The paper proposes an introduction to prefractal graphs. The main definitions and notation are proposed—the concept of a seed, the operations of processing a seed, the procedure for generating a prefractal graph. Canonical (typical) and non-canonical (special) types of prefractal graphs are considered separately. Important characteristics are proposed and described—the preservation of adjacency of edges for different ranks in the trajectory. The definition of subgraph-seeds of different ranks is given separately. Rules for weighting a prefractal graph by natural numbers and intervals are proposed. Separately, the definition of a fractal graph as infinite is given, and the differences between the concepts of fractal and prefractal graphs are described. At the end of the work, already published works of the authors are proposed, indicating the main backlogs, as well as a list of directions for new research. This work is the beginning of a cycle of works on the study of the properties and characteristics of fractal and prefractal graphs.

Testing biological network motif significance with exponential random graph models

Analysis of the structure of biological networks often uses statistical tests to establish the over-representation of motifs, which are thought to be important building blocks of such networks, related to their biological functions. However, there is disagreement as to the statistical significance of these motifs, and there are potential problems with standard methods for estimating this significance. Exponential random graph models (ERGMs) are a class of statistical model that can overcome some of the shortcomings of commonly used methods for testing the statistical significance of motifs. ERGMs were first introduced into the bioinformatics literature over 10 years ago but have had limited application to biological networks, possibly due to the practical difficulty of estimating model parameters. Advances in estimation algorithms now afford analysis of much larger networks in practical time. We illustrate the application of ERGM to both an undirected protein-protein interaction (PPI) network and directed gene regulatory networks. ERGM models indicate over-representation of triangles in the PPI network, and confirm results from previous research as to over-representation of transitive triangles (feed-forward loop) in an E. coli and a yeast regulatory network. We also confirm, using ERGMs, previous research showing that under-representation of the cyclic triangle (feedback loop) can be explained as a consequence of other topological features.

SUPPLEMENTARY INFORMATION

The online version contains supplementary material available at 10.1007/s41109-021-00434-y.

Impact of second-order network motif on online social networks

The behaviour of individual users in an online social network is a major contributing factor in determining the outcome of multiple network phenomenon. Group formation, growth of the network, information propagation, and rumour blocking are some of the many network behavioural traits that are influenced by the interaction patterns of the users in the network. Network motifs capture one such interaction pattern between users in online social networks (OSNs). For this work, four second-order (two-edged) network motifs have been considered, namely, message receiving pattern, message broadcasting pattern, message passing pattern, and reciprocal message pattern, to analyse user behaviour in online social networks. This work provides and utilizes a node interaction pattern-finding algorithm to identify the frequency of aforementioned second-order network motifs in six real-life online social networks (Facebook, GPlus, GNU, Twitter, Enron Email, and Wiki-vote). The frequency of network motifs participated in by a node is considered for the relative ranking of all nodes in the online social networks. The highest-rated nodes are considered seeds for information propagation. The performance of using network motifs for ranking nodes as seeds for information propagation is validated using statistical metrics Z-score, concentration, and significance profile and compared with baseline ranking methods in-degree centrality, out-degree centrality, closeness centrality, and PageRank. The comparative study shows the performance of centrality measures to be similar or better than second-order network motifs as seed nodes in information diffusion. The experimental results on finding frequencies and importance of different interaction patterns provide insights on the significance and representation of each such interaction pattern and how it varies from network to network.

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.