On the dynamics of random Boolean networks subject to noise: Attractors, ergodic sets and cell types

The asymptotic dynamics of random Boolean networks subject to random fluctuations is investigated. Under the influence of noise, the system can escape from the attractors of the deterministic model, and a thorough study of these transitions is presented. We show that the dynamics is more properly described by sets of attractors rather than single ones. We generalize here a previous notion of ergodic sets, and we show that the Threshold Ergodic Sets so defined are robust with respect to noise and, at the same time, that they do not suffer from a major drawback of ergodic sets. The system jumps from one attractor to another of the same Threshold Ergodic Set under the influence of noise, never leaving it. By interpreting random Boolean networks as models of genetic regulatory networks, we also propose to associate cell types to Threshold Ergodic Sets rather than to deterministic attractors or to ergodic sets, as it had been previously suggested. We also propose to associate cell differentiation to the process whereby a Threshold Ergodic Set composed by several attractors gives rise to another one composed by a smaller number of attractors. We show that this approach accounts for several interesting experimental facts about cell differentiation, including the possibility to obtain an induced pluripotent stem cell from a fully differentiated one by overexpressing some of its genes.     

Deconstruction and Dynamical Robustness of Regulatory Networks: Application to the Yeast Cell Cycle Networks

Analyzing all the deterministic dynamics of a Boolean regulatory network is a difficult problem since it grows exponentially with the number of nodes. In this paper, we present mathematical and computational tools for analyzing the complete deterministic dynamics of Boolean regulatory networks. For this, the notion of alliance is introduced, which is a subconfiguration of states that remains fixed regardless of the values of the other nodes. Also, equivalent classes are considered, which are sets of updating schedules which have the same dynamics. Using these techniques, we analyze two yeast cell cycle models. Results show the effectiveness of the proposed tools for analyzing update robustness as well as the discovery of new information related to the attractors of the yeast cell cycle models considering all the possible deterministic dynamics, which previously have only been studied considering the parallel updating scheme.     

An efficient algorithm for identifying primary phenotype attractors of a large-scale Boolean network

Background

Boolean network modeling has been widely used to model large-scale biomolecular regulatory networks as it can describe the essential dynamical characteristics of complicated networks in a relatively simple way. When we analyze such Boolean network models, we often need to find out attractor states to investigate the converging state features that represent particular cell phenotypes. This is, however, very difficult (often impossible) for a large network due to computational complexity.

Results

There have been some attempts to resolve this problem by partitioning the original network into smaller subnetworks and reconstructing the attractor states by integrating the local attractors obtained from each subnetwork. But, in many cases, the partitioned subnetworks are still too large and such an approach is no longer useful. So, we have investigated the fundamental reason underlying this problem and proposed a novel efficient way of hierarchically partitioning a given large network into smaller subnetworks by focusing on some attractors corresponding to a particular phenotype of interest instead of considering all attractors at the same time. Using the definition of attractors, we can have a simplified update rule with fixed state values for some nodes. The resulting subnetworks were small enough to find out the corresponding local attractors which can be integrated for reconstruction of the global attractor states of the original large network.

Conclusions

The proposed approach can substantially extend the current limit of Boolean network modeling for converging state analysis of biological networks.

     

Robustness and information propagation in attractors of random boolean networks

Attractors represent the long-term behaviors of Random Boolean Networks. We study how the amount of information propagated between the nodes when on an attractor, as quantified by the average pairwise mutual information ([Formula: see text]), relates to the robustness of the attractor to perturbations ([Formula: see text]). We find that the dynamical regime of the network affects the relationship between [Formula: see text] and [Formula: see text]. In the ordered and chaotic regimes, [Formula: see text] is anti-correlated with [Formula: see text], implying that attractors that are highly robust to perturbations have necessarily limited information propagation. Between order and chaos (for so-called "critical" networks) these quantities are uncorrelated. Finite size effects cause this behavior to be visible for a range of networks, from having a sensitivity of 1 to the point where [Formula: see text] is maximized. In this region, the two quantities are weakly correlated and attractors can be almost arbitrarily robust to perturbations without restricting the propagation of information in the network.     

Stochastic physics,complex systems and biology

