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/     

A network synthesis model for generating protein interaction network families

In this work, we introduce a novel network synthesis model that can generate families of evolutionarily related synthetic protein-protein interaction (PPI) networks. Given an ancestral network, the proposed model generates the network family according to a hypothetical phylogenetic tree, where the descendant networks are obtained through duplication and divergence of their ancestors, followed by network growth using network evolution models. We demonstrate that this network synthesis model can effectively create synthetic networks whose internal and cross-network properties closely resemble those of real PPI networks. The proposed model can serve as an effective framework for generating comprehensive benchmark datasets that can be used for reliable performance assessment of comparative network analysis algorithms. Using this model, we constructed a large-scale network alignment benchmark, called NAPAbench, and evaluated the performance of several representative network alignment algorithms. Our analysis clearly shows the relative performance of the leading network algorithms, with their respective advantages and disadvantages. The algorithm and source code of the network synthesis model and the network alignment benchmark NAPAbench are publicly available at http://www.ece.tamu.edu/bjyoon/NAPAbench/.     

Efficient detection of network motifs

Motifs in a given network are small connected subnetworks that occur in significantly higher frequencies than would be expected in random networks. They have recently gathered much attention as a concept to uncover structural design principles of complex networks. Kashtan et al. [Bioinformatics, 2004] proposed a sampling algorithm for performing the computationally challenging task of detecting network motifs. However, among other drawbacks, this algorithm suffers from a sampling bias and scales poorly with increasing subgraph size. Based on a detailed analysis of the previous algorithm, we present a new algorithm for network motif detection which overcomes these drawbacks. Furthermore, we present an efficient new approach for estimating the frequency of subgraphs in random networks that, in contrast to previous approaches, does not require the explicit generation of random networks. Experiments on a testbed of biological networks show our new algorithms to be orders of magnitude faster than previous approaches, allowing for the detection of larger motifs in bigger networks than previously possible and thus facilitating deeper insight into the field     

The network structure of myrmecophilic interactions

1. Ants establish mutualistic interactions involving a wide range of protective relationships (myrmecophily), in which they provide defence against enemies and partners provide food rewards and/or refuge. Although similar in the general outcome, myrmecophilic interactions differ in some characteristics such as quantity and quality of rewards offered by partners which may lead to different specialisation levels and, consequently, to different network properties. 2. The aim of this study was to identify structural patterns in myrmecophilic interaction networks, focusing on aspects related to specialisation: network modularity, nestedness and taxonomic relatedness of interaction ranges. To achieve this, a database of networks was compiled, including the following interactions: ants and domatia‐bearing plants (myrmecophytes); ants and extrafloral nectary‐bearing plants (EFNs); ants and floral nectary‐bearing plants (FNs); ants and Lepidoptera caterpillars; and ants and Hemiptera. 3. Myrmecophilic networks differed in their topology, with ant–myrmecophyte and ant–Lepidoptera networks being similar in their structural properties. A continuum was found, ranging from highly modular networks and phylogenetically structured interaction ranges in ant–myrmecophyte followed by ant–Lepidoptera networks to low modularity and taxonomically unrelated interaction ranges in ant–Hemiptera, EFN and FN networks. 4. These results suggest that different network topologies may be found across communities of species with similar interaction types, but also, that similar network topologies can be achieved through different mechanisms such as those between ants and myrmecophytes or Lepidoptera larvae. This study contributes to a generalisation of myrmecophilic network patterns and a better understanding of the relationship between specialisation and network topology.     

Advances to Bayesian network inference for generating causal networks from observational biological data

