Kavosh: a new algorithm for finding network motifs

Background  

Complex networks are studied across many fields of science and are particularly important to understand biological processes. Motifs in networks are small connected sub-graphs that occur significantly in higher frequencies than in random networks. They have recently gathered much attention as a useful concept to uncover structural design principles of complex networks. Existing algorithms for finding network motifs are extremely costly in CPU time and memory consumption and have practically restrictions on the size of motifs.     

CytoKavosh: A Cytoscape Plug-In for Finding Network Motifs in Large Biological Networks

Network motifs are small connected sub-graphs that have recently gathered much attention to discover structural behaviors of large and complex networks. Finding motifs with any size is one of the most important problems in complex and large networks. It needs fast and reliable algorithms and tools for achieving this purpose. CytoKavosh is one of the best choices for finding motifs with any given size in any complex network. It relies on a fast algorithm, Kavosh, which makes it faster than other existing tools. Kavosh algorithm applies some well known algorithmic features and includes tricky aspects, which make it an efficient algorithm in this field. CytoKavosh is a Cytoscape plug-in which supports us in finding motifs of given size in a network that is formerly loaded into the Cytoscape work-space (directed or undirected). High performance of CytoKavosh is achieved by dynamically linking highly optimized functions of Kavosh's C++ to the Cytoscape Java program, which makes this plug-in suitable for analyzing large biological networks. Some significant attributes of CytoKavosh is efficiency in time usage and memory and having no limitation related to the implementation in motif size. CytoKavosh is implemented in a visual environment Cytoscape that is convenient for the users to interact and create visual options to analyze the structural behavior of a network. This plug-in can work on any given network and is very simple to use and generates graphical results of discovered motifs with any required details. There is no specific Cytoscape plug-in, specific for finding the network motifs, based on original concept. So, we have introduced for the first time, CytoKavosh as the first plug-in, and we hope that this plug-in can be improved to cover other options to make it the best motif-analyzing tool.     

ModuleSearch: finding functional modules in a protein-protein interaction network

Many biological processes are performed by a group of proteins rather than by individual proteins. Proteins involved in the same biological process often form a densely connected sub-graph in a protein-protein interaction network. Therefore, finding a dense sub-graph provides useful information to predict the function or protein complex of uncharacterised proteins in the sub-graph. We developed a heuristic algorithm that finds functional modules in a protein-protein interaction network and visualises the modules. The algorithm has been implemented in a platform-independent, standalone program called ModuleSearch. In an interaction network of yeast proteins, ModuleSearch found 366 overlapping modules. Of the modules, 71% have a function shared by more than half the proteins in the module and 58% have a function shared by all proteins in the module. Comparison of ModuleSearch with other programs shows that ModuleSearch finds more sub-graphs than most other programs, yet a higher proportion of the sub-graphs correspond to known functional modules. ModuleSearch and sample data are freely available to academics at http://bclab.inha.ac.kr/ModuleSearch.     

ModuleSearch: finding functional modules in a protein–protein interaction network

Many biological processes are performed by a group of proteins rather than by individual proteins. Proteins involved in the same biological process often form a densely connected sub-graph in a protein–protein interaction network. Therefore, finding a dense sub-graph provides useful information to predict the function or protein complex of uncharacterised proteins in the sub-graph. We developed a heuristic algorithm that finds functional modules in a protein–protein interaction network and visualises the modules. The algorithm has been implemented in a platform-independent, standalone program called ModuleSearch. In an interaction network of yeast proteins, ModuleSearch found 366 overlapping modules. Of the modules, 71% have a function shared by more than half the proteins in the module and 58% have a function shared by all proteins in the module. Comparison of ModuleSearch with other programs shows that ModuleSearch finds more sub-graphs than most other programs, yet a higher proportion of the sub-graphs correspond to known functional modules. ModuleSearch and sample data are freely available to academics at http://bclab.inha.ac.kr/ModuleSearch.     

In silico evolution of functional modules in biochemical networks