In complex systems, the interplay between nonlinear and stochastic dynamics, e.g., J. Monod’s necessity and chance, gives rise to an evolutionary process in Darwinian sense, in terms of discrete jumps among attractors, with punctuated equilibria, spontaneous random “mutations” and “adaptations”. On an evolutionary time scale it produces sustainable diversity among individuals in a homogeneous population rather than convergence as usually predicted by a deterministic dynamics. The emergent discrete states in such a system, i.e., attractors, have natural robustness against both internal and external perturbations. Phenotypic states of a biological cell, a mesoscopic nonlinear stochastic open biochemical system, could be understood through such a perspective.     

Robustness and Evolvability of the Human Signaling Network

Biological systems are known to be both robust and evolvable to internal and external perturbations, but what causes these apparently contradictory properties? We used Boolean network modeling and attractor landscape analysis to investigate the evolvability and robustness of the human signaling network. Our results show that the human signaling network can be divided into an evolvable core where perturbations change the attractor landscape in state space, and a robust neighbor where perturbations have no effect on the attractor landscape. Using chemical inhibition and overexpression of nodes, we validated that perturbations affect the evolvable core more strongly than the robust neighbor. We also found that the evolvable core has a distinct network structure, which is enriched in feedback loops, and features a higher degree of scale-freeness and longer path lengths connecting the nodes. In addition, the genes with high evolvability scores are associated with evolvability-related properties such as rapid evolvability, low species broadness, and immunity whereas the genes with high robustness scores are associated with robustness-related properties such as slow evolvability, high species broadness, and oncogenes. Intriguingly, US Food and Drug Administration-approved drug targets have high evolvability scores whereas experimental drug targets have high robustness scores.     

Diversity of temporal correlations between genes in models of noisy and noiseless gene networks

Gene regulatory networks (GRNs) are parallel information processing systems, binding past events to future actions. Since cell types stably remain in restricted subsets of the possible states of the GRN, they are likely the dynamical attractors of the GRN. These attractors differ in which genes are active and in the amount of information propagating within the network. Using mutual information (I) as a measure of information propagation between genes in a GRN, modeled as finite-sized Random Boolean Networks (RBN), we study how the dynamical regime of the GRN affects I within attractors (I(A)). The spectra of I(A) of individual RBNs are found to be scattered and diverse, and distributions of I(A) of ensembles are non-trivial and change shape with mean connectivity. Mean and diversity of I(A) values maximize in the chaotic near-critical regime, whereas ordered near-critical networks are the best at retaining the distinctiveness of each attractor's I(A) with noise. The results suggest that selection likely favors near-critical GRNs as these both maximize mean and diversity of I(A), and are the most robust to noise. We find similar I(A) distributions in delayed stochastic models of GRNs. For a particular stochastic GRN, we show that both mean and variance of I(A) have local maxima as its connectivity and noise levels are varied, suggesting that the conclusions for the Boolean network models may be generalizable to more realistic models of GRNs.     

A framework to find the logic backbone of a biological network

Background

Cellular behaviors are governed by interaction networks among biomolecules, for example gene regulatory and signal transduction networks. An often used dynamic modeling framework for these networks, Boolean modeling, can obtain their attractors (which correspond to cell types and behaviors) and their trajectories from an initial state (e.g. a resting state) to the attractors, for example in response to an external signal. The existing methods however do not elucidate the causal relationships between distant nodes in the network.

Results

In this work, we propose a simple logic framework, based on categorizing causal relationships as sufficient or necessary, as a complement to Boolean networks. We identify and explore the properties of complex subnetworks that are distillable into a single logic relationship. We also identify cyclic subnetworks that ensure the stabilization of the state of participating nodes regardless of the rest of the network. We identify the logic backbone of biomolecular networks, consisting of external signals, self-sustaining cyclic subnetworks (stable motifs), and output nodes. Furthermore, we use the logic framework to identify crucial nodes whose override can drive the system from one steady state to another. We apply these techniques to two biological networks: the epithelial-to-mesenchymal transition network corresponding to a developmental process exploited in tumor invasion, and the network of abscisic acid induced stomatal closure in plants. We find interesting subnetworks with logical implications in these networks. Using these subgraphs and motifs, we efficiently reduce both networks to succinct backbone structures.

Conclusions

The logic representation identifies the causal relationships between distant nodes and subnetworks. This knowledge can form the basis of network control or used in the reverse engineering of networks.

     

Algorithms and Complexity Analyses for Control of Singleton Attractors in Boolean Networks