MOTIVATION: Network inference algorithms are powerful computational tools for identifying putative causal interactions among variables from observational data. Bayesian network inference algorithms hold particular promise in that they can capture linear, non-linear, combinatorial, stochastic and other types of relationships among variables across multiple levels of biological organization. However, challenges remain when applying these algorithms to limited quantities of experimental data collected from biological systems. Here, we use a simulation approach to make advances in our dynamic Bayesian network (DBN) inference algorithm, especially in the context of limited quantities of biological data. RESULTS: We test a range of scoring metrics and search heuristics to find an effective algorithm configuration for evaluating our methodological advances. We also identify sampling intervals and levels of data discretization that allow the best recovery of the simulated networks. We develop a novel influence score for DBNs that attempts to estimate both the sign (activation or repression) and relative magnitude of interactions among variables. When faced with limited quantities of observational data, combining our influence score with moderate data interpolation reduces a significant portion of false positive interactions in the recovered networks. Together, our advances allow DBN inference algorithms to be more effective in recovering biological networks from experimentally collected data. AVAILABILITY: Source code and simulated data are available upon request. SUPPLEMENTARY INFORMATION: http://www.jarvislab.net/Bioinformatics/BNAdvances/     

An efficient network querying method based on conditional random fields

MOTIVATION: A large amount of biomolecular network data for multiple species have been generated by high-throughput experimental techniques, including undirected and directed networks such as protein-protein interaction networks, gene regulatory networks and metabolic networks. There are many conserved functionally similar modules and pathways among multiple biomolecular networks in different species; therefore, it is important to analyze the similarity between the biomolecular networks. Network querying approaches aim at efficiently discovering the similar subnetworks among different species. However, many existing methods only partially solve this problem. RESULTS: In this article, a novel approach for network querying problem based on conditional random fields (CRFs) model is presented, which can handle both undirected and directed networks, acyclic and cyclic networks and any number of insertions/deletions. The CRF method is fast and can query pathways in a large network in seconds using a PC. To evaluate the CRF method, extensive computational experiments are conducted on the simulated and real data, and the results are compared with the existing network querying methods. All results show that the CRF method is very useful and efficient to find the conserved functionally similar modules and pathways in multiple biomolecular networks.     

Sets2Networks: network inference from repeated observations of sets

Background

The skeleton of complex systems can be represented as networks where vertices represent entities, and edges represent the relations between these entities. Often it is impossible, or expensive, to determine the network structure by experimental validation of the binary interactions between every vertex pair. It is usually more practical to infer the network from surrogate observations. Network inference is the process by which an underlying network of relations between entities is determined from indirect evidence. While many algorithms have been developed to infer networks from quantitative data, less attention has been paid to methods which infer networks from repeated co-occurrence of entities in related sets. This type of data is ubiquitous in the field of systems biology and in other areas of complex systems research. Hence, such methods would be of great utility and value.

Results

Here we present a general method for network inference from repeated observations of sets of related entities. Given experimental observations of such sets, we infer the underlying network connecting these entities by generating an ensemble of networks consistent with the data. The frequency of occurrence of a given link throughout this ensemble is interpreted as the probability that the link is present in the underlying real network conditioned on the data. Exponential random graphs are used to generate and sample the ensemble of consistent networks, and we take an algorithmic approach to numerically execute the inference method. The effectiveness of the method is demonstrated on synthetic data before employing this inference approach to problems in systems biology and systems pharmacology, as well as to construct a co-authorship collaboration network. We predict direct protein-protein interactions from high-throughput mass-spectrometry proteomics, integrate data from Chip-seq and loss-of-function/gain-of-function followed by expression data to infer a network of associations between pluripotency regulators, extract a network that connects 53 cancer drugs to each other and to 34 severe adverse events by mining the FDA’s Adverse Events Reporting Systems (AERS), and construct a co-authorship network that connects Mount Sinai School of Medicine investigators. The predicted networks and online software to create networks from entity-set libraries are provided online at http://www.maayanlab.net/S2N.

Conclusions

The network inference method presented here can be applied to resolve different types of networks in current systems biology and systems pharmacology as well as in other fields of research.     

Electrical coupling of photoreceptors in retinal network models

