Boolean network

State space of a Boolean network with N = 4 nodes and K = 1 edges per node (thin black arrows). Each node can either be switched on (red) or switched off (blue). For the sake of simplicity, only copy functions are used here. The thick (gray) arrows symbolize what a (synchronous) update does. The example has a total of four fixed point attractors, which are shown as large (orange) circles. There are also two attractors of length two.

Boolean networks refer to a model from statistical physics . They can be understood as a generalization of the Ising model , namely as a spin dynamics on a digraph . Each node is assigned both a Boolean state (or spin) and a Boolean function about the states of the incoming nodes. ${\displaystyle G=(V,E)}$ ${\displaystyle V}$

These update rules define the system dynamics, which are not trivial despite simple rules. In 1969, the doctor Stuart Kauffman was the first scientist to propose Boolean networks as a model for genetic networks, specifically for the special case that there are nodes (or genes ) that each depend exactly on other nodes , which is why this variation is also called the - model . Although Boolean networks are defined by simple rules, system dynamics were not understood mathematically until after 2000. ${\displaystyle N}$ ${\displaystyle K}$ ${\displaystyle N}$ ${\displaystyle K}$

Although Boolean networks are a vast oversimplification ( genes are never just on or off ), there are many examples in which a Boolean model predicts the correct sequence of switching events in a genetic network.

Math background

Networks are one way of studying the properties of complex systems . The topology of a graph reflects how the various units of the system interact with one another. Dynamics defined in addition to the topology can either change the edges of the graph over time (dynamics from the network) or only the values ​​of the nodes (dynamics on the network). Boolean networks are the second variant.

An important question when studying Boolean networks is to analyze the global properties of a given ensemble. The number and length of the attractors are one way of quantifying the global properties. The challenge here is that the state space grows extremely quickly, namely with it . Even with modern computers, memory limits are quickly reached. The simplest ensemble are the random Boolean networks (English: Random Boolean Networks , RBN). Here the graph topology is an Erdős-Rényi random graph . For RBNS there have been many attempts to characterize the distribution of attractors by means of mean values depending on the number of nodes. ${\displaystyle 2^{N}}$ ${\displaystyle N}$

Authors	year	Medium attractor length ${\displaystyle \langle A\rangle }$	Medium attractor number ${\displaystyle \langle \nu \rangle }$
Kauffman	1969	${\displaystyle \langle A\rangle \sim {\sqrt {N}}}$	${\displaystyle \langle \nu \rangle \sim {\sqrt {N}}}$
Bastolla / Parisi	1998	faster than a power law, ${\displaystyle \langle A\rangle >N^{x}\forall x}$	faster than a power law, ${\displaystyle \langle \nu \rangle >N^{x}\forall x}$
Bilke / Sjunnesson	2002		linear with the system size, ${\displaystyle \langle \nu \rangle \sim N}$
Socolar / Kauffman	2003		faster than linear, with ${\displaystyle \langle \nu \rangle >N^{x}}$ ${\displaystyle x>1}$
Samuelsson / Troein	2003		Proof of superpolynomial growth, ${\displaystyle \langle \nu \rangle >N^{x}\forall x}$
Mihaljev / thrush	2005	analytical argument for superpolynomial growth, ${\displaystyle \langle A\rangle >N^{x}\forall x}$	analytical argument for superpolynomial growth, ${\displaystyle \langle \nu \rangle >N^{x}\forall x}$

Individual evidence

1. ^ ^{A b} Stuart Kauffman: Homeostasis and Differentiation in Random Genetic Control Networks . In: Nature . 224, No. 5215, October 11, 1969, pp. 177-178. doi : 10.1038 / 224177a0 .
2. ↑ Barbara Drossel: Chapter 3. Random Boolean Networks . In: Cornell University . December 2009. arxiv : 0706.3351v2 . doi : 10.1002 / 9783527626359.ch3 .
3. ^ Réka Albert, Hans G Othmer: The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster . In: Journal of Theoretical Biology . 223, No. 1, July 2003, pp. 1-18. doi : 10.1016 / S0022-5193 (03) 00035-3 .
4. ↑ J. Li, AJ Bench, GS Vassiliou, N. Fourouclas, AC Ferguson-Smith, AR Green: Imprinting of the human L3MBTL gene, a polycomb family member located in a region of chromosome 20 deleted in human myeloid malignancies . In: Proceedings of the National Academy of Sciences . 101, No. 19, April 30, 2004, pp. 7341-7346. doi : 10.1073 / pnas.0308195101 .
5. ↑ U. Bastolla, G. Parisi: The modular structure of Kauffman networks . In: Physica D: Nonlinear Phenomena . 115, No. 3-4, May 1998, pp. 219-233. doi : 10.1016 / S0167-2789 (97) 00242-X .
6. ^ Sven Bilke, Fredrik Sjunnesson: Stability of the Kauffman model . In: Physical Review E . 65, No. 1, December 2001. doi : 10.1103 / PhysRevE.65.016129 .
7. ↑ J. Socolar, S. Kauffman: Scaling in Ordered and Critical Random Boolean Networks . In: Physical Review Letters . 90, No. 6, February 2003. arxiv : cond-mat / 0212306 . doi : 10.1103 / PhysRevLett.90.068702 .
8. ↑ Björn Samuelsson, Carl Troein: Superpolynomial Growth in the Number of Attractors in Kauffman Networks . In: Physical Review Letters . 90, No. 9, March 2003. doi : 10.1103 / PhysRevLett.90.098701 .
9. ↑ Tamara Mihaljev, Barbara Drossel: Scaling in a general class of critical random Boolean networks . In: Physical Review E . 74, No. 4, October 2006. doi : 10.1103 / PhysRevE.74.046101 .