Biomedical Engineering Reference
In-Depth Information
such networks is surprisingly complex and suggestive, and is a subject of active
research.
Boolean functions describing the switching of system variables between
binary values can be thought of as an approximation of a map corresponding to a
very complicated set of differential equations for the underlying physical proc-
esses. These functions, which must produce a binary output given some set of
binary inputs, are strongly nonlinear. Since the system variables can only have
two distinct values, the notion of a state corresponding to the sum of two other
distinct states is not even well defined. Even in this extreme situation, however,
the concepts of nonlinear dynamics provide a useful framework for discussing
network behavior. Here we present a bare-bones description of this framework
as an illustration of how the concepts discussed above enter the discussion.
A Boolean network is a collection of
N
logic gates, each having some fixed
number of inputs,
K
i
, and one binary output, T
i
, where
i
= 1, ...
N
indexes the
gates. The inputs to a gate are a subset of size
K
i
of the outputs from all of the
gates. Each gate is also characterized by a truth table
T
i
that determines T
i
as a
function of the inputs. On each (discrete) time step, all of the gates apply their
truth tables to their inputs and update their outputs accordingly. Each
T
i
is as-
sumed to be selected randomly from a weighted distribution of all the possible
truth tables with
K
i
inputs. To complete the definition of the model, one must
specify the
K
i
's and the procedure for choosing which T
i
's act as inputs to a given
gate. The best studied cases are networks in which all
K
i
are the same and the
choice of which gates are inputs to any given gate is completely random. The
result is a "random Boolean network" (RBN), sometimes referred to as a
"Kauffman net."
The system variables in an RBN are simply the values of the outputs of the
gates. The parameters of a particular model network are the choices of which
outputs serve as inputs to each gate and which Boolean function is assigned to
each gate. Instead of specifying all of these parameters explicitly, however, we
specify a random procedure for choosing them. The number of inputs to each
gate and the probabilities assigned to each of the different truth tables are taken
as the parameters of the model. Note that when we discuss the behavior of the
model at a certain set of parameter values, we are now talking about the average
or typical behavior of a whole class of individual RBNs—those constructed ac-
cording to a specified probabilistic procedure—rather than the detailed behavior
of one specific dynamical system. (For more on probabilistic procedures for
constructing the wiring diagrams of biological networks, see this volume, Part
II, chapter 4, by Wuchty, Ravasz, and Barabási.)
In an RBN, the trajectory associated with the differential equations becomes
a sequence of vertices in a state space that is a discrete set of points. If there are
N
gates in the network, each point in state space is an
N
-dimensional vector.
Now because the number of distinct states is finite, the total number of possible
states being 2
N
, the sequence must eventually arrive at a point that has been vis-
