Boolean network
Encyclopedia
A Boolean network consists of a set of Boolean variables whose state is determined by other variables in the network. They are a particular case of discrete dynamical network
s, where time and states are discrete, i.e. they have a bijection
onto an integer series. Boolean and elementary cellular automata are particular cases of Boolean networks, where the state of a variable is determined by its spatial neighbors. In a random boolean network the connections are wired randomly and the output of nodes are determined by randomly generated logic functions.
Random Boolean networks (RBNs) are known as NK networks or Kauffman networks. An RBN is a system of N binary-state nodes (representing genes) with K inputs to each node representing regulatory mechanisms. The two states (on/off) represent respectively, the status of a gene being active or inactive. The variable K is typically held constant, but it can also be varied across all genes, making it a set of integers instead of a single integer. In the simplest case each gene is assigned, at random, K regulatory inputs from among the N genes, and one of the possible Boolean functions of K inputs. This gives a random sample of the possible ensembles of the NK networks. The state of a network at any point in time is given by the current states of all N genes. Thus the state space of any such network is 2N.
Simulation of RBNs is done in discrete time steps. The state of a node at time t+1 is computed by applying the boolean function associated with the node to the state of its input nodes at time t. The behavior of specific RBNs and generalized classes of them has been the subject of much of Kauffman's (and others) research.
. If the attractor has only a single state it is called a point attractor, and if the attractor consists of more than one state it is called a cycle attractor. The set of states that lead to an attractor is called the basin of the attractor. States with no incoming connections are called garden-of-Eden states and the dynamics of the network flow from these states towards attractors. The time it takes to reach an attractor is called transient time. (Gershenson 2004)
Deterministic asynchronous RBNs (DARBNs) were introduced by Gershenson as a way to have RBNs that do not have asynchronous updating but still are deterministic. In DARBNs each node has two randomly generated parameters Pi and Qi (Pi, Qi ∈ ℕ, Pi > Qi). These parameters remain fixed. A node i will be updated when t ≡ Qi (mod Pi) where t is the time step. If more than one node is to be updated at a time step the nodes are updated in a pre-defined order, e.g. from lowest to highest i. Another way to do this is to synchronously update all nodes that fulfill the updating condition. The latter scheme is called deterministic semi-synchronous or deterministic generalized asynchronous RBNs (DGARBNs) (Gershenson, 2004).
RBNs where one or more nodes are selected for updating at each time step and the selected nodes are then synchronously updated are called generalized asynchronous RBNs (GARBNs). GARBNs are semi-synchronous, but non-deterministic (Gershenson, 2002).
Sequential dynamical system
Sequential dynamical systems are a class of graph dynamical systems. They are discrete dynamical systems which generalize many aspects of for example classical cellular automata, and they provide a framework for studying asynchronous processes over graphs...
s, where time and states are discrete, i.e. they have a bijection
Bijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
onto an integer series. Boolean and elementary cellular automata are particular cases of Boolean networks, where the state of a variable is determined by its spatial neighbors. In a random boolean network the connections are wired randomly and the output of nodes are determined by randomly generated logic functions.
Classical model
The first Boolean networks were proposed by Stuart A. Kauffman in 1969, as random models of genetic regulatory networks (Kauffman 1969, 1993).Random Boolean networks (RBNs) are known as NK networks or Kauffman networks. An RBN is a system of N binary-state nodes (representing genes) with K inputs to each node representing regulatory mechanisms. The two states (on/off) represent respectively, the status of a gene being active or inactive. The variable K is typically held constant, but it can also be varied across all genes, making it a set of integers instead of a single integer. In the simplest case each gene is assigned, at random, K regulatory inputs from among the N genes, and one of the possible Boolean functions of K inputs. This gives a random sample of the possible ensembles of the NK networks. The state of a network at any point in time is given by the current states of all N genes. Thus the state space of any such network is 2N.
Simulation of RBNs is done in discrete time steps. The state of a node at time t+1 is computed by applying the boolean function associated with the node to the state of its input nodes at time t. The behavior of specific RBNs and generalized classes of them has been the subject of much of Kauffman's (and others) research.
Attractors
A Boolean network has 2N possible states. Sooner or later it will reach a previously visited state, and thus, since the dynamics are deterministic, fall into an attractorAttractor
An attractor is a set towards which a dynamical system evolves over time. That is, points that get close enough to the attractor remain close even if slightly disturbed...
. If the attractor has only a single state it is called a point attractor, and if the attractor consists of more than one state it is called a cycle attractor. The set of states that lead to an attractor is called the basin of the attractor. States with no incoming connections are called garden-of-Eden states and the dynamics of the network flow from these states towards attractors. The time it takes to reach an attractor is called transient time. (Gershenson 2004)
Updating Schemes
Classical RBNs (CRBNs) use a synchronous updating scheme and a criticism of CRBNs as models of genetic regulatory networks is that genes do not change their states all at the same moment. Harvey and Bossomaier introduced this criticism and defined asynchronous RBNs (ARBNs) where a random node is selected at each time step and updated (Harvey and Bossomaier, 1997). Since a random node is updated ARBNs are non-deterministic and does not have the cycle attractors found in CRBNs (Gershenson, 2004).Deterministic asynchronous RBNs (DARBNs) were introduced by Gershenson as a way to have RBNs that do not have asynchronous updating but still are deterministic. In DARBNs each node has two randomly generated parameters Pi and Qi (Pi, Qi ∈ ℕ, Pi > Qi). These parameters remain fixed. A node i will be updated when t ≡ Qi (mod Pi) where t is the time step. If more than one node is to be updated at a time step the nodes are updated in a pre-defined order, e.g. from lowest to highest i. Another way to do this is to synchronously update all nodes that fulfill the updating condition. The latter scheme is called deterministic semi-synchronous or deterministic generalized asynchronous RBNs (DGARBNs) (Gershenson, 2004).
RBNs where one or more nodes are selected for updating at each time step and the selected nodes are then synchronously updated are called generalized asynchronous RBNs (GARBNs). GARBNs are semi-synchronous, but non-deterministic (Gershenson, 2002).