Understanding the large reaction networks found in biological systems is a daunting task. One approach is to divide a network into more manageable smaller modules, thus simplifying the problem. This is a common strategy used in engineering. However, the process of identifying biological modules is still in its infancy and very little is understood about the range and capabilities of motif structures found in biological modules. In order to delineate these modules, a library of functional motifs has been generated via in silico evolution techniques. On the basis of their functional forms, networks were evolved from four broad areas: oscillators, bistable switches, homeostatic systems and frequency filters. Some of these motifs were constructed from simple mass action kinetics, others were based on Michaelis-Menten kinetics as found in protein/protein networks and the remainder were based on Hill equations as found in gene/protein interaction networks. The purpose of the study is to explore the capabilities of different network architectures and the rich variety of functional forms that can be generated. Ultimately, the library may be used to delineate functional motifs in real biological networks.     

Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs

SUMMARY: Biological and engineered networks have recently been shown to display network motifs: a small set of characteristic patterns that occur much more frequently than in randomized networks with the same degree sequence. Network motifs were demonstrated to play key information processing roles in biological regulation networks. Existing algorithms for detecting network motifs act by exhaustively enumerating all subgraphs with a given number of nodes in the network. The runtime of such algorithms increases strongly with network size. Here, we present a novel algorithm that allows estimation of subgraph concentrations and detection of network motifs at a runtime that is asymptotically independent of the network size. This algorithm is based on random sampling of subgraphs. Network motifs are detected with a surprisingly small number of samples in a wide variety of networks. Our method can be applied to estimate the concentrations of larger subgraphs in larger networks than was previously possible with exhaustive enumeration algorithms. We present results for high-order motifs in several biological networks and discuss their possible functions. AVAILABILITY: A software tool for estimating subgraph concentrations and detecting network motifs (mfinder 1.1) and further information is available at http://www.weizmann.ac.il/mcb/UriAlon/     

生物分子网络弹性研究进展

弹性是生物分子网络重要且基础的属性之一,一方面弹性赋予生物分子网络抵抗内部噪声与环境干扰并维持其自身基本功能的能力,另一方面,弹性为网络状态的恢复制造了阻力。生物分子网络弹性研究试图回答如下3个问题：a. 生物分子网络弹性的产生机理是什么？b. 弹性影响下生物分子网络的状态如何发生转移？c. 如何预测生物网络状态转换临界点,以防止系统向不理想的状态演化？因此,研究生物分子网络弹性有助于理解生物系统内部运作机理,同时对诸如疾病发生临界点预测、生物系统状态逆转等临床应用具有重要的指导意义。鉴于此,本文主要针对以上生物分子网络弹性领域的3个热点研究问题,在研究方法和生物学应用上进行了系统地综述,并对未来生物分子网络弹性的研究方向进行了展望。     

Counting motifs in dynamic networks

Background

A network motif is a sub-network that occurs frequently in a given network. Detection of such motifs is important since they uncover functions and local properties of the given biological network. Finding motifs is however a computationally challenging task as it requires solving the costly subgraph isomorphism problem. Moreover, the topology of biological networks change over time. These changing networks are called dynamic biological networks. As the network evolves, frequency of each motif in the network also changes. Computing the frequency of a given motif from scratch in a dynamic network as the network topology evolves is infeasible, particularly for large and fast evolving networks.

Results

In this article, we design and develop a scalable method for counting the number of motifs in a dynamic biological network. Our method incrementally updates the frequency of each motif as the underlying network’s topology evolves. Our experiments demonstrate that our method can update the frequency of each motif in orders of magnitude faster than counting the motif embeddings every time the network changes. If the network evolves more frequently, the margin with which our method outperforms the existing static methods, increases.

Conclusions

We evaluated our method extensively using synthetic and real datasets, and show that our method is highly accurate(≥?96%) and that it can be scaled to large dense networks. The results on real data demonstrate the utility of our method in revealing interesting insights on the evolution of biological processes.

     

Searching RNA motifs and their intermolecular contacts with constraint networks

MOTIVATION: Searching RNA gene occurrences in genomic sequences is a task whose importance has been renewed by the recent discovery of numerous functional RNA, often interacting with other ligands. Even if several programs exist for RNA motif search, none exists that can represent and solve the problem of searching for occurrences of RNA motifs in interaction with other molecules. RESULTS: We present a constraint network formulation of this problem. RNA are represented as structured motifs that can occur on more than one sequence and which are related together by possible hybridization. The implemented tool MilPat is used to search for several sRNA families in genomic sequences. Results show that MilPat allows to efficiently search for interacting motifs in large genomic sequences and offers a simple and extensible framework to solve such problems. New and known sRNA are identified as H/ACA candidates in Methanocaldococcus jannaschii. AVAILABILITY: http://carlit.toulouse.inra.fr/MilPaT/MilPat.pl.     

