Replicating disease spread in empirical cattle networks by adjusting the probability of infection in random networks

Comparisons between mass-action or “random” network models and empirical networks have produced mixed results. Here we seek to discover whether a simulated disease spread through randomly constructed networks can be coerced to model the spread in empirical networks by altering a single disease parameter — the probability of infection. A stochastic model for disease spread through herds of cattle is utilised to model the passage of an SEIR (susceptible–latent–infected–resistant) through five networks. The first network is an empirical network of recorded contacts, from four datasets available, and the other four networks are constructed from randomly distributed contacts based on increasing amounts of information from the recorded network. A numerical study on adjusting the value of the probability of infection was conducted for the four random network models. We found that relative percentage reductions in the probability of infection, between 5.6% and 39.4% in the random network models, produced results that most closely mirrored the results from the empirical contact networks. In all cases tested, to reduce the differences between the two models, required a reduction in the probability of infection in the random network.     

Robustness and evolvability in genetic regulatory networks

Living organisms are robust to a great variety of genetic changes. Gene regulation networks and metabolic pathways self-organize and reaccommodate to make the organism perform with stability and reliability under many point mutations, gene duplications and gene deletions. At the same time, living organisms are evolvable, which means that these kind of genetic perturbations can eventually make the organism acquire new functions and adapt to new environments. It is still an open problem to determine how robustness and evolvability blend together at the genetic level to produce stable organisms that yet can change and evolve. Here we address this problem by studying the robustness and evolvability of the attractor landscape of genetic regulatory network models under the process of gene duplication followed by divergence. We show that an intrinsic property of this kind of networks is that, after the divergence of the parent and duplicate genes, with a high probability the previous phenotypes, encoded in the attractor landscape of the network, are preserved and new ones might appear. The above is true in a variety of network topologies and even for the case of extreme divergence in which the duplicate gene bears almost no relation with its parent. Our results indicate that networks operating close to the so-called "critical regime" exhibit the maximum robustness and evolvability simultaneously.     

A scale-free structure prior for graphical models with applications in functional genomics

The problem of reconstructing large-scale, gene regulatory networks from gene expression data has garnered considerable attention in bioinformatics over the past decade with the graphical modeling paradigm having emerged as a popular framework for inference. Analysis in a full Bayesian setting is contingent upon the assignment of a so-called structure prior-a probability distribution on networks, encoding a priori biological knowledge either in the form of supplemental data or high-level topological features. A key topological consideration is that a wide range of cellular networks are approximately scale-free, meaning that the fraction, , of nodes in a network with degree is roughly described by a power-law with exponent between and . The standard practice, however, is to utilize a random structure prior, which favors networks with binomially distributed degree distributions. In this paper, we introduce a scale-free structure prior for graphical models based on the formula for the probability of a network under a simple scale-free network model. Unlike the random structure prior, its scale-free counterpart requires a node labeling as a parameter. In order to use this prior for large-scale network inference, we design a novel Metropolis-Hastings sampler for graphical models that includes a node labeling as a state space variable. In a simulation study, we demonstrate that the scale-free structure prior outperforms the random structure prior at recovering scale-free networks while at the same time retains the ability to recover random networks. We then estimate a gene association network from gene expression data taken from a breast cancer tumor study, showing that scale-free structure prior recovers hubs, including the previously unknown hub SLC39A6, which is a zinc transporter that has been implicated with the spread of breast cancer to the lymph nodes. Our analysis of the breast cancer expression data underscores the value of the scale-free structure prior as an instrument to aid in the identification of candidate hub genes with the potential to direct the hypotheses of molecular biologists, and thus drive future experiments.     

A Scalable Computational Framework for Establishing Long-Term Behavior of Stochastic Reaction Networks