The spatial width of photoreceptor receptive fields affects the processing of signals in neural networks of the retina. This effect has been examined using the simple recurrent and non-recurrent network models, where lateral interaction strength was adjusted to approximate a prescribed receptive field profile. The results indicate that the optimal performance of the networks is obtained with photoreceptor receptive fields wider than the ganglion cell separation. It is thus concluded that while electrical coupling of photoreceptors in the retina reduces the intrinsic noise in the system, it also improves the sampling efficiency of the laterally coupled neural network of the retina.     

Identifying biological network structure, predicting network behavior, and classifying network state with High Dimensional Model Representation (HDMR)

This work presents an adapted Random Sampling - High Dimensional Model Representation (RS-HDMR) algorithm for synergistically addressing three key problems in network biology: (1) identifying the structure of biological networks from multivariate data, (2) predicting network response under previously unsampled conditions, and (3) inferring experimental perturbations based on the observed network state. RS-HDMR is a multivariate regression method that decomposes network interactions into a hierarchy of non-linear component functions. Sensitivity analysis based on these functions provides a clear physical and statistical interpretation of the underlying network structure. The advantages of RS-HDMR include efficient extraction of nonlinear and cooperative network relationships without resorting to discretization, prediction of network behavior without mechanistic modeling, robustness to data noise, and favorable scalability of the sampling requirement with respect to network size. As a proof-of-principle study, RS-HDMR was applied to experimental data measuring the single-cell response of a protein-protein signaling network to various experimental perturbations. A comparison to network structure identified in the literature and through other inference methods, including Bayesian and mutual-information based algorithms, suggests that RS-HDMR can successfully reveal a network structure with a low false positive rate while still capturing non-linear and cooperative interactions. RS-HDMR identified several higher-order network interactions that correspond to known feedback regulations among multiple network species and that were unidentified by other network inference methods. Furthermore, RS-HDMR has a better ability to predict network response under unsampled conditions in this application than the best statistical inference algorithm presented in the recent DREAM3 signaling-prediction competition. RS-HDMR can discern and predict differences in network state that arise from sources ranging from intrinsic cell-cell variability to altered experimental conditions, such as when drug perturbations are introduced. This ability ultimately allows RS-HDMR to accurately classify the experimental conditions of a given sample based on its observed network state.     

Enabling dynamic network analysis through visualization in TVNViewer

