Evolution of canalizing Boolean networks

Boolean networks with canalizing functions are used to model gene regulatory networks. In order to learn how such networks may behave under evolutionary forces, we simulate the evolution of a single Boolean network by means of an adaptive walk, which allows us to explore the fitness landscape. Mutations change the connections and the functions of the nodes. Our fitness criterion is the robustness of the dynamical attractors against small perturbations. We find that with this fitness criterion the global maximum is always reached and that there is a huge neutral space of 100% fitness. Furthermore, in spite of having such a high degree of robustness, the evolved networks still share many features with “chaotic” networks.     

Activities and sensitivities in boolean network models

We study how the notions of importance of variables in Boolean functions as well as the sensitivities of the functions to changes in these variables impact the dynamical behavior of Boolean networks. The activity of a variable captures its influence on the output of the function and is a measure of that variable's importance. The average sensitivity of a Boolean function captures the smoothness of the function and is related to its internal homogeneity. In a random Boolean network, we show that the expected average sensitivity determines the well-known critical transition curve. We also discuss canalizing functions and the fact that the canalizing variables enjoy higher importance, as measured by their activities, than the noncanalizing variables. Finally, we demonstrate the important role of the average sensitivity in determining the dynamical behavior of a Boolean network.     

The phase diagram of random Boolean networks with nested canalizing functions

We obtain the phase diagram of random Boolean networks with nested canalizing functions. Using the annealed approximation, we obtain the evolution of the number b _t of nodes with value one, and the network sensitivity λ, and compare with numerical simulations of quenched networks. We find that, contrary to what was reported by Kauffman et al. [Proc. Natl. Acad. Sci. 101, 17102 (2004)], these networks have a rich phase diagram, were both the “chaotic" and frozen phases are present, as well as an oscillatory regime of the value of b _t . We argue that the presence of only the frozen phase in the work of Kauffman et al. was due simply to the specific parametrization used, and is not an inherent feature of this class of functions. However, these networks are significantly more stable than the variant where all possible Boolean functions are allowed.     

Order or chaos in Boolean gene networks depends on the mean fraction of canalizing functions

We explore the connection between order/chaos in Boolean networks and the naturally occurring fraction of canalizing functions in such systems. This fraction turns out to give a very clear indication of whether the system possesses ordered or chaotic dynamics, as measured by Derrida plots, and also the degree of order when we compare different networks with the same number of vertices and edges. By studying also a wide distribution of indegrees in a network, we show that the mean probability of canalizing functions is a more reliable indicator of the type of dynamics for a finite network than the classical result on stability relating the bias to the mean indegree. Finally, we compare by direct simulations two biologically derived networks with networks of similar sizes but with power-law and Poisson distributions of indegrees, respectively. The biologically motivated networks are not more ordered than the latter, and in one case the biological network is even chaotic while the others are not.     

Boolean networks with variable number of inputs (K)

We studied a random Boolean network model with a variable number of inputs K per element. An interesting feature of this model, compared to the well-known fixed-K networks, is its higher orderliness. It seems that the distribution of connectivity alone contributes to a certain amount of order. In the present research, we tried to disentangle some of the reasons for this unexpected order. We also studied the influence of different numbers of source elements (elements with no inputs) on the network's dynamics. An analysis carried out on the networks with an average value of K=2 revealed a correlation between the number of source elements and the dynamic diversity of the network. As a diversity measure we used the number of attractors, their lengths and similarity. As a quantitative measure of the attractors' similarity, we developed two methods, one taking into account the size and the overlapping of the frozen areas, and the other in which active elements are also taken into account. As the number of source elements increases, the dynamic diversity of the networks does likewise: the number of attractors increases exponentially, while their similarity diminishes linearly. The length of attractors remains approximately the same, which indicates that the orderliness of the networks remains the same. We also determined the level of order that originates from the canalizing properties of Boolean functions and the propagation of this influence through the network. This source of order can account only for one-half of the frozen elements; the other half presumably freezes due to the complex dynamics of the network. Our work also demonstrates that different ways of assigning and redirecting connections between elements may influence the results significantly. Studying such systems can also help with modeling and understanding a complex organization and self-ordering in biological systems, especially the genetic ones.     