Reaction networks are systems in which the populations of a finite number of species evolve through predefined interactions. Such networks are found as modeling tools in many biological disciplines such as biochemistry, ecology, epidemiology, immunology, systems biology and synthetic biology. It is now well-established that, for small population sizes, stochastic models for biochemical reaction networks are necessary to capture randomness in the interactions. The tools for analyzing such models, however, still lag far behind their deterministic counterparts. In this paper, we bridge this gap by developing a constructive framework for examining the long-term behavior and stability properties of the reaction dynamics in a stochastic setting. In particular, we address the problems of determining ergodicity of the reaction dynamics, which is analogous to having a globally attracting fixed point for deterministic dynamics. We also examine when the statistical moments of the underlying process remain bounded with time and when they converge to their steady state values. The framework we develop relies on a blend of ideas from probability theory, linear algebra and optimization theory. We demonstrate that the stability properties of a wide class of biological networks can be assessed from our sufficient theoretical conditions that can be recast as efficient and scalable linear programs, well-known for their tractability. It is notably shown that the computational complexity is often linear in the number of species. We illustrate the validity, the efficiency and the wide applicability of our results on several reaction networks arising in biochemistry, systems biology, epidemiology and ecology. The biological implications of the results as well as an example of a non-ergodic biological network are also discussed.     

Preferential Duplication of Intermodular Hub Genes: An Evolutionary Signature in Eukaryotes Genome Networks

Whole genome protein-protein association networks are not random and their topological properties stem from genome evolution mechanisms. In fact, more connected, but less clustered proteins are related to genes that, in general, present more paralogs as compared to other genes, indicating frequent previous gene duplication episodes. On the other hand, genes related to conserved biological functions present few or no paralogs and yield proteins that are highly connected and clustered. These general network characteristics must have an evolutionary explanation. Considering data from STRING database, we present here experimental evidence that, more than not being scale free, protein degree distributions of organisms present an increased probability for high degree nodes. Furthermore, based on this experimental evidence, we propose a simulation model for genome evolution, where genes in a network are either acquired de novo using a preferential attachment rule, or duplicated with a probability that linearly grows with gene degree and decreases with its clustering coefficient. For the first time a model yields results that simultaneously describe different topological distributions. Also, this model correctly predicts that, to produce protein-protein association networks with number of links and number of nodes in the observed range for Eukaryotes, it is necessary 90% of gene duplication and 10% of de novo gene acquisition. This scenario implies a universal mechanism for genome evolution.     

Superiority of network motifs over optimal networks and an application to the revelation of gene network evolution

MOTIVATION: Estimating the network of regulative interactions between genes from gene expression measurements is a major challenge. Recently, we have shown that for gene networks of up to around 35 genes, optimal network models can be computed. However, even optimal gene network models will in general contain false edges, since the expression data will not unambiguously point to a single network. RESULTS: In order to overcome this problem, we present a computational method to enumerate the most likely m networks and to extract a widely common subgraph (denoted as gene network motif) from these. We apply the method to bacterial gene expression data and extensively compare estimation results to knowledge. Our results reveal that gene network motifs are in significantly better agreement to biological knowledge than optimal network models. We also confirm this observation in a series of estimations using synthetic microarray data and compare estimations by our method with previous estimations for yeast. Furthermore, we use our method to estimate similarities and differences of the gene networks that regulate tryptophan metabolism in two related species and thereby demonstrate the analysis of gene network evolution. AVAILABILITY: Commercial license negotiable with Gene Networks Inc. (cherkis@gene-networks.com) CONTACT: sascha-ott@gmx.net     

The effects of network neighbours on protein evolution

Interacting proteins may often experience similar selection pressures. Thus, we may expect that neighbouring proteins in biological interaction networks evolve at similar rates. This has been previously shown for protein-protein interaction networks. Similarly, we find correlated rates of evolution of neighbours in networks based on co-expression, metabolism, and synthetic lethal genetic interactions. While the correlations are statistically significant, their magnitude is small, with network effects explaining only between 2% and 7% of the variation. The strongest known predictor of the rate of protein evolution remains expression level. We confirmed the previous observation that similar expression levels of neighbours indeed explain their similar evolution rates in protein-protein networks, and showed that the same is true for metabolic networks. In co-expression and synthetic lethal genetic interaction networks, however, neighbouring genes still show somewhat similar evolutionary rates even after simultaneously controlling for expression level, gene essentiality and gene length. Thus, similar expression levels and related functions (as inferred from co-expression and synthetic lethal interactions) seem to explain correlated evolutionary rates of network neighbours across all currently available types of biological networks.     

Maximum Number of Fixed Points in Regulatory Boolean Networks