A Boolean network (BN) is a mathematical model of genetic networks. We propose several algorithms for control of singleton attractors in BN. We theoretically estimate the average-case time complexities of the proposed algorithms, and confirm them by computer experiments. The results suggest the importance of gene ordering. Especially, setting internal nodes ahead yields shorter computational time than setting external nodes ahead in various types of algorithms. We also present a heuristic algorithm which does not look for the optimal solution but for the solution whose computational time is shorter than that of the exact algorithms.     

Intrinsic properties of Boolean dynamics in complex networks

We study intrinsic properties of attractor in Boolean dynamics of complex networks with scale-free topology, comparing with those of the so-called Kauffman's random Boolean networks. We numerically study both frozen and relevant nodes in each attractor in the dynamics of relatively small networks (20?N?200). We investigate numerically robustness of an attractor to a perturbation. An attractor with cycle length of ?_c in a network of size N consists of ?_c states in the state space of 2^N states; each attractor has the arrangement of N nodes, where the cycle of attractor sweeps ?_c states. We define a perturbation as a flip of the state on a single node in the attractor state at a given time step. We show that the rate between unfrozen and relevant nodes in the dynamics of a complex network with scale-free topology is larger than that in Kauffman's random Boolean network model. Furthermore, we find that in a complex scale-free network with fluctuation of the in-degree number, attractors are more sensitive to a state flip for a highly connected node (i.e. input-hub node) than to that for a less connected node. By some numerical examples, we show that the number of relevant nodes increases, when an input-hub node is coincident with and/or connected with an output-hub node (i.e. a node with large output-degree) one another.     

Boolean dynamics of biological networks with multiple coupled feedback loops

Boolean networks have been frequently used to study the dynamics of biological networks. In particular, there have been various studies showing that the network connectivity and the update rule of logical functions affect the dynamics of Boolean networks. There has been, however, relatively little attention paid to the dynamical role of a feedback loop, which is a circular chain of interactions between Boolean variables. We note that such feedback loops are ubiquitously found in various biological systems as multiple coupled structures and they are often the primary cause of complex dynamics. In this article, we investigate the relationship between the multiple coupled feedback loops and the dynamics of Boolean networks. We show that networks have a larger proportion of basins corresponding to fixed-point attractors as they have more coupled positive feedback loops, and a larger proportion of basins for limit-cycle attractors as they have more coupled negative feedback loops.     

Ergodic Sets as Cell Phenotype of Budding Yeast Cell Cycle

It has been suggested that irreducible sets of states in Probabilistic Boolean Networks correspond to cellular phenotype. In this study, we identify such sets of states for each phase of the budding yeast cell cycle. We find that these “ergodic sets” underly the cyclin activity levels during each phase of the cell cycle. Our results compare to the observations made in several laboratory experiments as well as the results of differential equation models. Dynamical studies of this model: (i) indicate that under stochastic external signals the continuous oscillating waves of cyclin activity and the opposing waves of CKIs emerge from the logic of a Boolean-based regulatory network without the need for specific biochemical/kinetic parameters; (ii) suggest that the yeast cell cycle network is robust to the varying behavior of cell size (e.g., cell division under nitrogen deprived conditions); (iii) suggest the irreversibility of the Start signal is a function of logic of the G1 regulon, and changing the structure of the regulatory network can render start reversible.     

Floral morphogenesis: stochastic explorations of a gene network epigenetic landscape

In contrast to the classical view of development as a preprogrammed and deterministic process, recent studies have demonstrated that stochastic perturbations of highly non-linear systems may underlie the emergence and stability of biological patterns. Herein, we address the question of whether noise contributes to the generation of the stereotypical temporal pattern in gene expression during flower development. We modeled the regulatory network of organ identity genes in the Arabidopsis thaliana flower as a stochastic system. This network has previously been shown to converge to ten fixed-point attractors, each with gene expression arrays that characterize inflorescence cells and primordial cells of sepals, petals, stamens, and carpels. The network used is binary, and the logical rules that govern its dynamics are grounded in experimental evidence. We introduced different levels of uncertainty in the updating rules of the network. Interestingly, for a level of noise of around 0.5-10%, the system exhibited a sequence of transitions among attractors that mimics the sequence of gene activation configurations observed in real flowers. We also implemented the gene regulatory network as a continuous system using the Glass model of differential equations, that can be considered as a first approximation of kinetic-reaction equations, but which are not necessarily equivalent to the Boolean model. Interestingly, the Glass dynamics recover a temporal sequence of attractors, that is qualitatively similar, although not identical, to that obtained using the Boolean model. Thus, time ordering in the emergence of cell-fate patterns is not an artifact of synchronous updating in the Boolean model. Therefore, our model provides a novel explanation for the emergence and robustness of the ubiquitous temporal pattern of floral organ specification. It also constitutes a new approach to understanding morphogenesis, providing predictions on the population dynamics of cells with different genetic configurations during development.     

