Expected Number of Fixed Points in Boolean Networks with Arbitrary Topology

Boolean network models describe genetic, neural, and social dynamics in complex networks, where the dynamics depend generally on network topology. Fixed points in a genetic regulatory network are typically considered to correspond to cell types in an organism. We prove that the expected number of fixed points in a Boolean network, with Boolean functions drawn from probability distributions that are not required to be uniform or identical, is one, and is independent of network topology if only a feedback arc set satisfies a stochastic neutrality condition. We also demonstrate that the expected number is increased by the predominance of positive feedback in a cycle.

Figure 1

An example set of a Boolean network and probability distributions of Boolean functions. Boolean function $f_i$, assigned to vertex $i$, is drawn from its probability distribution $P_i(f_i)$. Under link condition (i), a graph of $P_i(f_i)$ can have $2^{2^{K_i}}$ (the total number of Boolean functions) bars at most, where $K_i$ is the number of input links to vertex $i$. Under link condition (ii) or (iii), a graph has less than $2^{2^{K_i}}$ bars. In this example, uniform, biased, and more complicated distributions are illustrated for $P_1(f_1)$, $P_2(f_2)$, and $P_3(f_3)$.

Figure 2

(a) Schematic of a set of input vertices to vertex $i$, denoted by ${\mathit{J}}_{\mathit{i}}=\{1,2,3\}$. Subset ${\mathit{T}}_{\mathit{i}}=\{1,2\}$ is employed to classify Boolean functions $f_i$. (b) Truth table of three-variable Boolean functions. Based on the definition of an $\mathsf{N}$-equivalent class with respect to ${\mathit{T}}_{\mathit{i}}=\{1,2\}$, functions $A–D$, $E–H$, and $I–J$ are organized into classes labeled as $m_i({\mathit{T}}_{\mathit{i}})=1$, 2, and 3. The number of functions in the $m_i({\mathit{T}}_{\mathit{i}})$th class, $Q_i[m_i({\mathit{T}}_{\mathit{i}})]$, depends on $m_i({\mathit{T}}_{\mathit{i}})$.

Figure 3

Definition of feedback arc set (FAS). The bold arrows and circles in the original network correspond to links forming the FAS and vertices taking these links, respectively. Numbers 1–5 in the acyclic network represent an acyclic ordering. Therefore, $j<i$ holds for any link $j\to i$.

Figure 4

Numerically obtained frequency distributions of the number of FPs for each BN (a)–(d). (a),(b) Boolean functions for all vertices were randomly generated under the $p$ bias ($p=0.6$). (c) The functions $f_{3,5}$ were assumed to be only AND functions. (d) The links labeled as $+$ and $-$ were constrained in positive and negative interactions, respectively. The average values were (a)–(c) $⟨n⟩=1.0$ and (d) 5.2.