Random Boolean Networks
The aim of the assignment is to give one an appreciation of (a) the
power of simple computational models in giving us a plausible explanation
of biological phenomena and (b) how automata models can be used to
understand how genes switching each other on and off can result in
different cellular phenotypes.
For this we look at Random Boolean Networks (also known as Kauffman automata or NK-Boolean Neworks). Formally, these are defined by a network comprising N nodes, the state of each node i at a given time t (time evolving in discrete steps, i.e., t=1,2,3, etc) being given by a Boolean variable s_i (t), i.e., each s_i can take one of two values, 0 or 1 (say). Additionally, each node receives inputs from K other nodes (where K can range between 0 - i.e., all nodes are isolated - to N-1 - i.e., the network is completely connected). In the usual setting, the set of K nodes from which a given node i will receive connections is chosen randomly from the N-1 available nodes.
Each node at any given time t decides which of the two states it will adopt by looking at the states of the nodes it is receiving inputs from. As each of its K neighbors can be either in 0 or 1 state, this means that the total number of possible input state combinations seen by node i is 2^K. The dynamical rule governing the response of the node has to say what its state should be for each input state combination - i.e. assign either a 0 or 1 to each of the 2^K combinations. Thus, there are a possible 2^(2^K) such rules - and each node can randomly choose any one of them - but once assigned initially, this is the rule they will use throughout the simulation (quenched condition).
One can now start a simulation by starting with a random initial state
(randomly assigning 0s and 1s to the N nodes) and then looking at the time
evolution of the system state S(t)={s_1(t),s_2(t), ..., s_N(t)}.
Sometimes,
the system will quickly settle down to a fixed point attrator, i.e., after
a transient period, we find that the same system state is repeated over and
over again, viz., S(T)=S(T+1)=S(T+2)=...
At other times, the system state exhibits periodic cycles where S cycles
between a number of states over and over again. Given that the total number
of possible states that the system can adopt is 2^N it is of course true
that strictly speaking that the system can only exhibit periodic cycles.
However, if N is even moderately (e.g., N=20) the number of possible states
is so large, that the periodicity of a cycle may not be apparent.
Start with N=10 and then try for larger N
(a) Show that for K=1 the system quickly settles down to fixed points
(b) Show that for K=2 the system usually settles to fixed points or short cycles. Estimate the number of attractors (the state the system settles down to after transients) and the typical size of the basins of attraction for these.
(c) For K=3 show the system does not seem to be settle down to short cycles or fixed points. Estimate the number of attractors and basin sizes for this case too.
It has been suggested that there is a phase transition that occurs between K=2 and K=3. Kauffman originally proposed this model as the mechanism by which the genes within a cell switch each other on or off to create a particular cellular phenotype. Thus, the number of attractors for the network will correspond to the different cellular phenotype that the gene network can produce.
(d) Can one derive a theoretical expression for the number of attractors for K=2 and K=3 cases ? You can research on the web.
(e) The behavior of the system for K=3 or higher is often called chaotic.
But how will you characterize this ? Strictly speaking, you have to show
that small differences in initial states will result in large differences
in the states achieved after some time. How will you measure this ? Come up
with plausible measures for this (you can look at the idea of boolean
derivative of Vichniac [Physica D Vol 45, 1990, pp 63-74 or Peter
Grassberger's idea of damage spreading exponents, for example).