From Genes to Flower Patterns and Evolution: Dynamic Models of Gene Regulatory Networks

Genes and proteins form complex dynamical systems or gene regulatory networks (GRN) that can reach several steady states (attractors). These may be associated with distinct cell types. In plants, the ABC combinatorial model establishes the necessary gene combinations for floral organ cell specification. We have developed dynamic gene regulatory network (GRN) models to understand how the combinatorial selection of gene activity is established during floral organ primordia specification as a result of the concerted action of ABC and non-ABC genes. Our analyses have shown that the floral organ specification GRN reaches six attractors with gene configurations observed in primordial cell types during early stages of flower development and four that correspond to regions of the inflorescence meristem. This suggests that it is the overall GRN dynamics rather than precise signals that underlie the ABC model. Furthermore, our analyses suggest that the steady states of the GRN are robust to random alterations of the logical functions that define the gene interactions. Here we have updated the GRN model and have systematically altered the outputs of all the logical functions and addressed in which cases the original attractors are recovered. We then reduced the original three-state GRN to a two-state (Boolean) GRN and performed the same systematic perturbation analysis. Interestingly, the Boolean GRN reaches the same number and type of attractors as reached by the three-state GRN, and it responds to perturbations in a qualitatively identical manner as the original GRN. These results suggest that a Boolean model is sufficient to capture the dynamical features of the floral network and provide additional support for the robustness of the floral GRN. These findings further support that the GRN model provides a dynamical explanation for the ABC model and that the floral GRN robustness could be behind the widespread conservation of the floral plan among eudicotyledoneous plants. Other aspects of evolution of flower organ arrangement and ABC gene expression patterns are discussed in the context of the approach proposed here. álvaro Chaos, Max Aldana and Elena Alvarez-Buylla contributed equally to this work.     

Logical and symbolic analysis of robust biological dynamics

Logical models provide insight about key control elements of biological networks. Based solely on the logical structure, we can determine state transition diagrams that give the allowed possible transitions in a coarse grained phase space. Attracting pathways and stable nodes in the state transition diagram correspond to robust attractors that would be found in several different types of dynamical systems that have the same logical structure. Attracting nodes in the state transition diagram correspond to stable steady states. Furthermore, the sequence of logical states appearing in biological networks with robust attracting pathways would be expected to appear also in Boolean networks, asynchronous switching networks, and differential equations having the same underlying structure. This provides a basis for investigating naturally occurring and synthetic systems, both to predict the dynamics if the structure is known, and to determine the structure if the transitions are known.     

An Efficient Algorithm for Computing Attractors of Synchronous And Asynchronous Boolean Networks

Biological networks, such as genetic regulatory networks, often contain positive and negative feedback loops that settle down to dynamically stable patterns. Identifying these patterns, the so-called attractors, can provide important insights for biologists to understand the molecular mechanisms underlying many coordinated cellular processes such as cellular division, differentiation, and homeostasis. Both synchronous and asynchronous Boolean networks have been used to simulate genetic regulatory networks and identify their attractors. The common methods of computing attractors are that start with a randomly selected initial state and finish with exhaustive search of the state space of a network. However, the time complexity of these methods grows exponentially with respect to the number and length of attractors. Here, we build two algorithms to achieve the computation of attractors in synchronous and asynchronous Boolean networks. For the synchronous scenario, combing with iterative methods and reduced order binary decision diagrams (ROBDD), we propose an improved algorithm to compute attractors. For another algorithm, the attractors of synchronous Boolean networks are utilized in asynchronous Boolean translation functions to derive attractors of asynchronous scenario. The proposed algorithms are implemented in a procedure called geneFAtt. Compared to existing tools such as genYsis, geneFAtt is significantly faster in computing attractors for empirical experimental systems.

Availability

The software package is available at https://sites.google.com/site/desheng619/download.     