Canalizing Kauffman networks: nonergodicity and its effect on their critical behavior

Boolean networks have been used to study numerous phenomena, including gene regulation, neural networks, social interactions, and biological evolution. Here, we propose a general method for determining the critical behavior of Boolean systems built from arbitrary ensembles of Boolean functions. In particular, we solve the critical condition for systems of units operating according to canalizing functions and present strong numerical evidence that our approach correctly predicts the phase transition from order to chaos in such systems.     

Statistical evidence of strain induced breaking of metallic point contacts

As a paradigm for modeling gene regulatory networks, probabilistic Boolean networks (PBNs) form a subclass of Markov genetic regulatory networks. To date, many different stochastic optimal control approaches have been developed to find therapeutic intervention strategies for PBNs. A PBN is essentially a collection of constituent Boolean networks via a probability structure. Most of the existing works assume that the probability structure for Boolean networks selection is known. Such an assumption cannot be satisfied in practice since the presence of noise prevents the probability structure from being accurately determined. In this paper, we treat a case in which we lack the governing probability structure for Boolean network selection. Specifically, in the framework of PBNs, the theory of finite horizon Markov decision process is employed to find optimal constituent Boolean networks with respect to the defined objective functions. In order to illustrate the validity of our proposed approach, an example is also displayed.     

Number and length of attractors in a critical Kauffman model with connectivity one

The Kauffman model describes a system of randomly connected nodes with dynamics based on Boolean update functions. Though it is a simple model, it exhibits very complex behavior for "critical" parameter values at the boundary between a frozen and a disordered phase, and is therefore used for studies of real network problems. We prove here that the mean number and mean length of attractors in critical random Boolean networks with connectivity one both increase faster than any power law with network size. We derive these results by generating the networks through a growth process and by calculating lower bounds.     

Comparing the evolution of canalyzing and threshold networks

We study the influence of the type of update functions on the evolution of Boolean networks under selection for dynamical robustness. The chosen types of functions are canalyzing functions and threshold functions. Starting from a random initial network, we evolve the network by an adaptive walk. During the first time period, where the networks evolve to the plateau of 100 percent fitness, we find that both type of update functions give the same behavior, albeit for different network sizes and connectedness. However, on the long run, as the networks continue to evolve on the fitness plateau, the different types of update functions give rise to different network structure, due to their different mutational robustness. When both types of update functions occur together, none of them is preferred under long-term evolution.     

Response of boolean networks to perturbations

We evaluate the probability that a Boolean network returns to an attractor after perturbing h nodes. We find that the return probability as function of h can display a variety of different behaviours, which yields insights into the state-space structure. In addition to performing computer simulations, we derive analytical results for several types of Boolean networks, in particular for Random Boolean Networks. We also apply our method to networks that have been evolved for robustness to small perturbations, and to a biological example.     

An adjustable aperiodic model class of genomic interactions using continuous time Boolean networks (Boolean delay equations)

Following the complete sequencing of several genomes, interest has grown in the construction of genetic regulatory networks, which attempt to describe how different genes work together in both normal and abnormal cells. This interest has led to significant research in the behavior of abstract network models, with Boolean networks emerging as one particularly popular type. An important limitation of these networks is that their time evolution is necessarily periodic, motivating our interest in alternatives that are capable of a wider range of dynamic behavior. In this paper we examine one such class, that of continuous-time Boolean networks, a special case of the class of Boolean delay equations (BDEs) proposed for climatic and seismological modeling. In particular, we incorporate a biologically motivated refractory period into the dynamic behavior of these networks, which exhibit binary values like traditional Boolean networks, but which, unlike Boolean networks, evolve in continuous time. In this way, we are able to overcome both computational and theoretical limitations of the general class of BDEs while still achieving dynamics that are either aperiodic or effectively so, with periods many orders of magnitude longer than those of even large discrete time Boolean networks.     

