Stability of functions in Boolean models of gene regulatory networks

Boolean networks are used to model large nonlinear systems such as gene regulatory networks. We will present results that can be used to understand how the choice of functions affects the network dynamics. The so called bias-map and its fixed points depict much of the function's dynamical role in the network. We define the concept of stabilizing functions and show that many Post and canalizing functions are also stabilizing functions. Boolean networks constructed using the same type of stabilizing functions are always stable regardless of the average in-degree of network functions. We derive the number of all stabilizing functions and find it to be much larger than the number of Post and canalizing functions. We also discuss the implementation of functions and apply the presented results to biological data that give an approximation of the distribution of regulatory functions in eucaryotic cells. We find that the obtained theoretical results on the number of active genes are biologically plausible. Finally, based on the presented results, we discuss why canalizing and Post regulatory functions seem to be common in cells.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

Using the Renormalization Group to Classify Boolean Functions

This paper argues that the renormalization group technique used to characterize phase transitions in condensed matter systems can be used to classify Boolean functions. A renormalization group transformation is presented that maps an arbitrary Boolean function of N Boolean variables to one of N−1 variables. Applying this transformation to a generic Boolean function (one whose output for each input is chosen randomly and independently to be one or zero with equal probability) yields another generic Boolean function. Moreover, applying the transformation to some other functions known to be non-generic, such as Boolean functions that can be written as polynomials of degree ξ with ξ ≪ N and functions that depend on composite variables such as the arithmetic sum of the inputs, yields non-generic results. One can thus define different phases of Boolean functions as classes of functions with different types of behavior upon repeated application of the renormalization transformation. Possible relationships between different phases of Boolean functions and computational complexity classes studied in computer science are discussed.     

Boolean game on scale-free networks

Inspired by the local minority game, we propose a network Boolean game and investigate its dynamical properties on scale-free networks. The system can self-organize to a stable state with better performance than the random choice game, although only the local information is available to each agent. By introducing the heterogeneity of local interactions, we find that the system will achieve the best performance when each agent's interaction frequency is linearly correlated with its information capacity. Generally, the agents with more information gain more than those with less information, while in the optimal case, each agent almost has the same average profit. In addition, we investigate the role of irrational factor and find an interesting symmetrical behavior.     

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.     

Superpolynomial growth in the number of attractors in Kauffman networks

The Kauffman model describes a particularly simple class of random Boolean networks. Despite the simplicity of the model, it exhibits complex behavior and has been suggested as a model for real world network problems. We introduce a novel approach to analyzing attractors in random Boolean networks, and applying it to Kauffman networks we prove that the average number of attractors grows faster than any power law with system size.     

Control of random Boolean networks via average sensitivity of Boolean functions

In this paper,we discuss how to transform the disordered phase into an ordered phase in random Boolean networks.To increase the effectiveness,a control scheme is proposed,which periodically freezes a fraction of the network based on the average sensitivity of Boolean functions of the nodes.Theoretical analysis is carried out to estimate the expected critical value of the fraction,and shows that the critical value is reduced using this scheme compared to that of randomly freezing a fraction of the nodes.Finally,the simulation is given for illustrating the effectiveness of the proposed method.     

Symbolic synchronization and the detection of global properties of coupled dynamics from local information

We study coupled dynamics on networks using symbolic dynamics. The symbolic dynamics is defined by dividing the state space into a small number of regions (typically 2), and considering the relative frequencies of the transitions between those regions. It turns out that the global qualitative properties of the coupled dynamics can be classified into three different phases based on the synchronization of the variables and the homogeneity of the symbolic dynamics. Of particular interest is the homogeneous unsynchronized phase, where the coupled dynamics is in a chaotic unsynchronized state, but exhibits qualitative similar symbolic dynamics at all the nodes in the network. We refer to this dynamical behavior as symbolic synchronization. In this phase, the local symbolic dynamics of any arbitrarily selected node reflects global properties of the coupled dynamics, such as qualitative behavior of the largest Lyapunov exponent and phase synchronization. This phase depends mainly on the network architecture, and only to a smaller extent on the local chaotic dynamical function. We present results for two model dynamics, iterations of the one-dimensional logistic map and the two-dimensional Henon map, as local dynamical function.     

Constructing backbone network by using tinker algorithm

Revealing how a biological network is organized to realize its function is one of the main topics in systems biology. The functional backbone network, defined as the primary structure of the biological network, is of great importance in maintaining the main function of the biological network. We propose a new algorithm, the tinker algorithm, to determine this core structure and apply it in the cell-cycle system. With this algorithm, the backbone network of the cell-cycle network can be determined accurately and efficiently in various models such as the Boolean model, stochastic model, and ordinary differential equation model. Results show that our algorithm is more efficient than that used in the previous research. We hope this method can be put into practical use in relevant future studies.     

Node importance for dynamical process on networks: a multiscale characterization

Defining the importance of nodes in a complex network has been a fundamental problem in analyzing the structural organization of a network, as well as the dynamical processes on it. Traditionally, the measures of node importance usually depend either on the local neighborhood or global properties of a network. Many real-world networks, however, demonstrate finely detailed structure at various organization levels, such as hierarchy and modularity. In this paper, we propose a multiscale node-importance measure that can characterize the importance of the nodes at varying topological scale. This is achieved by introducing a kernel function whose bandwidth dictates the ranges of interaction, and meanwhile, by taking into account the interactions from all the paths a node is involved. We demonstrate that the scale here is closely related to the physical parameters of the dynamical processes on networks, and that our node-importance measure can characterize more precisely the node influence under different physical parameters of the dynamical process. We use epidemic spreading on networks as an example to show that our multiscale node-importance measure is more effective than other measures.     

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.     

Topological Field Theory and Computing with Instantons

It is well known that dynamical systems may be employed as computing machines. However, not all dynamical systems offer particular advantages compared to the standard paradigm of computation, in regard to efficiency and scalability. Recently, it was suggested that a new type of machines, named digital –hence scalable– memcomputing machines (DMMs), that employ non‐linear dynamical systems with memory, can solve complex Boolean problems efficiently. This result was derived using functional analysis without, however, providing a clear understanding of which physical features make DMMs such an efficient computational tool. Here, we show, using recently proposed topological field theory of dynamical systems, that the solution search by DMMs is a composite instanton. This process effectively breaks the topological supersymmetry common to all dynamical systems, including DMMs. The emergent long‐range order – a collective dynamical behavior– allows logic gates of the machines to correlate arbitrarily far away from each other, despite their non‐quantum character. We exemplify these results with the solution of prime factorization, but the conclusions generalize to DMMs applied to any other Boolean problem.     

Basin entropy in Boolean network ensembles

The information processing capacity of a complex dynamical system is reflected in the partitioning of its state space into disjoint basins of attraction, with state trajectories in each basin flowing towards their corresponding attractor. We introduce a novel network parameter, the basin entropy, as a measure of the complexity of information that such a system is capable of storing. By studying ensembles of random Boolean networks, we find that the basin entropy scales with system size only in critical regimes, suggesting that the informationally optimal partition of the state space is achieved when the system is operating at the critical boundary between the ordered and disordered phases.     

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.