Detecting controlling nodes of boolean regulatory networks

Boolean models of regulatory networks are assumed to be tolerant to perturbations. That qualitatively implies that each function can only depend on a few nodes. Biologically motivated constraints further show that functions found in Boolean regulatory networks belong to certain classes of functions, for example, the unate functions. It turns out that these classes have specific properties in the Fourier domain. That motivates us to study the problem of detecting controlling nodes in classes of Boolean networks using spectral techniques. We consider networks with unbalanced functions and functions of an average sensitivity less than ?k, where k is the number of controlling variables for a function. Further, we consider the class of 1-low networks which include unate networks, linear threshold networks, and networks with nested canalyzing functions. We show that the application of spectral learning algorithms leads to both better time and sample complexity for the detection of controlling nodes compared with algorithms based on exhaustive search. For a particular algorithm, we state analytical upper bounds on the number of samples needed to find the controlling nodes of the Boolean functions. Further, improved algorithms for detecting controlling nodes in large-scale unate networks are given and numerically studied.     

Multiple states in river and lake ecosystems

Nonlinear models of ecosystem dynamics that incorporate positive feedbacks and multiple, internally reinforced states have considerable explanatory power. However, linear models may be adequate, particularly if ecosystem behaviour is primarily controlled by external processes. In lake ecosystems, internal (mainly biotic) processes are thought to have major impacts on system behaviour, whereas in rivers, external (mainly physical) factors have traditionally been emphasized. We consider the hypothesis that models that exhibit multiple states are useful for understanding the behaviour of lake ecosystems, but not as useful for understanding stream ecosystems. Some of the best-known examples of multiple states come from lake ecosystems. We review some of these examples, and we also describe examples of multiple states in rivers. We conclude that the hypothesis is an oversimplification; the importance of physical forcing in rivers does not eliminate the possibility of internal feedbacks that create multiple states, although in rivers these feedbacks are likely to include physical as well as biotic processes. Nonlinear behaviour in aquatic ecosystems may be more common than current theory indicates.     

Attractor analysis of asynchronous Boolean models of signal transduction networks

Prior work on the dynamics of Boolean networks, including analysis of the state space attractors and the basin of attraction of each attractor, has mainly focused on synchronous update of the nodes’ states. Although the simplicity of synchronous updating makes it very attractive, it fails to take into account the variety of time scales associated with different types of biological processes. Several different asynchronous update methods have been proposed to overcome this limitation, but there have not been any systematic comparisons of the dynamic behaviors displayed by the same system under different update methods. Here we fill this gap by combining theoretical analysis such as solution of scalar equations and Markov chain techniques, as well as numerical simulations to carry out a thorough comparative study on the dynamic behavior of a previously proposed Boolean model of a signal transduction network in plants. Prior evidence suggests that this network admits oscillations, but it is not known whether these oscillations are sustained. We perform an attractor analysis of this system using synchronous and three different asynchronous updating schemes both in the case of the unperturbed (wild-type) and perturbed (node-disrupted) systems. This analysis reveals that while the wild-type system possesses an update-independent fixed point, any oscillations eventually disappear unless strict constraints regarding the timing of certain processes and the initial state of the system are satisfied. Interestingly, in the case of disruption of a particular node all models lead to an extended attractor. Overall, our work provides a roadmap on how Boolean network modeling can be used as a predictive tool to uncover the dynamic patterns of a biological system under various internal and environmental perturbations.     

Deterministic characterization of phase noise in biomolecular oscillators

On top of the many external perturbations, cellular oscillators also face intrinsic perturbations due the randomness of chemical kinetics. Biomolecular oscillators, distinct in their parameter sets or distinct in their architecture, show different resilience with respect to such intrinsic perturbations. Assessing this resilience can be done by ensemble stochastic simulations. These are computationally costly and do not permit further insights into the mechanistic cause of the observed resilience. For reaction systems operating at a steady state, the linear noise approximation (LNA) can be used to determine the effect of molecular noise. Here we show that methods based on LNA fail for oscillatory systems and we propose an alternative ansatz. It yields an asymptotic expression for the phase diffusion coefficient of stochastic oscillators. Moreover, it allows us to single out the noise contribution of every reaction in an oscillatory system. We test the approach on the one-loop model of the Drosophila circadian clock. Our results are consistent with those obtained through stochastic simulations with a gain in computational efficiency of about three orders of magnitude.