Compositional properties of random Boolean networks

Random Boolean networks (RBNs) are used in a number of applications, including cell differentiation, immune response, evolution, gene regulatory networks, and neural networks. This paper addresses the problem of computing attractors in RBNs. An RBN with $n$ vertices has up to $2^n$ states. Therefore, for large $n$, computing attractors by full enumeration of states is not feasible. The state space can be reduced by removing irrelevant vertices, which have no influence on the network’s dynamics. In this paper, we show that attractors of an RBN can be computed compositionally from the attractors of the independent components of the subgraph induced by the relevant vertices of the network. The presented approach reduces the complexity of the problem from $O\left(2^n\right)$ to $O\left(2^l\right)$, where $l$ is the number of relevant vertices in the largest component.

Figure 1

Example of an RBN. The state of a vertex $v_i$ at time $t+1$ is given by ${\sigma }_{v_i}(t+1)=f_{v_i}\mathbf{(}{\sigma }_{v_j}\left(t\right),{\sigma }_{v_k}\left(t\right)\mathbf{)}$, where $v_j$ and $v_k$ are the predecessors of $v_i$, and $f_{v_i}$ is the Boolean function associated to $v_i$ (shown by the Boolean expression inside $v_i$).

Figure 2

Reduced network $G_R$ for the RBN in Fig. 1.

Figure 3

(a) State space of the component $G_1=\{v_2,v_5,v_9\}$. There are two attractors, $A_{11}=⟨011,100⟩$ and $A_{12}=⟨000,001,101,111,110,010⟩$. (b) State space of the component $G_2=\{v_1,v_7\}$. There is one attractor, $A_{21}=⟨00,10,11,01⟩$.