Boolean networks (BNs) have been extensively used as mathematical models of genetic regulatory networks. The number of fixed points of a BN is a key feature of its dynamical behavior. Here, we study the maximum number of fixed points in a particular class of BNs called regulatory Boolean networks, where each interaction between the elements of the network is either an activation or an inhibition. We find relationships between the positive and negative cycles of the interaction graph and the number of fixed points of the network. As our main result, we exhibit an upper bound for the number of fixed points in terms of minimum cardinality of a set of vertices meeting all positive cycles of the network, which can be applied in the design of genetic regulatory networks.     

Interplay between Graph Topology and Correlations of Third Order in Spiking Neuronal Networks

The study of processes evolving on networks has recently become a very popular research field, not only because of the rich mathematical theory that underpins it, but also because of its many possible applications, a number of them in the field of biology. Indeed, molecular signaling pathways, gene regulation, predator-prey interactions and the communication between neurons in the brain can be seen as examples of networks with complex dynamics. The properties of such dynamics depend largely on the topology of the underlying network graph. In this work, we want to answer the following question: Knowing network connectivity, what can be said about the level of third-order correlations that will characterize the network dynamics? We consider a linear point process as a model for pulse-coded, or spiking activity in a neuronal network. Using recent results from theory of such processes, we study third-order correlations between spike trains in such a system and explain which features of the network graph (i.e. which topological motifs) are responsible for their emergence. Comparing two different models of network topology—random networks of Erdős-Rényi type and networks with highly interconnected hubs—we find that, in random networks, the average measure of third-order correlations does not depend on the local connectivity properties, but rather on global parameters, such as the connection probability. This, however, ceases to be the case in networks with a geometric out-degree distribution, where topological specificities have a strong impact on average correlations.     

Efficient reverse-engineering of a developmental gene regulatory network

Understanding the complex regulatory networks underlying development and evolution of multi-cellular organisms is a major problem in biology. Computational models can be used as tools to extract the regulatory structure and dynamics of such networks from gene expression data. This approach is called reverse engineering. It has been successfully applied to many gene networks in various biological systems. However, to reconstitute the structure and non-linear dynamics of a developmental gene network in its spatial context remains a considerable challenge. Here, we address this challenge using a case study: the gap gene network involved in segment determination during early development of Drosophila melanogaster. A major problem for reverse-engineering pattern-forming networks is the significant amount of time and effort required to acquire and quantify spatial gene expression data. We have developed a simplified data processing pipeline that considerably increases the throughput of the method, but results in data of reduced accuracy compared to those previously used for gap gene network inference. We demonstrate that we can infer the correct network structure using our reduced data set, and investigate minimal data requirements for successful reverse engineering. Our results show that timing and position of expression domain boundaries are the crucial features for determining regulatory network structure from data, while it is less important to precisely measure expression levels. Based on this, we define minimal data requirements for gap gene network inference. Our results demonstrate the feasibility of reverse-engineering with much reduced experimental effort. This enables more widespread use of the method in different developmental contexts and organisms. Such systematic application of data-driven models to real-world networks has enormous potential. Only the quantitative investigation of a large number of developmental gene regulatory networks will allow us to discover whether there are rules or regularities governing development and evolution of complex multi-cellular organisms.     

On analytical approaches to epidemics on networks

One way to describe the spread of an infection on a network is by approximating the network by a random graph. However, the usual way of constructing a random graph does not give any control over the number of triangles in the graph, while these triangles will naturally arise in many networks (e.g. in social networks). In this paper, random graphs with a given degree distribution and a given expected number of triangles are constructed. By using these random graphs we analyze the spread of two types of infection on a network: infections with a fixed infectious period and infections for which an infective individual will infect all of its susceptible neighbors or none. These two types of infection can be used to give upper and lower bounds for R(0), the probability of extinction and other measures of dynamics of infections with more general infectious periods.     

Identification of functional modules from conserved ancestral protein-protein interactions

