618 lines
63 KiB
TeX
618 lines
63 KiB
TeX
\documentclass[journal,compsoc,10pt]{IEEEtran}
|
||
|
||
% Load some possibly useful packages. You can remove the ones you don't need or
|
||
% add other packages that you need in your paper.
|
||
\usepackage{graphicx} % required to include graphics
|
||
\usepackage{amsfonts,amssymb,amsmath} % mathsymbols etc
|
||
\usepackage{mathtools} % includes some fixes to amsmath, and adds convenience macros
|
||
\usepackage{bm} % make any letter boldface in math
|
||
\usepackage{algpseudocode} % aka `algorithmicx`: same look `algorithmic`, but more flexible
|
||
\usepackage{array} % for better looking arrays
|
||
\usepackage{booktabs} % for better looking tables
|
||
\usepackage[usenames]{xcolor} % colors for highlighting etc.
|
||
\usepackage{url} % for urls
|
||
\usepackage{cite}
|
||
\usepackage[%pdftitle=, % define the PDF metadata
|
||
%pdfauthor=,
|
||
colorlinks=true, linkcolor=purple, urlcolor=blue, citecolor=cyan,
|
||
anchorcolor=black % make links/references 'clickable' without ugly frames
|
||
]{hyperref}
|
||
\usepackage{cleveref} % smart references to figures, equations etc.
|
||
|
||
% some packages which may be useful when drafting, but should be removed before submission
|
||
\usepackage{todonotes}
|
||
|
||
|
||
|
||
\usepackage{tikz}
|
||
|
||
\usepackage[caption=false, font=footnotesize]{subfig}
|
||
\renewcommand{\citepunct}{, }
|
||
|
||
% You can define your own commands. This is useful for shorthands, for example
|
||
\newcommand{\EE}{\mathbb{E}}
|
||
\newcommand{\RR}{\mathbb{R}}
|
||
\newcommand{\eE}{\mathcal{E}}
|
||
\newcommand{\gG}{\mathcal{G}}
|
||
\newcommand{\nN}{\mathcal{N}}
|
||
\newcommand{\lnorm}[1]{\ell_{#1}\text{-norm}}
|
||
|
||
% Commands are also useful to ensure standardized notation, such as how to display vectors and matrices.
|
||
% The point is to replace formatting commands with semantic ones.
|
||
% This both makes the source more semantic, and also makes it easier to change formatting choices later
|
||
% IMPORTANT: In TeX, all commands share a global namespace. You need to be careful therefore not to overwrite an existing command.
|
||
% Use \newcommand to ensure you don't accidentally overwrite an important macro
|
||
% Use \renewcommand if you *do* want to overwrite a macro, have checked what the original does,
|
||
% and have made sure the redefinition is safe.
|
||
\newcommand{\T}{\mathsf{T}} % transpose
|
||
\renewcommand{\vec}[1]{\bm{#1}} % redefine \vec to produce boldface instead of adding an arrow
|
||
\newcommand{\mat}[1]{\bm{#1}} % define \vec to produce boldface
|
||
\newcommand{\ones}{\bm{1}} % all-ones vector
|
||
\newcommand{\eye}{\bm{I}} % identity matrix
|
||
\newcommand{\ei}{\bm{e}_i} % standard basis vector e_i
|
||
\newcommand{\ej}{\bm{e}_j} % standard basis vector e_j
|
||
% TIP: Resist the temptation to be too clever with macros
|
||
% - \ei and \ej are easier to type than e.g. \ee[i] (note that \e is a low-level command and should not be redefined)
|
||
% - While you can define macros in terms of other macros (eg we could define \ei in terms of \vec),
|
||
% many journals won’t accept this. Recursive macros also produce more frequent and more complicated compilation errors
|
||
|
||
% Commands like \sin and \exp ensure proper fonts and spacing for math operators.
|
||
% Use the dedicated \DeclareMathOperator to define new operators
|
||
\DeclareMathOperator{\diag}{diag}
|
||
|
||
|
||
\begin{document}
|
||
|
||
\title{Influence of update schemes on boolean networks}
|
||
|
||
% author information
|
||
% COMMENT OUT THESE LINES FOR YOUR CONFERENCE SUBMISSION!
|
||
% \author{Tom Zuidberg \\ 455969}
|
||
|
||
\maketitle
|
||
\thispagestyle{plain}
|
||
\pagestyle{plain}
|
||
|
||
\begin{abstract}
|
||
Boolean networks are a widely used framework for modeling the qualitative dynamics of biological regulatory systems. A central modeling decision is the choice of update scheme, which determines how and when individual nodes are evaluated at each time step and directly shapes the resulting dynamics. This paper introduces and compares four commonly used update schemes: synchronous, sequential, probabilistic, and asynchronous. We analyze how each scheme affects attractor structure, reachability, and network robustness, and discuss their practical implications for the modeling of gene regulatory networks. A central finding is that the same network can exhibit fundamentally different attractors depending on which scheme is used, demonstrating that the choice of update scheme is not a neutral implementation detail but a direct factor that influences the dynamical behavior of the model and the biological conclusions that can be drawn from it.
|
||
\end{abstract}
|
||
|
||
|
||
\section{Introduction}
|
||
Boolean networks were first introduced by Stuart Kauffman in the late 1960s as a simplified model of biochemical systems \cite{helikar2011boolean}. In this framework, genes or regulatory components are represented as binary variables, each taking a value of either 0 (inactive) or 1 (active), whose states evolve according to logical update functions encoding regulatory interactions. Despite their simplicity, boolean networks have proven useful in capturing qualitative dynamical behavior in complex biochemical systems, and have since become a standard tool of modeling in systems biology \cite{bornholdt2008boolean}.
|
||
|
||
A key abstraction in boolean network modeling is the concept of attractors. Since a boolean network with $n$ nodes has exactly $2^n$ possible states and the dynamics are deterministic, the system must eventually revisit a state it has already visited, by the pigeonhole principle \cite{rosen2019discrete}. The resulting recurring patterns, either fixed-points or limit cycles, are called attractors and are often interpreted as stable cellular or functional states \cite{helikar2011boolean}. In the context of gene regulatory networks (GRNs), attractors have been proposed to correspond to distinct cell types or phenotypic states \cite{bornholdt2008boolean}.
|
||
|
||
Gene regulatory networks describe the interactions between genes, transcription factors, and other molecular entities that together control gene expression. Modeling GRNs as boolean networks provides a simplified view: instead of tracking continuous concentration levels of molecular species, each gene is treated as either expressed or silenced. This allows for qualitative insight into questions such as how different cell types arise from the same genetic blueprint, or how mutations affect the stable states of the system \cite{bornholdt2008boolean, schwab2020concepts}.
|
||
|
||
When it comes to modeling a system as a boolean network, the choice of update scheme plays an important role, as it defines how and when individual nodes are updated at each time step. This choice is not merely a technical detail, since it affects which attractors exist, which states are reachable from a given initial condition, and how robustly the network responds to perturbations \cite{schwab2020concepts, aracena2009robustness}. The most commonly used schemes include the synchronous scheme, where all nodes update simultaneously; the sequential scheme, where nodes are updated one after another in a fixed order; the probabilistic scheme, which introduces randomness into the update process; and the asynchronous scheme, where only one node is updated per time step.
|
||
|
||
The question of which update scheme best reflects biological reality has been an active area of research. Asynchronous schemes have often been considered more biologically plausible, since biochemical processes in living cells rarely occur simultaneously across all genes. However, as recent studies have shown, synchronous and asynchronous schemes can lead to the same meaningful behavior under the right conditions, and the practical choice of scheme often comes down to available biological knowledge and computational feasibility \cite{schwab2020concepts}.
|
||
|
||
In the following, we will introduce the formal model of boolean networks in \cref{sec:bn}, followed by a comparison of the different update schemes in \cref{sec:update_schemes}. Finally, in \cref{sec:relevance_grn}, we will discuss the implications of these schemes for the modeling of gene regulatory networks.
|
||
|
||
\section{Boolean networks}
|
||
\label{sec:bn}
|
||
A boolean network consists of nodes $x_i(t)$ that have a boolean state, either $0$ or $1$, at a point in time $t$. Each node has a corresponding update function
|
||
\begin{equation}
|
||
\label{eq:update_fn}
|
||
f_i(x_1(t), x_2(t), \ldots, x_n(t)) = x_i(t+1),
|
||
\end{equation}
|
||
expressing the new state of $x_i(t+1)$, where $f_i$ takes as input the states of all nodes connected to node $i$ by an incoming edge. The state of the boolean network can be described as a binary string \mbox{$x(t) = x_1 x_2\ldots x_n$} where each node is replaced with the corresponding state 0 or 1.
|
||
|
||
|
||
\begin{figure}
|
||
\centering
|
||
|
||
\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt
|
||
\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
|
||
%uncomment if require: \path (0,321); %set diagram left start at 0, and has height of 321
|
||
|
||
%Shape: Circle [id:dp6120737986176485]
|
||
\draw (89.67,50) .. controls (89.67,38.95) and (98.62,30) .. (109.67,30) .. controls (120.71,30) and (129.67,38.95) .. (129.67,50) .. controls (129.67,61.05) and (120.71,70) .. (109.67,70) .. controls (98.62,70) and (89.67,61.05) .. (89.67,50) -- cycle ;
|
||
%Shape: Circle [id:dp4460102181537059]
|
||
\draw (179.67,50) .. controls (179.67,38.95) and (188.62,30) .. (199.67,30) .. controls (210.71,30) and (219.67,38.95) .. (219.67,50) .. controls (219.67,61.05) and (210.71,70) .. (199.67,70) .. controls (188.62,70) and (179.67,61.05) .. (179.67,50) -- cycle ;
|
||
%Shape: Circle [id:dp5043508885922044]
|
||
\draw (89.67,130) .. controls (89.67,118.95) and (98.62,110) .. (109.67,110) .. controls (120.71,110) and (129.67,118.95) .. (129.67,130) .. controls (129.67,141.05) and (120.71,150) .. (109.67,150) .. controls (98.62,150) and (89.67,141.05) .. (89.67,130) -- cycle ;
|
||
%Shape: Circle [id:dp19837549619745176]
|
||
\draw (179.67,130) .. controls (179.67,118.95) and (188.62,110) .. (199.67,110) .. controls (210.71,110) and (219.67,118.95) .. (219.67,130) .. controls (219.67,141.05) and (210.71,150) .. (199.67,150) .. controls (188.62,150) and (179.67,141.05) .. (179.67,130) -- cycle ;
|
||
%Straight Lines [id:da34212297668952507]
|
||
\draw (129.67,46) -- (177.67,46) ;
|
||
\draw [shift={(179.67,46)}, rotate = 180] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (12,-3) -- (0,0) -- (12,3) -- cycle ;
|
||
%Straight Lines [id:da9191192486085845]
|
||
\draw (179.67,54) -- (131.67,54) ;
|
||
\draw [shift={(129.67,54)}, rotate = 360] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (12,-3) -- (0,0) -- (12,3) -- cycle ;
|
||
%Straight Lines [id:da9988186797184601]
|
||
\draw (109.67,70) -- (109.67,108) ;
|
||
\draw [shift={(109.67,110)}, rotate = 270] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (12,-3) -- (0,0) -- (12,3) -- cycle ;
|
||
%Straight Lines [id:da0026996459711727816]
|
||
\draw (129.67,126) -- (177.67,126) ;
|
||
\draw [shift={(179.67,126)}, rotate = 180] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (12,-3) -- (0,0) -- (12,3) -- cycle ;
|
||
%Straight Lines [id:da6389438894367955]
|
||
\draw (179.67,134) -- (131.67,134) ;
|
||
\draw [shift={(129.67,134)}, rotate = 360] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (12,-3) -- (0,0) -- (12,3) -- cycle ;
|
||
|
||
% Text Node
|
||
\draw (105.17,42.5) node [anchor=north west][inner sep=0.75pt] [align=left] {1};
|
||
% Text Node
|
||
\draw (194.67,42.5) node [anchor=north west][inner sep=0.75pt] [align=left] {2};
|
||
% Text Node
|
||
\draw (104.67,122.5) node [anchor=north west][inner sep=0.75pt] [align=left] {3};
|
||
% Text Node
|
||
\draw (194.67,122) node [anchor=north west][inner sep=0.75pt] [align=left] {4};
|
||
|
||
\end{tikzpicture}
|
||
\begin{align}
|
||
f_1 &= \neg x_2 \nonumber \\
|
||
f_2 &= x_1 \nonumber \\
|
||
f_3 &= x_1\oplus x_4 \nonumber \\
|
||
f_4 &= x_3
|
||
\end{align}
|
||
\caption{Example of a boolean network with four nodes. Each vertex indicates that a node is part of the update function of the other node. For instance $x_1$ is part of $f_2$ and $f_3$. Note that $\neg$ means the logical NOT and $\oplus$ means the logical XOR function.
|
||
}
|
||
\label{fig:bn_example}
|
||
\end{figure}
|
||
|
||
Consider the boolean network shown in \cref{fig:bn_example}. For example, if the state is $x(t)=0011$ at time $t$, it means that $x_1, x_2$ are $0$ and $x_3, x_4$ are $1$. After applying the synchronous update, the next state $x(t+1)$ is $1011$. Updating the network multiple times creates a trajectory, which is the sequence of the states starting from the initial state. Continuing with the example from \cref{fig:bn_example}, the trajectory is $0011 \rightarrow 1011 \rightarrow 1101 \rightarrow 0100 \rightarrow \ldots$. Each trajectory in a boolean network eventually reaches one of two scenarios: either it falls into a fixed-point attractor, which is a state that loops back into itself upon update; or it falls into a periodic cycle of states called limit cycle.
|
||
|
||
A \textit{state graph} is a directed graph that shows all the possible states of the boolean network along the corresponding trajectories that can be navigated by starting at any state and following the direction of the edges. For example, the state graph in \cref{fig:bn_syn_state_graph} shows the trajectories from the boolean network in \cref{fig:bn_example}. These state graphs help visualize the fixed-point and limit cycles, e.g. 2 cycles of length 8.
|
||
|
||
In boolean networks, \textit{robustness} refers to the stability of the behavior with regard to perturbations, e.g. a single node state change. A boolean network with poor robustness means that a simple flip of a node can change the resulting attractor or cycle for that trajectory. With regard to our example from \cref{fig:bn_syn_state_graph}, if either $x_3$ or $x_4$ (not both at once) is flipped, the cycle switches. A strong robustness however would mean that even with such perturbations, the resulting attractor or cycle does not change.
|
||
|
||
The set of all states that eventually lead to a particular attractor is called its \emph{basin of attraction}. In the state graph in \cref{fig:bn_syn_state_graph}, the two cycles each have a basin of eight states, meaning that starting from any state in a basin, the network will always converge to the corresponding attractor. Larger basins generally indicate more dominant or robust attractors. In biological terms, a large basin could, for example, represent a cell state that is easily reached and hard to escape from, which shows that they are ideal to model stable functional states.
|
||
|
||
Not every state in a boolean network is reachable from another state through the dynamics. States that have no predecessor in the state graph are called \emph{garden-of-Eden states}: they can only appear as initial conditions and are never produced by any update step. Their presence reduces the effective state space that the network can explore during normal operation. In the synchronous state graph of \cref{fig:bn_syn_state_graph}, no garden-of-Eden states are present, since every state is reachable from at least one other state within the two cycles.
|
||
|
||
The structure of the state graph, including the number and size of attractors, the shape of their basins and the presence of garden-of-Eden states, depends critically on both the network topology and the choice of update scheme. The following section illustrates how changing the update scheme while keeping the network and its update functions fixed can produce a completely different state graph, with different attractors, different basins and different reachability properties.
|
||
|
||
|
||
|
||
\begin{figure}
|
||
\centering
|
||
\includegraphics[height=7cm]{bn_example_table.png}
|
||
|
||
\caption{State transitions for all states of the boolean network from \cref{fig:bn_example} using synchronous update scheme once.}
|
||
\label{fig:bn_state_table}
|
||
\end{figure}
|
||
|
||
|
||
\begin{figure}
|
||
|
||
|
||
\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt
|
||
|
||
\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
|
||
%uncomment if require: \path (0,182); %set diagram left start at 0, and has height of 182
|
||
|
||
%Straight Lines [id:da7515060673133168]
|
||
\draw (63,30) -- (91,30) ;
|
||
\draw [shift={(93,30)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da5101009163931332]
|
||
\draw (133,30) -- (161,30) ;
|
||
\draw [shift={(163,30)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da17974568496180332]
|
||
\draw (203,30) -- (231,30) ;
|
||
\draw [shift={(233,30)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da28479803325341]
|
||
\draw (93,70) -- (65,70) ;
|
||
\draw [shift={(63,70)}, rotate = 360] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da9289522355407928]
|
||
\draw (163,70) -- (135,70) ;
|
||
\draw [shift={(133,70)}, rotate = 360] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da5098188343671546]
|
||
\draw (233,70) -- (205,70) ;
|
||
\draw [shift={(203,70)}, rotate = 360] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da48531701923414494]
|
||
\draw (43,60) -- (43,42) ;
|
||
\draw [shift={(43,40)}, rotate = 90] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da8391791574907262]
|
||
\draw (253,40) -- (253,58) ;
|
||
\draw [shift={(253,60)}, rotate = 270] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da24177074905043572]
|
||
\draw (63,110) -- (91,110) ;
|
||
\draw [shift={(93,110)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da21625025411268273]
|
||
\draw (133,110) -- (161,110) ;
|
||
\draw [shift={(163,110)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da9822082649794383]
|
||
\draw (203,110) -- (231,110) ;
|
||
\draw [shift={(233,110)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da1915219980691898]
|
||
\draw (93,150) -- (65,150) ;
|
||
\draw [shift={(63,150)}, rotate = 360] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da22061673245947822]
|
||
\draw (163,150) -- (135,150) ;
|
||
\draw [shift={(133,150)}, rotate = 360] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da6267831846161589]
|
||
\draw (233,150) -- (205,150) ;
|
||
\draw [shift={(203,150)}, rotate = 360] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da6290428382558753]
|
||
\draw (43,140) -- (43,122) ;
|
||
\draw [shift={(43,120)}, rotate = 90] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da9391797989074463]
|
||
\draw (253,120) -- (253,138) ;
|
||
\draw [shift={(253,140)}, rotate = 270] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
|
||
% Text Node
|
||
\draw (24,22) node [anchor=north west][inner sep=0.75pt] [align=left] {0000};
|
||
% Text Node
|
||
\draw (94,22) node [anchor=north west][inner sep=0.75pt] [align=left] {1000};
|
||
% Text Node
|
||
\draw (164,22) node [anchor=north west][inner sep=0.75pt] [align=left] {1110};
|
||
% Text Node
|
||
\draw (234,22) node [anchor=north west][inner sep=0.75pt] [align=left] {0111};
|
||
% Text Node
|
||
\draw (94,62) node [anchor=north west][inner sep=0.75pt] [align=left] {1101};
|
||
% Text Node
|
||
\draw (24,62) node [anchor=north west][inner sep=0.75pt] [align=left] {0100};
|
||
% Text Node
|
||
\draw (164,62) node [anchor=north west][inner sep=0.75pt] [align=left] {1011};
|
||
% Text Node
|
||
\draw (234,62) node [anchor=north west][inner sep=0.75pt] [align=left] {0011};
|
||
% Text Node
|
||
\draw (24,102) node [anchor=north west][inner sep=0.75pt] [align=left] {0001};
|
||
% Text Node
|
||
\draw (94,102) node [anchor=north west][inner sep=0.75pt] [align=left] {1010};
|
||
% Text Node
|
||
\draw (164,102) node [anchor=north west][inner sep=0.75pt] [align=left] {1111};
|
||
% Text Node
|
||
\draw (234,102) node [anchor=north west][inner sep=0.75pt] [align=left] {0101};
|
||
% Text Node
|
||
\draw (94,142) node [anchor=north west][inner sep=0.75pt] [align=left] {1100};
|
||
% Text Node
|
||
\draw (24,142) node [anchor=north west][inner sep=0.75pt] [align=left] {0110};
|
||
% Text Node
|
||
\draw (164,142) node [anchor=north west][inner sep=0.75pt] [align=left] {1001};
|
||
% Text Node
|
||
\draw (234,142) node [anchor=north west][inner sep=0.75pt] [align=left] {0010};
|
||
|
||
|
||
\end{tikzpicture}
|
||
\centering
|
||
\caption{State graph of the boolean network shown in \cref{fig:bn_example} using synchronous update scheme showing two separate limit cycles of length 8.}
|
||
\label{fig:bn_syn_state_graph}
|
||
\end{figure}
|
||
|
||
|
||
|
||
|
||
\section{Update Schemes}
|
||
\label{sec:update_schemes}
|
||
The dynamics of a boolean network depend not only on its topology and update functions, but also on the choice of update scheme, which defines how and when nodes are updated at each time step. Different schemes can lead to a notably different behavior, including different attractor structures, reachability properties and robustness characteristics \cite{schwab2020concepts, aracena2009robustness}. In general, update schemes can be divided into deterministic schemes, where the sequence of updates is fixed, and stochastic schemes, where randomness plays a role. In the following subsections, we introduce four commonly used update schemes and depict their effects on the boolean network from \cref{fig:bn_example}.
|
||
|
||
\subsection{Synchronous scheme}
|
||
In \cref{sec:bn}, we have used the \textit{synchronous update scheme} to introduce the general dynamics of boolean networks. This scheme assumes that each update function takes the exact same amount of time and executes at the same time, which means that regardless of the outcome of the first function, any subsequent function will have the same result. Updating the network with this method is quite simple, always leads to a deterministic output, and does not require a lot of computing power in order to simulate larger networks, as each state of the network results in exactly one updated state. With regard to gene regulatory networks however, this is an oversimplification as biological GRNs never execute fully synchronously. Furthermore, the change of one node has no direct effect on any other function, whereas larger biochemical systems often show dependencies between regulatory functions \cite{helikar2011boolean, schwab2020concepts}.
|
||
|
||
Despite this biological limitation, the synchronous scheme has important structural properties that make it the most widely used scheme in practice. Since every global state maps to exactly one successor state, the state space forms a functional graph in which every node has exactly one outgoing edge, which, as we previously covered, will converge to either a fixed-point attractor or a limit cycle. Hence, the full attractor landscape is completely determined by the update functions alone \cite{helikar2011boolean}. As a direct consequence, all attractors can be found by exhaustively simulating every possible initial state, which requires at most $2^n$ simulations of bounded length. For networks of moderate size this is computationally feasible, making synchronous update well suited for systematic attractor analysis. For very large networks, however, this exhaustive approach quickly becomes infeasible due to the exponential growth of the number of states.
|
||
|
||
The synchronous scheme was also the original formulation used by Kauffman when he introduced random boolean networks as a model of gene regulation \cite{helikar2011boolean}. In his analysis of networks, where update functions are assigned randomly, Kauffman found that the average number and length of attractors depends strongly on the average node connectivity $K$. At low connectivity the network settles quickly into a small number of short attractors; at high connectivity the dynamics become chaotic with very long cycle lengths. At a critical connectivity of around $K = 2$ the network is poised between these two regimes, a property that has been proposed as a signature of real biological regulatory networks \cite{bornholdt2008boolean}. This critical behavior and the tools used to study it are defined with respect to the synchronous scheme, which illustrates why the synchronous update remains central to the theoretical analysis of boolean networks even when other schemes may be more biologically appropriate.
|
||
|
||
|
||
|
||
|
||
|
||
|
||
\subsection{Sequential scheme}
|
||
In the \textit{sequential update scheme}, nodes are updated one after another in a fixed order within each time step, which allows for side effects: the updated value of an earlier node in the sequence can influence the outcome of later ones. For example, take the sequence $(x_1, x_2, x_3, x_4)$. Updating the state $0000$ means first using $f_1$ which results in an intermediate state $1000$, then using $f_2$, then $f_3$, and lastly $f_4$. This will lead to $0000 \rightarrow 1111$, a different state from that produced when using the synchronous update scheme. In fact, the whole state graph changes depending on the update scheme used, namely every initial state will fall into a single 4-state cycle: $0000 \rightarrow 1111 \rightarrow 0011 \rightarrow 1100 \rightarrow 0000$ (see \cref{fig:bn_seq_state_graph}).
|
||
|
||
\begin{figure}
|
||
\centering
|
||
|
||
\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt
|
||
|
||
\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
|
||
%uncomment if require: \path (0,182); %set diagram left start at 0, and has height of 182
|
||
|
||
%Straight Lines [id:da7515060673133168]
|
||
\draw (60,40) -- (88.34,58.89) ;
|
||
\draw [shift={(90,60)}, rotate = 213.69] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da5101009163931332]
|
||
\draw (130,70) -- (158,70) ;
|
||
\draw [shift={(160,70)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da17974568496180332]
|
||
\draw (180,40) -- (180,58) ;
|
||
\draw [shift={(180,60)}, rotate = 270] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da28479803325341]
|
||
\draw (230,70) -- (202,70) ;
|
||
\draw [shift={(200,70)}, rotate = 360] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da9289522355407928]
|
||
\draw (230,40) -- (201.66,58.89) ;
|
||
\draw [shift={(200,60)}, rotate = 326.31] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da5098188343671546]
|
||
\draw (230,110) -- (202,110) ;
|
||
\draw [shift={(200,110)}, rotate = 360] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da48531701923414494]
|
||
\draw (110,100) -- (110,82) ;
|
||
\draw [shift={(110,80)}, rotate = 90] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da8391791574907262]
|
||
\draw (180,80) -- (180,98) ;
|
||
\draw [shift={(180,100)}, rotate = 270] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da24177074905043572]
|
||
\draw (60,110) -- (88,110) ;
|
||
\draw [shift={(90,110)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da21625025411268273]
|
||
\draw (60,70) -- (88,70) ;
|
||
\draw [shift={(90,70)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da9822082649794383]
|
||
\draw (60,140) -- (88.34,121.11) ;
|
||
\draw [shift={(90,120)}, rotate = 146.31] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da1915219980691898]
|
||
\draw (180,140) -- (180,122) ;
|
||
\draw [shift={(180,120)}, rotate = 90] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da22061673245947822]
|
||
\draw (230,140) -- (201.66,121.11) ;
|
||
\draw [shift={(200,120)}, rotate = 33.69] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da6267831846161589]
|
||
\draw (160,110) -- (132,110) ;
|
||
\draw [shift={(130,110)}, rotate = 360] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da6290428382558753]
|
||
\draw (110,140) -- (110,122) ;
|
||
\draw [shift={(110,120)}, rotate = 90] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
%Straight Lines [id:da9391797989074463]
|
||
\draw (110,40) -- (110,58) ;
|
||
\draw [shift={(110,60)}, rotate = 270] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29) ;
|
||
|
||
% Text Node
|
||
\draw (91,62) node [anchor=north west][inner sep=0.75pt] [align=left] {0000};
|
||
% Text Node
|
||
\draw (231,62) node [anchor=north west][inner sep=0.75pt] [align=left] {1000};
|
||
% Text Node
|
||
\draw (21,22) node [anchor=north west][inner sep=0.75pt] [align=left] {1110};
|
||
% Text Node
|
||
\draw (161,142) node [anchor=north west][inner sep=0.75pt] [align=left] {0111};
|
||
% Text Node
|
||
\draw (231,102) node [anchor=north west][inner sep=0.75pt] [align=left] {1101};
|
||
% Text Node
|
||
\draw (24,62) node [anchor=north west][inner sep=0.75pt] [align=left] {0100};
|
||
% Text Node
|
||
\draw (21,142) node [anchor=north west][inner sep=0.75pt] [align=left] {1011};
|
||
% Text Node
|
||
\draw (161,102) node [anchor=north west][inner sep=0.75pt] [align=left] {0011};
|
||
% Text Node
|
||
\draw (91,142) node [anchor=north west][inner sep=0.75pt] [align=left] {0001};
|
||
% Text Node
|
||
\draw (231,22) node [anchor=north west][inner sep=0.75pt] [align=left] {1010};
|
||
% Text Node
|
||
\draw (161,62) node [anchor=north west][inner sep=0.75pt] [align=left] {1111};
|
||
% Text Node
|
||
\draw (231,142) node [anchor=north west][inner sep=0.75pt] [align=left] {0101};
|
||
% Text Node
|
||
\draw (91,102) node [anchor=north west][inner sep=0.75pt] [align=left] {1100};
|
||
% Text Node
|
||
\draw (91,22) node [anchor=north west][inner sep=0.75pt] [align=left] {0110};
|
||
% Text Node
|
||
\draw (21,102) node [anchor=north west][inner sep=0.75pt] [align=left] {1001};
|
||
% Text Node
|
||
\draw (161,22) node [anchor=north west][inner sep=0.75pt] [align=left] {0010};
|
||
|
||
|
||
\end{tikzpicture}
|
||
|
||
\caption{State graph of the boolean network shown in \cref{fig:bn_example} using the sequential update with the sequence $(x_1, x_2, x_3, x_4)$, leading to a limit cycle of length 4.}
|
||
|
||
\label{fig:bn_seq_state_graph}
|
||
|
||
\end{figure}
|
||
|
||
While the sequential update scheme produces different dynamics than those of the synchronous one (see \cref{fig:bn_syn_state_graph}), it is always possible to derive an equivalent synchronous function set that produces identical state transitions. The key observation is that when a node $x_i$ is evaluated in a sequential update, all nodes $x_j$ that appear earlier in the sequence have already been updated to their new values. The synchronous equivalent $f'_i$ is therefore obtained from $f_i$ (see \cref{eq:update_fn}) by substituting, for each input variable $x_j$ that precedes $x_i$ in the sequence, the already-derived new function $f'_j$ in place of $x_j$.
|
||
|
||
For the boolean network from \cref{fig:bn_example} with sequence $(x_1, x_2, x_3, x_4)$, the conversion proceeds as follows. Since $x_1$ is first in the sequence, its function is unchanged. For $x_2$, the original function $f_2 = x_1$ depends on $x_1$, which has already been updated; substituting $x_1 \mapsto f'_1$ gives $f'_2 = f'_1$. For $x_3$, the function $f_3 = x_1 \oplus x_4$ depends on $x_1$ (already updated) but not $x_2$; substituting $x_1 \mapsto f'_1$ gives $f'_3 = f'_1 \oplus x_4$. Finally, $f_4 = x_3$ depends on $x_3$, which has already been updated; substituting $x_3 \mapsto f'_3$ gives $f'_4 = f'_3$. Expanding these yields the synchronous functions
|
||
\begin{align}
|
||
f'_1 &= \neg x_2, \nonumber \\
|
||
f'_2 &= f'_1 = \neg x_2, \nonumber \\
|
||
f'_3 &= f'_1 \oplus x_4 = \neg x_2 \oplus x_4, \nonumber \\
|
||
f'_4 &= f'_3 = \neg x_2 \oplus x_4.
|
||
\label{eq:seq_sync}
|
||
\end{align}
|
||
|
||
This means that a sequential scheme can always be expressed as an equivalent synchronous scheme with a different set of update functions, as shown in \cref{eq:seq_sync}. Furthermore, if the side-effects from the sequential scheme are desired, the resulting synchronous function set is generally larger and more complex.
|
||
|
||
An extension of the sequential scheme is the \textit{block-sequential scheme}. This allows the modeler to divide the nodes into groups, called blocks, that run synchronously, while the blocks execute in sequence. This allows for further fine-tuning of the behavior and can simplify the modeling of realistic systems. The block-sequential scheme can also be converted to a synchronous scheme, thus producing the same behavior as previously described \cite{goles2010block}.
|
||
|
||
An important practical consideration is that for a network with $n$ nodes, there are $n!$ possible sequential orderings, and different orderings can produce different state graphs and attractors. This makes the choice of sequence both a useful modeling tool and a potential source of ambiguity, since the biologically correct ordering is often not known in advance \cite{goles2010block}. The block-sequential scheme partially addresses this by only requiring a partition of nodes into blocks and an ordering of those blocks, rather than a complete linear ordering over all nodes. This reduction in the number of free parameters for the sequence makes it more tractable to systematically explore how update ordering affects the dynamics, while still capturing meaningful temporal structure between different groups of regulatory events \cite{schwab2020concepts, goles2010block}.
|
||
|
||
|
||
|
||
\subsection{Probabilistic scheme}
|
||
The \textit{probabilistic scheme} introduces a qualitatively different kind of update rule. Instead of a single deterministic update function per node, each node is assigned a set of possible update functions, each with an associated probability. Upon updating a node, one function from this set is selected at random according to a predefined distribution, making the dynamics of the network stochastic rather than deterministic. This is in contrast to the synchronous, sequential, and asynchronous deterministic schemes, where the outcome of each update step is fully determined by the current state of the network.
|
||
|
||
\begin{figure}[h]
|
||
\centering
|
||
\begin{align}
|
||
f_1 &= \neg x_2 \nonumber \\
|
||
f_2 &= x_1 \nonumber \\
|
||
f_3 &= x_1 \oplus x_4 \nonumber \\
|
||
f_4 &= x_3 \quad (p = 0.5) \nonumber \\
|
||
f_{4,\text{switch}} &= \neg x_3 \quad (p = 0.5)
|
||
\end{align}
|
||
\caption{Update functions of the boolean network from \cref{fig:bn_example}, extended with the probabilistic alternative $f_{4,\text{switch}}$ for node $x_4$. Both functions for $x_4$ are selected with equal probability at every update step.}
|
||
\label{fig:bn_prob_example}
|
||
\end{figure}
|
||
|
||
An example of how this can drastically change the outcome is shown in \cref{fig:bn_prob_example}, where a second function is added to node $x_4$ from the network in \cref{fig:bn_example}. Let \mbox{$f_{4,\text{switch}} = \neg f_4 = \neg x_3$} with an equal probability distribution. This simple addition means that, on average, every second update the state switches from one cycle to the other. Thus there are no longer two individual cycles. Any initial state will eventually reach all possible states and will never fall into a repeating pattern.
|
||
|
||
More formally, a probabilistic boolean network assigns to each node $x_i$ a set of update functions $\{f_i^{(1)}, \ldots, f_i^{(k_i)}\}$ with corresponding probabilities $\{p_i^{(1)}, \ldots, p_i^{(k_i)}\}$ that sum to 1. At each step, one function per node is selected at random according to these probabilities. The resulting dynamics can be analyzed as a Markov chain over the $2^n$ possible states, where the long-term behavior is described by a stationary distribution over states rather than a single fixed attractor \cite{schwab2020concepts}. In other words, once sufficient noise is introduced, the system can escape what would otherwise be deterministic attractors, and over time it explores a much broader region of the state space than any single deterministic trajectory would cover.
|
||
|
||
This connection to GRN modeling is particularly relevant for oscillatory networks, such as the Repressilator, discussed in detail in \cref{sec:relevance_grn}. Under deterministic update schemes, the Repressilator produces a clean periodic oscillation. In real biological cells, however, gene expression is inherently noisy: a gene that should be repressed may occasionally still produce a small amount of transcript due to stochastic effects, such as transcriptional bursting or low molecule counts. By introducing a small probability for an alternative update function, this noise can be captured in the model. The result is an irregular oscillation whose period varies from cycle to cycle, which is considerably closer to the gene expression dynamics observed in living cells than the perfectly regular output of a deterministic scheme \cite{schwab2020concepts}.
|
||
|
||
\subsection{Asynchronous scheme}
|
||
While synchronous, sequential and probabilistic schemes update all the nodes in one time step, the \textit{asynchronous scheme} only updates one node per time step. There are two main variants. In asynchronous deterministic update, a fixed predetermined sequence specifies which single node is updated at each time step. This differs from the sequential scheme in a fundamental way: in the sequential scheme, the entire sequence is executed within one time step, updating all nodes once; in asynchronous deterministic update, each element of the sequence constitutes a separate time step that updates exactly one node. The same node can therefore appear at multiple positions across successive time steps, giving it a higher effective update frequency and allowing the modeler to encode that certain regulatory processes occur faster than others. In asynchronous random update, the node to be updated at each step is chosen randomly, with the simplest case being a uniform selection over all nodes. While the probabilistic scheme introduced stochasticity at the level of function selection, asynchronous random update introduces stochasticity at the level of node selection: there is no predetermined order, and from any given state, multiple different transitions are possible depending on which node happens to be selected.
|
||
|
||
During early stages of boolean network research, it was believed that the asynchronous update would lead to more realistic models of biochemical systems \cite{schwab2020concepts}. However, as some studies have shown, asynchronous and synchronous schemes can lead to the same meaningful behavior for certain networks, and the choice between them often comes down to practical considerations. A concrete limitation of the asynchronous approach is its computational cost: since each time step updates only one node, a single full round over all $n$ nodes requires $n$ sequential steps. Assuming each step takes seconds to minutes, this could add up to several days for large networks \cite{schwab2020concepts}.
|
||
|
||
The intuition behind the belief that asynchronous update is more realistic is that biological processes rarely occur simultaneously: genes are transcribed and translated on different timescales, and regulatory events in one part of the network need not coincide with those elsewhere. Despite this motivation, studies have shown that for many practical GRN models the attractors that correspond to meaningful biological states tend to be preserved across update schemes. This suggests that the coarse-grained behavior of a network is often robust to the specific update schedule, provided the biological logic encoded in the update functions is correct \cite{schwab2020concepts}.
|
||
|
||
A key structural consequence of the random asynchronous variant is that, as in the probabilistic scheme, it introduces non-determinism into the state graph. Since the node to update is chosen at random, from any given state there are in general multiple possible successor states rather than a single deterministic one. This makes identifying attractors more complex than in the synchronous or sequential case, since a state can lead to different trajectories on different runs \cite{schwab2020concepts}.
|
||
|
||
More generally, cyclic attractors that arise in synchronous networks due to the simultaneous evaluation of all update functions are often absent under asynchronous dynamics. Because only one node is updated at a time, the global symmetry that produces such artificial cycles is broken, and the system instead settles into attractors that more faithfully reflect the underlying regulatory logic \cite{bornholdt2008boolean}. The practical consequence of this is discussed in detail using the repressilator as a case study in \cref{sec:relevance_grn}.
|
||
|
||
Furthermore, the random asynchronous scheme is closely related to the probabilistic scheme. Rather than randomizing which update function is applied to each node, it randomizes which node is updated at each step, while keeping the update functions themselves fixed.
|
||
|
||
|
||
\section{Relevance for Gene Regulatory Networks}
|
||
\label{sec:relevance_grn}
|
||
|
||
A gene regulatory network (GRN) is a system of interactions between genes, transcription factors and other regulatory molecules that together control gene expression in a cell. Since each gene can be treated as either active (expressed) or inactive (silenced), boolean networks are a natural fit for modeling GRNs. They have been applied to a variety of well-known GRNs, such as the cell-cycle network of \textit{Saccharomyces cerevisiae} or the segment polarity network of \textit{Drosophila melanogaster} \cite{helikar2011boolean, bornholdt2008boolean}. In these models, the attractors of the boolean network are interpreted as stable gene expression patterns corresponding to distinct cell types or functional states. A cell that has committed to a specific developmental fate, for example, would correspond to a fixed-point attractor in the GRN model, while transient oscillations in gene expression would appear as limit cycles.
|
||
|
||
A particularly instructive example for studying the effect of update schemes on GRN models is the \textit{repressilator}: a synthetic regulatory circuit in which three genes each repress the next in a cyclic fashion \cite{bornholdt2008boolean}. As shown in \cref{fig:bn_repr}, the network has update functions of the form $f_i = \neg x_{i-1}$ (indices modulo 3). Despite having only three nodes and eight possible states, the Repressilator shows a strikingly different attractor structure depending on which update scheme is used.
|
||
|
||
\begin{figure}
|
||
\centering
|
||
\includegraphics[height=6cm]{bn_repressilator.png}
|
||
\caption{The GRN Repressilator modeled as a boolean network and the update table using the synchronous scheme.}
|
||
\label{fig:bn_repr}
|
||
\end{figure}
|
||
|
||
\begin{figure}
|
||
\centering
|
||
\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt
|
||
|
||
\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
|
||
%uncomment if require: \path (0,273); %set diagram left start at 0, and has height of 273
|
||
|
||
%Straight Lines [id:da6732952894657575]
|
||
\draw (117.8,28.2) -- (144.8,28.2) ;
|
||
\draw [shift={(147.8,28.2)}, rotate = 180] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da46162142180164867]
|
||
\draw (162.8,38.2) -- (162.8,55.2) ;
|
||
\draw [shift={(162.8,58.2)}, rotate = 270] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da8411742710774129]
|
||
\draw (162.8,78.2) -- (162.8,95.2) ;
|
||
\draw [shift={(162.8,98.2)}, rotate = 270] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da02385519127417357]
|
||
\draw (147.8,108.2) -- (120.8,108.2) ;
|
||
\draw [shift={(117.8,108.2)}, rotate = 360] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da9369563609902064]
|
||
\draw (102.8,58.2) -- (102.8,41.2) ;
|
||
\draw [shift={(102.8,38.2)}, rotate = 90] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da2026651869232049]
|
||
\draw (102.8,98.2) -- (102.8,81.2) ;
|
||
\draw [shift={(102.8,78.2)}, rotate = 90] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da9759950912927599]
|
||
\draw (218.8,78.2) -- (218.8,61.2) ;
|
||
\draw [shift={(218.8,58.2)}, rotate = 90] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da42118359777387304]
|
||
\draw (227.8,58.2) -- (227.8,75.2) ;
|
||
\draw [shift={(227.8,78.2)}, rotate = 270] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da6189979487429944]
|
||
\draw (87,201) -- (114,201) ;
|
||
\draw [shift={(117,201)}, rotate = 180] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da24388249395288197]
|
||
\draw (132,171) -- (132,188) ;
|
||
\draw [shift={(132,191)}, rotate = 270] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da5377128840336186]
|
||
\draw (192,171) -- (192,188) ;
|
||
\draw [shift={(192,191)}, rotate = 270] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da7172765108275505]
|
||
\draw (237,201) -- (210,201) ;
|
||
\draw [shift={(207,201)}, rotate = 360] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da7736169235673199]
|
||
\draw (147,197) -- (174,197) ;
|
||
\draw [shift={(177,197)}, rotate = 180] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da6598487496376828]
|
||
\draw (132,231) -- (132,214) ;
|
||
\draw [shift={(132,211)}, rotate = 90] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da5213149848331206]
|
||
\draw (192,231) -- (192,214) ;
|
||
\draw [shift={(192,211)}, rotate = 90] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
%Straight Lines [id:da35822810959220885]
|
||
\draw (177,206) -- (150,206) ;
|
||
\draw [shift={(147,206)}, rotate = 360] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
|
||
|
||
% Text Node
|
||
\draw (90.8,20.2) node [anchor=north west][inner sep=0.75pt] [align=left] {001};
|
||
% Text Node
|
||
\draw (148.8,20.2) node [anchor=north west][inner sep=0.75pt] [align=left] {011};
|
||
% Text Node
|
||
\draw (150.8,100.2) node [anchor=north west][inner sep=0.75pt] [align=left] {110};
|
||
% Text Node
|
||
\draw (90.8,60.2) node [anchor=north west][inner sep=0.75pt] [align=left] {101};
|
||
% Text Node
|
||
\draw (90.8,100.2) node [anchor=north west][inner sep=0.75pt] [align=left] {100};
|
||
% Text Node
|
||
\draw (150.8,60.2) node [anchor=north west][inner sep=0.75pt] [align=left] {010};
|
||
% Text Node
|
||
\draw (208.8,40.2) node [anchor=north west][inner sep=0.75pt] [align=left] {000};
|
||
% Text Node
|
||
\draw (208.8,80.2) node [anchor=north west][inner sep=0.75pt] [align=left] {111};
|
||
% Text Node
|
||
\draw (178,233) node [anchor=north west][inner sep=0.75pt] [align=left] {001};
|
||
% Text Node
|
||
\draw (178,153) node [anchor=north west][inner sep=0.75pt] [align=left] {011};
|
||
% Text Node
|
||
\draw (118,153) node [anchor=north west][inner sep=0.75pt] [align=left] {110};
|
||
% Text Node
|
||
\draw (118,193) node [anchor=north west][inner sep=0.75pt] [align=left] {101};
|
||
% Text Node
|
||
\draw (118,233) node [anchor=north west][inner sep=0.75pt] [align=left] {100};
|
||
% Text Node
|
||
\draw (178,193) node [anchor=north west][inner sep=0.75pt] [align=left] {010};
|
||
% Text Node
|
||
\draw (58,193) node [anchor=north west][inner sep=0.75pt] [align=left] {000};
|
||
% Text Node
|
||
\draw (238,193) node [anchor=north west][inner sep=0.75pt] [align=left] {111};
|
||
|
||
\end{tikzpicture}
|
||
|
||
\caption{State graphs of the repressilator as boolean network: The upper two cycles are the result of the use of synchronous scheme; the lower graph is the result of sequential scheme with sequence $(x_1, x_2,x_3)$.}
|
||
\label{fig:bn_repr_state_graph}
|
||
\end{figure}
|
||
|
||
|
||
\begin{figure*}[h]
|
||
\centering
|
||
\subfloat[Asynchronous update scheme\label{fig:repr_async_stationary}]{%
|
||
\includegraphics[width=0.48\textwidth]{repressilator_async.pdf}}
|
||
\hfill
|
||
\subfloat[Probabilistic update scheme\label{fig:repr_prob_stationary}]{
|
||
\includegraphics[width=0.48\textwidth]{repressilator_prob025.pdf}}
|
||
\caption{
|
||
Comparison between theoretical stationary probability distribution and empirical data from a test run using asynchronous random (\cref{fig:repr_async_stationary}) and probabilistic (\cref{fig:repr_prob_stationary}) with one million simulated time steps, both starting from initial state $x=000$.
|
||
}
|
||
\end{figure*}
|
||
|
||
Under the synchronous scheme, the network has two attractors, shown in the upper part of \cref{fig:bn_repr_state_graph}. The first is a period-6 oscillation cycle through the states $100 \rightarrow 101 \rightarrow 001 \rightarrow 011 \rightarrow 010 \rightarrow 110 \rightarrow 100$, which corresponds to the alternating gene expression observed in experimental implementations of the repressilator. The second is an artificial period-2 cycle alternating between $000$ (all genes off) and $111$ (all genes on). This second attractor has no biological basis: it arises purely because updating all three repressors simultaneously maps $000$ to $111$ and back, a dynamic that would not occur if the genes were updated at slightly different times.
|
||
|
||
Under random asynchronous update, the picture changes. From state $000$, any node selected for updating will have $f_i = \neg 0 = 1$, meaning the network is immediately pushed into one of the oscillatory states regardless of which node is chosen. The same applies to $111$. Neither state can sustain itself, so they become transient states and the artificial 2-cycle disappears entirely. Only the biologically meaningful oscillation remains as an attractor. This confirms that the period-2 cycle in the synchronous case was indeed an artifact of simultaneous updating \cite{bornholdt2008boolean}, and it illustrates why asynchronous update is often considered more biologically faithful for oscillatory GRN models.
|
||
|
||
Under a sequential scheme with sequence $(x_1, x_2, x_3)$, the attractor structure changes even more dramatically, as shown in the lower part of \cref{fig:bn_repr_state_graph}. Tracing through the state transitions reveals that the only attractor is now a period-2 cycle between states $010$ and $101$, a subset of the states from the synchronous 6-cycle. The synchronous 6-cycle itself no longer exists as an attractor, and all eight states converge to this single 2-cycle. This is a clear example that even among deterministic schemes, changing the update order can completely alter the attractor landscape.
|
||
|
||
|
||
|
||
Under a probabilistic scheme, the clean periodic oscillation gives way to an irregular, noisy one. Introducing a small probability for an alternative update function on any of the three genes, modeling the stochastic fluctuations that occur in real gene expression, means the network occasionally deviates from the regular cycle. The long-term behavior is no longer a fixed attractor but a stationary distribution over states, reflecting how much time the system spends in each expression configuration on average \cite{schwab2020concepts}. This type of model is particularly useful for understanding phenotypic variability within a population of genetically identical cells.
|
||
|
||
The repressilator example illustrates a key point for GRN modeling in general: the choice of update scheme is not a neutral decision. It directly affects which attractors exist, which states are biologically accessible, and how realistically the model captures the noise and timing characteristics of the underlying system. For large-scale GRNs where the biological timing of regulatory events is not known, synchronous update remains the practical standard due to its computational simplicity and the ease of attractor analysis. Sequential or block-sequential update is appropriate when relative timing information is available. Asynchronous update is biologically motivated but becomes slow for large networks, and probabilistic update is the method of choice when transcriptional noise is a central modeling goal.
|
||
|
||
|
||
The long-term behavior of stochastic update schemes can be analyzed formally through the theory of Markov chains. Both the random asynchronous and the probabilistic synchronous schemes define a stochastic process over the $2^n$ possible states, where the probability of moving to the next state depends only on the current one. This process is fully captured by a \textit{transition matrix} $P \in [0,1]^{2^n \times 2^n}$, where the entry $P_{ij}$ gives the probability of transitioning from state $i$ to state $j$ in one time step. Each row of $P$ sums to one, reflecting that the network must always move to some state.
|
||
|
||
The stationary distribution $\pi$ is a probability vector over the $2^n$ states satisfying
|
||
\begin{equation}
|
||
\label{eq:stationary}
|
||
\pi P = \pi,
|
||
\end{equation}
|
||
meaning $\pi$ is a left eigenvector of $P$ with eigenvalue 1. Intuitively, $\pi(x)$ gives the long-run fraction of time the network spends in state $x$: transient states receive $\pi(x) = 0$, while recurrent states satisfy $\pi(x) > 0$ and are revisited indefinitely. For an irreducible Markov chain, a unique $\pi$ satisfying \cref{eq:stationary} always exists. Comparing $\pi$ against empirical visit frequencies from a long simulation then provides a practical validation of the model.
|
||
|
||
Under random asynchronous update of the repressilator, the states $000$ and $111$ are transient: from either state, every possible node selection immediately moves the network away, so once left they are never revisited. No stationary distribution can assign positive probability to a transient state, hence $\pi(000) = \pi(111) = 0$. The remaining six oscillatory states $\{100, 101, 001, 011, 010, 110\}$ form a single irreducible recurrent class. Since the update rule selects each of the three nodes with equal probability $\frac{1}{3}$, the transition matrix restricted to this class is symmetric, and the unique solution to \cref{eq:stationary} is the uniform distribution $\pi(x) = \frac{1}{6}$ for each of the six states. \Cref{fig:repr_async_stationary} shows that a long simulation run closely matches this theoretical result.
|
||
|
||
Under the probabilistic synchronous scheme, the analysis differs. When a per-node bit-flip probability $p \neq 0$ is introduced alongside the standard repression function, the resulting transition matrix $P$ is doubly stochastic: not only does every row sum up to one, but every column does as well. For any doubly stochastic matrix over a finite irreducible Markov chain, the uniform distribution is the unique solution to \cref{eq:stationary}, giving $\pi(x) = \frac{1}{8}$ for all eight states in the long run, including $000$ and $111$, which carry zero probability under the asynchronous scheme. \Cref{fig:repr_prob_stationary} confirms this result empirically, illustrating how the two stochastic schemes produce qualitatively different long-term behavior despite both introducing randomness.
|
||
|
||
\section{Conclusion}
|
||
This paper gave an overview of four update schemes for boolean networks and analyzed how they affect the dynamics of a model. The synchronous scheme, where all nodes update simultaneously, produces fully deterministic and easily enumerable dynamics, making it the most widely used approach in practice despite its biological simplifications. Sequential and block-sequential schemes allow for a more realistic encoding of temporal ordering between regulatory events while retaining determinism. The probabilistic scheme introduces stochastic variation at the level of the update functions, capturing noise and fluctuations in the system. The asynchronous scheme updates one node at a time and, in its random variant, introduces non-determinism at the level of node selection rather than function selection.
|
||
|
||
The repressilator example from \cref{sec:relevance_grn} makes the practical stakes of this choice concrete. Even in a network with only three nodes, as illustrated in \cref{fig:bn_repr_state_graph}, the synchronous scheme produces a spurious 2-cycle between $000$ and $111$ alongside the biologically relevant 6-cycle. The asynchronous scheme eliminates this artifact. The sequential scheme with sequence $(x_1, x_2, x_3)$ replaces the 6-cycle with an entirely different 2-cycle through $010 \leftrightarrow 101$. The probabilistic scheme turns the regular oscillation into a noisy, variable one. The update scheme is therefore not just a computational choice; it determines which attractors the model has and what biological conclusions can be drawn from them.
|
||
|
||
The question of which scheme best captures the biology of a given system remains an active area of research. A notable recent contribution is the introduction of Most Permissive Boolean Networks \cite{pauleve2020reconciling}, a new update semantics that generalizes both synchronous and asynchronous approaches and carries a formal guarantee that no behavior achievable by a compatible quantitative model is missed. Unlike standard asynchronous update, the most permissive semantics also avoids the state-space explosion that makes large-scale asynchronous analysis intractable, enabling attractor analysis of genome-scale regulatory networks. On the tooling side, software packages such as BoolNet \cite{mussel2010boolnet} and GINsim \cite{naldi2018colomoto} bring multiple update schemes and attractor analysis algorithms to a broader research community.
|
||
|
||
Open questions include how to choose a biologically grounded update scheme when experimental timing data is sparse \cite{schwab2020concepts, aracena2009robustness}, how to parameterize probabilistic models from single-cell RNA sequencing data \cite{schwab2020concepts}, and how to efficiently compute attractor landscapes in asynchronous networks with thousands of nodes \cite{pauleve2020reconciling}. Boolean networks, despite their simplicity, remain a powerful framework for understanding the dynamical logic of gene regulation, and the choice of update scheme is central to using them well.
|
||
|
||
|
||
|
||
|
||
|
||
|
||
% The list of references is provided as `references.bib`
|
||
\bibliographystyle{unsrt}
|
||
\bibliography{IEEEabrv,references}
|
||
|
||
\end{document} |