Network topological optimization for packet routing using multi-objective simulated annealing method

A new multi-objective simulated annealing (MOSA) algorithm is proposed for optimizing network topology. In this paper, the MOSA algorithm is used to perform two-objective simultaneous optimization. The two objectives examined in this paper are the critical packet generation rate, and average number of overall packet loads. Our results indicate that homogeneous networks can support a large critical packet generation rate under the congestion-free state, but the networks must be able to sustain relatively heavy packet load pressure if the same packet generation rate is assigned to a more heterogeneous network. At the same time, it is also found that heterogeneous networks can relieve packet load pressure, but the network is likely to become congested due to an abrupt increase of packet loads. We find that when the network size is large, lowering the average number of packet loads and raising the critical packet generation rate need not to be compromised too much. We also point out that networks can be more robust to abrupt increase of packet loads if networks are structured more homogeneously in the process of network size increment.     

Core percolation and onset of complexity in boolean networks

The determination and classification of fixed points of large Boolean networks is addressed in terms of a constraint-satisfaction problem. We develop a general simplification scheme that, removing all those variables and functions belonging to trivial logical cascades, returns the computational core of the network. The transition line from an easy to a complex regulatory phase is described as a function of the parameters of the model, identifying thereby both theoretically and algorithmically the relevant regulatory variables.     

Coevolution of information processing and topology in hierarchical adaptive random Boolean networks

Random Boolean Networks (RBNs) are frequently used for modeling complex systems driven by information processing, e.g. for gene regulatory networks (GRNs). Here we propose a hierarchical adaptive random Boolean Network (HARBN) as a system consisting of distinct adaptive RBNs (ARBNs) – subnetworks – connected by a set of permanent interlinks. We investigate mean node information, mean edge information as well as mean node degree. Information measures and internal subnetworks topology of HARBN coevolve and reach steady-states that are specific for a given network structure. The main natural feature of ARBNs, i.e. their adaptability, is preserved in HARBNs and they evolve towards critical configurations which is documented by power law distributions of network attractor lengths. The mean information processed by a single node or a single link increases with the number of interlinks added to the system. The mean length of network attractors and the mean steady-state connectivity possess minima for certain specific values of the quotient between the density of interlinks and the density of all links in networks. It means that the modular network displays extremal values of its observables when subnetworks are connected with a density a few times lower than a mean density of all links.     

Damage spreading and criticality in finite random dynamical networks

We systematically study and compare damage spreading at the sparse percolation (SP) limit for random Boolean and threshold networks with perturbations that are independent of the network size N. This limit is relevant to information and damage propagation in many technological and natural networks. Using finite-size scaling, we identify a new characteristic connectivity Ks, at which the average number of damaged nodes d[over ], after a large number of dynamical updates, is independent of N. Based on marginal damage spreading, we determine the critical connectivity Kc(sparse)(N) for finite N at the SP limit and show that it systematically deviates from Kc, established by the annealed approximation, even for large system sizes. Our findings can potentially explain the results recently obtained for gene regulatory networks and have important implications for the evolution of dynamical networks that solve specific tasks.     

Combinatorial explosion in model gene networks