ABSTRACT: BACKGROUND: Many biological processes are context-dependent or temporally specific. As a result, relationships between molecular constituents evolve across time and environments. While cutting-edge machine learning techniques can recover these networks, exploring and interpreting the rewiring behavior is challenging. Information visualization shines in this type of exploratory analysis, motivating the development of TVNViewer (http://sailing.cs.cmu.edu/tvnviewer), a visualization tool for dynamic network analysis. RESULTS: In this paper, we demonstrate visualization techniques for dynamic network analysis by using TVNViewer to analyze yeast cell cycle and breast cancer progression datasets. CONCLUSIONS: TVNViewer is a powerful new visualization tool for the analysis of biological networks that change across time or space.     

动物移动网络研究对景观生态学的贡献

景观生态学在其发展之初的20世纪80年代, 提出了关于景观网络研究(包括景观网络概念、网络结构指数和景观连接度)的基本构想, 这些构想需要在景观过程的研究中逐渐被落实和发展。动物移动过程因动物在斑块或廊道上有着独特丰富的属性特征、与周围资源环境之间存在复杂反馈而区别于无机物运移的景观过程, 则动物移动网络研究在实现关于景观网络研究的基本构想、推动景观生态学发展中贡献独特。因此, 总结动物移动网络研究的来源脉络及其对景观生态学的理论贡献对于景观网络领域和景观生态学学科的发展都具有重要意义。本文抓住景观生态学发展之初提出的关于景观网络研究的基本构想, 寻找和剖析其中所蕴含的景观生态学思想, 追踪这些思想如何被落实、发展、并形成目前的三个热点方向: 动物移动网络模拟、重要值评价和景观连接度分析; 总结这三个方向的研究进展, 指出整合动物的空间行为特征是必然发展趋势; 揭示出动物移动网络研究始终都以发掘斑块或廊道的动物有机体的属性特征(如种群数量)、以及描述这种属性在不同斑块或廊道之间的差异和联系为方向, 正是这种属性的发掘有效地落实、发展和丰富了关于景观网络研究的最初构想, 对景观生态学的贡献比其他过程更为独特。文章还总结了我国动物移动网络研究与国际研究相比较为滞后的现状, 指出其暂时尚未显示出对我国景观生态学的独特贡献; 强调发展源于跟踪定位数据的动物空间行为生态学研究是减小差距的重要、必要前提。期望本文能引发关于景观网络乃至景观生态学理论发展的方向性思考, 为研究者提供参考。     

Inferring general relations between network characteristics from specific network ensembles

Different network models have been suggested for the topology underlying complex interactions in natural systems. These models are aimed at replicating specific statistical features encountered in real-world networks. However, it is rarely considered to which degree the results obtained for one particular network class can be extrapolated to real-world networks. We address this issue by comparing different classical and more recently developed network models with respect to their ability to generate networks with large structural variability. In particular, we consider the statistical constraints which the respective construction scheme imposes on the generated networks. After having identified the most variable networks, we address the issue of which constraints are common to all network classes and are thus suitable candidates for being generic statistical laws of complex networks. In fact, we find that generic, not model-related dependencies between different network characteristics do exist. This makes it possible to infer global features from local ones using regression models trained on networks with high generalization power. Our results confirm and extend previous findings regarding the synchronization properties of neural networks. Our method seems especially relevant for large networks, which are difficult to map completely, like the neural networks in the brain. The structure of such large networks cannot be fully sampled with the present technology. Our approach provides a method to estimate global properties of under-sampled networks in good approximation. Finally, we demonstrate on three different data sets (C. elegans neuronal network, R. prowazekii metabolic network, and a network of synonyms extracted from Roget's Thesaurus) that real-world networks have statistical relations compatible with those obtained using regression models.     

Gene regulatory network modeling via global optimization of high-order dynamic Bayesian network

ABSTRACT: BACKGROUND: Dynamic Bayesian network (DBN) is among the mainstream approaches for modeling various biological networks, including the gene regulatory network (GRN). Most current methods for learning DBN employ either local search such as hill-climbing, or a meta stochastic global optimization framework such as genetic algorithm or simulated annealing, which are only able to locate sub-optimal solutions. Further, current DBN applications have essentially been limited to small sized networks. RESULTS: To overcome the above difficulties, we introduce here a deterministic global optimization based DBN approach for reverse engineering genetic networks from time course gene expression data. For such DBN models that consist only of inter time slice arcs, we show that there exists a polynomial time algorithm for learning the globally optimal network structure. The proposed approach, named GlobalMIT+, employs the recently proposed information theoretic scoring metric named mutual information test (MIT). GlobalMIT+ is able to learn high-order time delayed genetic interactions, which are common to most biological systems. Evaluation of the approach using both synthetic and real data sets, including a 733 cyanobacterial gene expression data set, shows significantly improved performance over other techniques. CONCLUSIONS: Our studies demonstrate that deterministic global optimization approaches can infer large scale genetic networks.     

Cobweb: a Java applet for network exploration and visualisation

SUMMARY: Cobweb is a Java applet for real-time network visualization; its strength lies in enabling the interactive exploration of networks. Therefore, it allows new nodes to be interactively added to a network by querying a database on a server. The network constantly rearranges to provide the most meaningful topological view. AVAILABILITY: Cobweb is available under the GPLv3 and may be freely downloaded at http://bioinformatics.charite.de/cobweb.     

Preliminary screening of neural network configurations for bioreactor applications

Summary A methodology and a computer code have been devised to perform a preliminary analysis of six types of neural networks commonly employed for bioreactor problems. Both static and time-varying data can be analysed, and the values of the parameters and/or sampling times can be chosen according to the system behavior. The results help to select a suitable network configuration for detailed training and application. This is illustrated for a fed-batch fermentation to produce recombinant -galactosidase.