Boolean networks

Next: Generalised logic Up: Logical models Previous: Logical models

Subsections

Boolean networks

One of the earliest approaches to modelling large networks of interacting genes was to view a genetic regulatory system as a network of logical elements [67,68,70].

The Boolean network approach makes a number of assumptions to simplify analysis [119]. First, the activation of a single gene is represented as a Boolean switch that can be either on or off. In effect, a gene can be either expressed or not expressed and there is no possibility of intermediate levels of activation. This assumption is reasonable when a gene spends most of its time either at a floor value of zero or at some positive saturation level and the time required for a gene to switch is negligible with respect to the time scale of the model. The second assumption is that the regulatory control of a gene is described by a combination of Boolean logic rules, such as AND, OR and NOT. The final assumption is that timing is synchronous, that is, the states of all genes are updated simultaneously at each time step.

One of the immediate advantages of these assumptions was that the computational requirements of simulating regulatory systems were massively reduced, allowing the exploration of much larger systems. On the other hand, the validity of the above assumptions, and the value of the Boolean approach in general, has been questioned by a number of people, particularly in the biological community, where there is a perceived lack of connection between simulation results and empirically testable hypotheses [42].

As there was little knowledge of the connectivity patterns in real biological networks, Kauffman used an ensemble approach, generating large numbers of randomly connected networks with randomly chosen Boolean updating functions [69]. His goal was to measure the generic properties of certain classes of networks and observe how their global dynamics resulted from local interactions.

Model description

Kauffman's model of Boolean networks have two primary parameters: network size, N, the number of elements in the network and network connectivity, K, the number of inputs regulating the activity of each element. Each of the N elements is associated with a rule table specifying outputs for each of the 2^K possible input combinations. As each element in the network is updated simultaneously, the system is deterministic and the state at time t + 1 can be determined on the basis of the state at time t (see Figure 6). The rule tables for each element can be defined in a number of different ways [7]: They may be fixed over time (the quenched model), as is usually the case when a single network is being simulated. Alternatively, a new set of rule tables may be generated at each step (the annealled model), which simplifies theoretical analysis of network behaviour.

**Figure 6:** An example of a Boolean network: (a) the wiring diagram; (b) the updating rules; (c) a state transition table, showing how network activation at time t + 1 depends on network activation at time t; and (d) the state space of the network, with two point attractors and a limit cycle with a period of two.
$\begin{figure} \begin{center} \includegraphics[scale=0.5]{figures/rbn} \end{center} \end{figure}$

Theoretical results and hypotheses

Classes of behaviour

The dynamics of a system will fall into three different phases depending on the value of K. There are a number of different metrics for distinguishing between these phases, one of which is information transfer. If two identical systems are initialized with similar, but not identical, starting states, the distance between their subsequent states (measured by a Hamming metric) will change over time. This property reflects the localisation of information transfer. If the Hamming distance stays small, information is communicated across only a local portion of the network. If the Hamming distance increases, it indicates that information is being transferred to a much larger portion of the network.

When K > 2, the Hamming distance grows exponentially with time and the system is in the chaotic or disordered phase. When K < 2, the Hamming distance decays exponentially with time and the system is in the frozen or ordered phase. For K = 2, the Hamming distance remains stable, subject to fluctuations. This phase has been referred to as the critical or complex phase. It is also colloquially known in some contexts as ``the edge of chaos''.

For quenched networks (i.e., those with updating functions fixed over time), a system will eventually return to a previously visited point and the dynamics will form a cycle with a given period. All possible states in a system will either be a part of one of these cycles, or a transient point in a path leading to one of these cycles. Taking language from the field of dynamic systems, a cycle can be referred to as an attractor and the set of all points that lead to a particular cycle as its basin of attraction. A garden of eden state is a particular type of state that has no predecessors. An attractor can either be a fixed point (period equal to 1), or a limit cycle (period greater than 1) (see Figure 6 (d)).

Attractors as cell types

Chaotic systems tend to contain cycles with long periods and long transients. Frozen systems tend to have much shorter cycles and transients. The behaviour of critical systems is intermediate between these. As mentioned in Section 2, different cell types are distinguished primarily on the basis of which of their genes are expressed. Kauffman draws an analogy between an attractor in a Boolean network and a particular cell type or fate. The transient period then corresponds to the process of cell differentiation. In the chaotic regime, these transients would appear to be unrealistically long. Furthermore, systems in the chaotic regime tend to be highly sensitive to perturbations, which does not correspond to the robust behaviour displayed by biological systems. On the other hand, systems in the frozen regime, while displaying acceptably short transient lengths, have virtually zero sensitivity to perturbations, which would appear to preclude any differentiation whatsoever.

Kauffman therefore proposed that life occurs in the vicintiy of the critical regime [70], and argued that the relationship between attractor number and system size in Boolean networks mirrored the observed relationship between cell types and number of genes in various biological organisms [67]. The exact properties of the scaling law between system size and attractor number has been the subject of continued debate [15,17,115]. Regardless, at a qualitative level, systems in the critical regime tend to display both short transient lengths and a small, but significant, level of sensitivity to perturbations. These features are consistent with a biological system in which cell types are relatively stable but have a small possibility of mutating to one of a few ``neighbouring'' cell types. The properties of Boolean network state spaces and the analogy between basins of attraction and cell types have been extensively explored by Wuensche [143,144].

Extensions and applications

Updating rules