MOTIVATION: The increasing availability of large-scale protein-protein interaction (PPI) data has fueled the efforts to elucidate the building blocks and organization of cellular machinery. Previous studies have shown cross-species comparison to be an effective approach in uncovering functional modules in protein networks. This has in turn driven the research for new network alignment methods with a more solid grounding in network evolution models and better scalability, to allow multiple network comparison. RESULTS: We develop a new framework for protein network alignment, based on reconstruction of an ancestral PPI network. The reconstruction algorithm is built upon a proposed model of protein network evolution, which takes into account phylogenetic history of the proteins and the evolution of their interactions. The application of our methodology to the PPI networks of yeast, worm and fly reveals that the most probable conserved ancestral interactions are often related to known protein complexes. By projecting the conserved ancestral interactions back onto the input networks we are able to identify the corresponding conserved protein modules in the considered species. In contrast to most of the previous methods, our algorithm is able to compare many networks simultaneously. The performed experiments demonstrate the ability of our method to uncover many functional modules with high specificity. AVAILABILITY: Information for obtaining software and supplementary results are available at http://bioputer.mimuw.edu.pl/papers/cappi.     

Analysis of gene network robustness based on saturated fixed point attractors

The analysis of gene network robustness to noise and mutation is important for fundamental and practical reasons. Robustness refers to the stability of the equilibrium expression state of a gene network to variations of the initial expression state and network topology. Numerical simulation of these variations is commonly used for the assessment of robustness. Since there exists a great number of possible gene network topologies and initial states, even millions of simulations may be still too small to give reliable results. When the initial and equilibrium expression states are restricted to being saturated (i.e., their elements can only take values 1 or −1 corresponding to maximum activation and maximum repression of genes), an analytical gene network robustness assessment is possible. We present this analytical treatment based on determination of the saturated fixed point attractors for sigmoidal function models. The analysis can determine (a) for a given network, which and how many saturated equilibrium states exist and which and how many saturated initial states converge to each of these saturated equilibrium states and (b) for a given saturated equilibrium state or a given pair of saturated equilibrium and initial states, which and how many gene networks, referred to as viable, share this saturated equilibrium state or the pair of saturated equilibrium and initial states. We also show that the viable networks sharing a given saturated equilibrium state must follow certain patterns. These capabilities of the analytical treatment make it possible to properly define and accurately determine robustness to noise and mutation for gene networks. Previous network research conclusions drawn from performing millions of simulations follow directly from the results of our analytical treatment. Furthermore, the analytical results provide criteria for the identification of model validity and suggest modified models of gene network dynamics. The yeast cell-cycle network is used as an illustration of the practical application of this analytical treatment.     

Intervention in a family of Boolean networks

MOTIVATION: Intervention in a gene regulatory network is used to avoid undesirable states, such as those associated with a disease. Several types of intervention have been studied in the framework of a probabilistic Boolean network (PBN), which is a collection of Boolean networks in which the gene state vector transitions according to the rules of one of the constituent networks and where network choice is governed by a selection distribution. The theory of automatic control has been applied to find optimal strategies for manipulating external control variables that affect the transition probabilities to desirably affect dynamic evolution over a finite time horizon. In this paper we treat a case in which we lack the governing probability structure for Boolean network selection, so we simply have a family of Boolean networks, but where these networks possess a common attractor structure. This corresponds to the situation in which network construction is treated as an ill-posed inverse problem in which there are many Boolean networks created from the data under the constraint that they all possess attractor structures matching the data states, which are assumed to arise from sampling the steady state of the real biological network. RESULTS: Given a family of Boolean networks possessing a common attractor structure composed of singleton attractors, a control algorithm is derived by minimizing a composite finite-horizon cost function that is a weighted average over all the individual networks, the idea being that we desire a control policy that on average suits the networks because these are viewed as equivalent relative to the data. The weighting for each network at any time point is taken to be proportional to the instantaneous estimated probability of that network being the underlying network governing the state transition. The results are applied to a family of Boolean networks derived from gene-expression data collected in a study of metastatic melanoma, the intent being to devise a control strategy that reduces the WNT5A gene's action in affecting biological regulation. AVAILABILITY: The software is available on request. SUPPLEMENTARY INFORMATION: The supplementary Information is available at http://ee.tamu.edu/~edward/tree     

Age-Dependent Evolution of the Yeast Protein Interaction Network Suggests a Limited Role of Gene Duplication and Divergence