Toward a classification of isodynamic feed-forward motifs

A preceding study analysed how the topology of network motifs affects the overall rate of the underlying biochemical processes. Surprisingly, it was shown that topologically non-isomorphic motifs can still be isodynamic in the sense that they exhibit the exact same performance rate. Because of the high prevalence of feed-forward functional modules in biological networks, one may hypothesize that evolution tends to favour motifs with faster dynamics. As a step towards ranking the efficiency of feed-forward network motifs, we use a linear flow model to prove theorems establishing that certain classes of motifs are isodynamic. In partitioning the class of all motifs on n nodes into equivalence classes based upon their dynamics, we establish a basis for comparing the efficiency/performance rates of different motifs. The potential biological importance of the theorems is briefly discussed and is the subject of an ongoing large-scale project.     

A path-based computational model for long non-coding RNA-protein interaction prediction

Recently, lncRNAs have attracted accumulating attentions because more and more experimental researches have shown lncRNA can play critical roles in many biological processes. Predicting potential interactions between lncRNAs and proteins are key to understand the lncRNAs biological functions. But traditional biological experiments are expensive and time-consuming, network similarity methods provide a powerful solution to computationally predict lncRNA-protein interactions. In this work, a novel path-based lncRNA-protein interaction (PBLPI) prediction model is proposed by integrating protein semantic similarity, lncRNA functional similarity, known human lncRNA-protein interactions, and Gaussian interaction profile kernel similarity. PBLPI model utilizes three interlinked sub-graphs to construct a heterogeneous graph, and then infers potential lncRNA-protein interactions through depth-first search algorithm. Consequently, PBLPI achieves reliable performance in the frameworks of 5-fold cross validation (average AUC is 0.9244 and AUPR is 0.6478). In the case study, we use “Mus musculus” data to further validate the reliability of PBLPI method. It is anticipated that PBLPI would become a useful tool to identify potential lncRNA-protein interactions.     

Failure tolerance of motif structure in biological networks

Complex networks serve as generic models for many biological systems that have been shown to share a number of common structural properties such as power-law degree distribution and small-worldness. Real-world networks are composed of building blocks called motifs that are indeed specific subgraphs of (usually) small number of nodes. Network motifs are important in the functionality of complex networks, and the role of some motifs such as feed-forward loop in many biological networks has been heavily studied. On the other hand, many biological networks have shown some degrees of robustness in terms of their efficiency and connectedness against failures in their components. In this paper we investigated how random and systematic failures in the edges of biological networks influenced their motif structure. We considered two biological networks, namely, protein structure network and human brain functional network. Furthermore, we considered random failures as well as systematic failures based on different strategies for choosing candidate edges for removal. Failure in the edges tipping to high degree nodes had the most destructive role in the motif structure of the networks by decreasing their significance level, while removing edges that were connected to nodes with high values of betweenness centrality had the least effect on the significance profiles. In some cases, the latter caused increase in the significance levels of the motifs.     

Chaotic motifs in gene regulatory networks

Chaos should occur often in gene regulatory networks (GRNs) which have been widely described by nonlinear coupled ordinary differential equations, if their dimensions are no less than 3. It is therefore puzzling that chaos has never been reported in GRNs in nature and is also extremely rare in models of GRNs. On the other hand, the topic of motifs has attracted great attention in studying biological networks, and network motifs are suggested to be elementary building blocks that carry out some key functions in the network. In this paper, chaotic motifs (subnetworks with chaos) in GRNs are systematically investigated. The conclusion is that: (i) chaos can only appear through competitions between different oscillatory modes with rivaling intensities. Conditions required for chaotic GRNs are found to be very strict, which make chaotic GRNs extremely rare. (ii) Chaotic motifs are explored as the simplest few-node structures capable of producing chaos, and serve as the intrinsic source of chaos of random few-node GRNs. Several optimal motifs causing chaos with atypically high probability are figured out. (iii) Moreover, we discovered that a number of special oscillators can never produce chaos. These structures bring some advantages on rhythmic functions and may help us understand the robustness of diverse biological rhythms. (iv) The methods of dominant phase-advanced driving (DPAD) and DPAD time fraction are proposed to quantitatively identify chaotic motifs and to explain the origin of chaotic behaviors in GRNs.     