The explosive growth in knowledge of the genome of humans and other organisms leaves open the question of how the functioning of genes in interacting networks is coordinated for orderly activity. One approach to this problem is to study mathematical properties of abstract network models that capture the logical structures of gene networks. The principal issue is to understand how particular patterns of activity can result from particular network structures, and what types of behavior are possible. We study idealized models in which the logical structure of the network is explicitly represented by Boolean functions that can be represented by directed graphs on n-cubes, but which are continuous in time and described by differential equations, rather than being updated synchronously via a discrete clock. The equations are piecewise linear, which allows significant analysis and facilitates rapid integration along trajectories. We first give a combinatorial solution to the question of how many distinct logical structures exist for n-dimensional networks, showing that the number increases very rapidly with n. We then outline analytic methods that can be used to establish the existence, stability and periods of periodic orbits corresponding to particular cycles on the n-cube. We use these methods to confirm the existence of limit cycles discovered in a sample of a million randomly generated structures of networks of 4 genes. Even with only 4 genes, at least several hundred different patterns of stable periodic behavior are possible, many of them surprisingly complex. We discuss ways of further classifying these periodic behaviors, showing that small mutations (reversal of one or a few edges on the n-cube) need not destroy the stability of a limit cycle. Although these networks are very simple as models of gene networks, their mathematical transparency reveals relationships between structure and behavior, they suggest that the possibilities for orderly dynamics in such networks are extremely rich and they offer novel ways to think about how mutations can alter dynamics. (c) 2000 American Institute of Physics.     

From topology to dynamics in biochemical networks

Abstract formulations of the regulation of gene expression as random Boolean switching networks have been studied extensively over the past three decades. These models have been developed to make statistical predictions of the types of dynamics observed in biological networks based on network topology and interaction bias, p. For values of mean connectivity chosen to correspond to real biological networks, these models predict disordered dynamics. However, chaotic dynamics seems to be absent from the functioning of a normal cell. While these models use a fixed number of inputs for each element in the network, recent experimental evidence suggests that several biological networks have distributions in connectivity. We therefore study randomly constructed Boolean networks with distributions in the number of inputs, K, to each element. We study three distributions: delta function, Poisson, and power law (scale free). We analytically show that the critical value of the interaction bias parameter, p, above which steady state behavior is observed, is independent of the distribution in the limit of the number of elements N--> infinity. We also study these networks numerically. Using three different measures (types of attractors, fraction of elements that are active, and length of period), we show that finite, scale-free networks are more ordered than either the Poisson or delta function networks below the critical point. Thus the topology of scale-free biochemical networks, characterized by a wide distribution in the number of inputs per element, may provide a source of order in living cells. (c) 2001 American Institute of Physics.     

Oscillatory Dynamics and Oscillation Death in Complex Networks Consisting of Both Excitatory and Inhibitory Nodes

In neural networks, both excitatory and inhibitory cells play important roles in determining the functions of systems. Various dynamical networks have been proposed as artificial neural networks to study the properties of biological systems where the influences of excitatory nodes have been extensively investigated while those of inhibitory nodes have been studied much less. In this paper, we consider a model of oscillatory networks of excitable Boolean maps consisting of both excitatory and inhibitory nodes, focusing on the roles of inhibitory nodes. We find that inhibitory nodes in sparse networks (small average connection degree) play decisive roles in weakening oscillations, and oscillation death occurs after continual weakening of oscillation for sufficiently high inhibitory node density. In the sharp contrast, increasing inhibitory nodes in dense networks may result in the increase of oscillation amplitude and sudden oscillation death at much lower inhibitory node density and the nearly highest excitation activities. Mechanism under these peculiar behaviors of dense networks is explained by the competition of the duplex effects of inhibitory nodes.     

Propagation of external regulation and asynchronous dynamics in random Boolean networks

Boolean networks and their dynamics are of great interest as abstract modeling schemes in various disciplines, ranging from biology to computer science. Whereas parallel update schemes have been studied extensively in past years, the level of understanding of asynchronous updates schemes is still very poor. In this paper we study the propagation of external information given by regulatory input variables into a random Boolean network. We compute both analytically and numerically the time evolution and the asymptotic behavior of this propagation of external regulation (PER). In particular, this allows us to identify variables that are completely determined by this external information. All those variables in the network that are not directly fixed by PER form a core which contains, in particular, all nontrivial feedback loops. We design a message-passing approach allowing to characterize the statistical properties of these cores in dependence of the Boolean network and the external condition. At the end we establish a link between PER dynamics and the full random asynchronous dynamics of a Boolean network.