Proteins interact in complex protein–protein interaction (PPI) networks whose topological properties—such as scale-free topology, hierarchical modularity, and dissortativity—have suggested models of network evolution. Currently preferred models invoke preferential attachment or gene duplication and divergence to produce networks whose topology matches that observed for real PPIs, thus supporting these as likely models for network evolution. Here, we show that the interaction density and homodimeric frequency are highly protein age–dependent in real PPI networks in a manner which does not agree with these canonical models. In light of these results, we propose an alternative stochastic model, which adds each protein sequentially to a growing network in a manner analogous to protein crystal growth (CG) in solution. The key ideas are (1) interaction probability increases with availability of unoccupied interaction surface, thus following an anti-preferential attachment rule, (2) as a network grows, highly connected sub-networks emerge into protein modules or complexes, and (3) once a new protein is committed to a module, further connections tend to be localized within that module. The CG model produces PPI networks consistent in both topology and age distributions with real PPI networks and is well supported by the spatial arrangement of protein complexes of known 3-D structure, suggesting a plausible physical mechanism for network evolution.     

Stabilizing patterning in the Drosophila segment polarity network by selecting models in silico

The segmentation of Drosophila is a prime model to study spatial patterning during embryogenesis. The spatial expression of segment polarity genes results from a complex network of interacting proteins whose expression products are maintained after successful segmentation. This prompted us to investigate the stability and robustness of this process using a dynamical model for the segmentation network based on Boolean states. The model consists of intra-cellular as well as inter-cellular interactions between adjacent cells in one spatial dimension. We quantify the robustness of the dynamical segmentation process by a systematic analysis of mutations. Our starting point consists in a previous Boolean model for Drosophila segmentation. We define mathematically the notion of dynamical robustness and show that the proposed model exhibits limited robustness in gene expression under perturbations. We applied in silico evolution (mutation and selection) and discover two classes of modified gene networks that have a more robust spatial expression pattern. We verified that the enhanced robustness of the two new models is maintained in differential equations models. By comparing the predicted model with experiments on mutated flies, we then discuss the two types of enhanced models. Drosophila patterning can be explained by modelling the underlying network of interacting genes. Here we demonstrate that simple dynamical considerations and in silico evolution can enhance the model to robustly express the expected pattern, helping to elucidate the role of further interactions.     

Nested Canalyzing Depth and Network Stability

We introduce the nested canalyzing depth of a function, which measures the extent to which it retains a nested canalyzing structure. We characterize the structure of functions with a given depth and compute the expected activities and sensitivities of the variables. This analysis quantifies how canalyzation leads to higher stability in Boolean networks. It generalizes the notion of nested canalyzing functions (NCFs), which are precisely the functions with maximum depth. NCFs have been proposed as gene regulatory network models, but their structure is frequently too restrictive and they are extremely sparse. We find that functions become decreasingly sensitive to input perturbations as the canalyzing depth increases, but exhibit rapidly diminishing returns in stability. Additionally, we show that as depth increases, the dynamics of networks using these functions quickly approach the critical regime, suggesting that real networks exhibit some degree of canalyzing depth, and that NCFs are not significantly better than functions of sufficient depth for many applications of the modeling and reverse engineering of biological networks.     

Numerical bifurcation analysis of distance-dependent on-center off-surround shunting neural networks

 On-center off-surround shunting neural networks are often applied as models for content-addressable memory (CAM), the equilibria being the stored memories. One important demand of biological plausible CAMs is that they function under a broad range of parameters, since several parameters vary due to postnatal maturation or learning. Ellias, Cohen and Grossberg have put much effort into showing the stability properties of several configurations of on-center off-surround shunting neural networks. In this article we present numerical bifurcation analysis of distance-dependent on-center off-surround shunting neural networks with fixed external input. We varied four parameters that may be subject to postnatal maturation: the range of both excitatory and inhibitory connections and the strength of both inhibitory and excitatory connections. These analyses show that fold bifurcations occur in the equilibrium behavior of the network by variation of all four parameters. The most important result is that the number of activation peaks in the equilibrium behavior varies from one to many if the range of inhibitory connections is decreased. Moreover, under a broad range of the parameters the stability of the network is maintained. The examined network is implemented in an ART network, Exact ART, where it functions as the classification layer F2. The stability of the ART network with the F2-field in different dynamic regimes is maintained and the behavior is functional in Exact ART. Through a bifurcation the learning behavior of Exact ART may even change from forming local representations to forming distributed representations. Received: 23 January 1996 / Accepted in revised form: 1 July 1996