Dynamic network rewiring determines temporal regulatory functions in Drosophila melanogaster development processes

The identification of network motifs has been widely considered as a significant step towards uncovering the design principles of biomolecular regulatory networks. To date, time‐invariant networks have been considered. However, such approaches cannot be used to reveal time‐specific biological traits due to the dynamic nature of biological systems, and hence may not be applicable to development, where temporal regulation of gene expression is an indispensable characteristic. We propose a concept of a “temporal sequence of network motifs”, a sequence of network motifs in active sub‐networks constructed over time, and investigate significant network motifs in the active temporal sub‐networks of Drosophila melanogaster . Based on this concept, we find a temporal sequence of network motifs which changes according to developmental stages and thereby cannot be identified from the whole static network. Moreover, we show that the temporal sequence of network motifs corresponding to each developmental stage can be used to describe pivotal developmental events.     

Toward a classification of isodynamic feed-forward motifs

A preceding study analysed how the topology of network motifs affects the overall rate of the underlying biochemical processes. Surprisingly, it was shown that topologically non-isomorphic motifs can still be isodynamic in the sense that they exhibit the exact same performance rate. Because of the high prevalence of feed-forward functional modules in biological networks, one may hypothesize that evolution tends to favour motifs with faster dynamics. As a step towards ranking the efficiency of feed-forward network motifs, we use a linear flow model to prove theorems establishing that certain classes of motifs are isodynamic. In partitioning the class of all motifs on n nodes into equivalence classes based upon their dynamics, we establish a basis for comparing the efficiency/performance rates of different motifs. The potential biological importance of the theorems is briefly discussed and is the subject of an ongoing large-scale project.     

Exact algorithms for planted motif problems.

The problem of identifying meaningful patterns (i.e., motifs) from biological data has been studied extensively due to its paramount importance. Three versions of this problem have been identified in the literature. One of these three problems is the planted (l, d)-motif problem. Several instances of this problem have been posed as a challenge. Numerous algorithms have been proposed in the literature that address this challenge. Many of these algorithms fall under the category of heuristic algorithms. In this paper we present algorithms for the planted (l, d)-motif problem that always find the correct answer(s). Our algorithms are very simple and are based on some ideas that are fundamentally different from the ones employed in the literature. We believe that the techniques we introduce in this paper will find independent applications.     

The Index-Based Subgraph Matching Algorithm with General Symmetries (ISMAGS): Exploiting Symmetry for Faster Subgraph Enumeration

Subgraph matching algorithms are used to find and enumerate specific interconnection structures in networks. By enumerating these specific structures/subgraphs, the fundamental properties of the network can be derived. More specifically in biological networks, subgraph matching algorithms are used to discover network motifs, specific patterns occurring more often than expected by chance. Finding these network motifs yields information on the underlying biological relations modelled by the network. In this work, we present the Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS), an improved version of the Index-based Subgraph Matching Algorithm (ISMA). ISMA quickly finds all instances of a predefined motif in a network by intelligently exploring the search space and taking into account easily identifiable symmetric structures. However, more complex symmetries (possibly involving switching multiple nodes) are not taken into account, resulting in superfluous output. ISMAGS overcomes this problem by using a customised symmetry analysis phase to detect all symmetric structures in the network motif subgraphs. These structures are then converted to symmetry-breaking constraints used to prune the search space and speed up calculations. The performance of the algorithm was tested on several types of networks (biological, social and computer networks) for various subgraphs with a varying degree of symmetry. For subgraphs with complex (multi-node) symmetric structures, high speed-up factors are obtained as the search space is pruned by the symmetry-breaking constraints. For subgraphs with no or simple symmetric structures, ISMAGS still reduces computation times by optimising set operations. Moreover, the calculated list of subgraph instances is minimal as it contains no instances that differ by only a subgraph symmetry. An implementation of the algorithm is freely available at https://github.com/mhoubraken/ISMAGS.