A major problem with Kauffman's argument is that the level of connectivity of networks displaying such complex behaviour (K = 2) is much lower than has been observed in real systems (where some genes may be controlled by as many as 20 regulatory factors). Several modifications to the Boolean model have been proposed that address this issue. By default, a random Boolean function has an equal probability of switching a given gene on or off. However, the model can be extended by the addition of a bias term, p, specifying the probability that a certain combination of inputs result in an element being switched off.

The behaviour of a network now depends on both K and p For a fixed K, these three phases can also be reached by altering p, the bias in the rule tables (see Figure 7). As p is changed, the level of connectivity corresponding to the critical phase, K_c is given by:

$\begin{eqnarray} K_c & = & \frac{1}{2p(1-p)} \end{eqnarray}$

**Figure 7:** The phase space of Boolean networks with random (left) and scale-free (right) connectivity.
$\begin{figure} \begin{center} \includegraphics[scale=0.4]{figures/rbn-space} \end{center} \end{figure}$

Kauffman has also proposed that biology may use only a subset of the total possible range of Boolean functions, termed canalizing functions, in which the state of a single input is sufficient to determine at least one of the possible output states [70]. A network using canalizing functions displays more stable behaviour than a non-canalizing network, however, as K increases, the proportion of functions that are canalizing decreases rapidly. It has been argued that canalizing functions are likely to be extremely rare at realistic levels of connectivity [7]. However, reviews of the biological literature have suggested a strong bias towards canalizing functions in regulatory interactions with 3, 4 and 5 inputs [53]. A number of other definitions of Boolean updating functions that produce more stable behaviour have also been proposed [105,96].

Network structure

While the approaches to increasing network stability mentioned so far have focused on modifying the updating rules, or the network dynamics, it has also been suggested that changing network structure may stabilize network behaviour. In particular, if nodes are connected with a scale-free distribution (see Section 7 below), rather than a random distribution, the position of the order/disorder boundary in the state space will be modified, increasing the size of the ordered region [7,43,91] (see Figure 7).

Another approach that has been taken to generating Boolean networks in a non-random fashion is to extract the network structure and updating rules from a lower level of description. In the Artificial Genome model [99], network structure and functions are generated by parsing a string of bases (the artificial genome). This method results in networks with a significantly different degree distribution and a restricted set of updating rules [46].

Timing

Most of the results mentioned so far have relied on the assumption that network updating is carried out synchronously, that is, the activation of every node is updated simultaneously. It has been pointed out that relaxing this assumption and allowing asynchronous updating introduces a level of indeterminism that interferes with many of the interesting phenomena displayed by traditional Boolean networks [55]. Using two different definitions of asynchrony (essentially with and without replacement), Harvey and Bossomaier found that cyclic attractors disappeared, point attractors remained, and a new category of ``loose attractors'' appeared, in which the network passes indefinitely through some subset of its possible states [55]. The nature of basins of attraction also changes, with some being definite basins, from which all paths lead to the attractor, and others being possible basins, form which at least one path leads to the attractor.

This work was followed up by Di Paolo, who defined a measure of ``pseudo-periodicity'' in which an autocorrelation function is used to measure the probability of a given state approximately recurring with a particular regularity. He demonstrated that it was possible to evolve systems that were able to display rhythmic behaviour [94]. Analysis of these evolved systems has been carried out to determine what properties of networks allow the emergence of robust rhythmic behaviour from inherently noisy components [103]. A pruning algorithm is presented that allows evolved rhythmic networks to be reduced to their functional core and reveal that a common feature of these networks is a ring of elements that produces travelling waves of activation. This architectural component acts as a cellular clock for the entire system, other nodes in the network being either stationary or entrained by the central clock. One limitation of this analysis is that it favours the evolution of rhythmic behaviour in networks with relatively low values of K. An advantage of these systems is their intrinsic robustness to external perturbation. The evolutionary search mechanism used to evolve these networks also biases the discovery of networks operating with a single timescale, whereas biological systems can accommodate more complex temporal designs [103].

Applications

Boolean networks of genetic regulation have also been applied in a number of other domains, including:

to build models of specific systems, such as, Drosophila embryogenesis [18] and the endothelial cell cycle [63];
as the basis for phenomenological models of a morphogenetic processes [59,60,61];
to study the evolutionary dynamics of regulatory networks [21,22,44];
as a framework for inferring regulatory networks from gene expression data [78,1,2,3]; and
as a biologically-inspired control mechanism for autonomous agents [35].

Strengths and limitations

The main strengths of the Boolean network model are its analytical tractability and the ease and efficiency with which it can be simulated. The primary limitations of the model are its perceived lack of applicability to biological systems. Some of these issues, such as connectivity and synchrony, have been raised in the section above. A more fundamental objection concerns the starting point for these models, the validity of the Boolean assumption. Some genes are known to have different regulatory effects depending on their level of expression and in some situations the transient period between as a gene switches may be significant. While a Boolean representation may be sufficient for a product that tends to be present either in excess, or in insignificant quantities, products whose concentration varies in a more smoothly continuous fashion may require a continuous function to accurately capture their dynamics [112,20]. A number of researchers have also demonstrated that there is not a direct correlation between the dynamic behaviour of Boolean systems and that of corresponding continuous systems [49,11], suggesting a qualitative loss of behavioural information.

Next: Generalised logic Up: Logical models Previous: Logical models

Nic Geard 2004-05-06