Transcript Tyler - Clarkson University

DYNAMICS OF RANDOM
BOOLEAN NETWORKS
James F. Lynch
Clarkson University
The Lac Operon (Jacob &
Monod)
Stuart Kauffman:
Cellular metabolism is controlled by a dynamic
network, where the activity of some genes and
molecules affects the activity of other
constituents of the network.
It is constructed from unreliable parts and is
subjected to mutations, yet it behaves in a
robust and reliable manner.
Is this order and stability the result of
natural selection?
Kauffman: not entirely. There is a statistical
tendency toward order and self-organization.
Natural selection acts on self-organizing
systems, rather than creating them.
Without an innate tendency toward order,
almost all mutations would be fatal.
MODELING CELLULAR
METABOLISM AS A BOOLEAN
NETWORK
• Gate ≡ Gene or other metabolic element
• State ≡ Active/Inactive (1 or 0)
• Inputs ≡ Regulators
fi
gate i
computes fi
inputs
to
gate i
DYNAMICS
At any time t  0,1,2,
Each gate is in state 0 or 1.
Then, each gate i
reads states of its inputs, say x i1 , x i2 , 
and
its state at time t  1 becomes f i x i1 , x i2 ,  .


STATE SPACE
State of network at time
states of all gates.
t is the vector of
transition
state
Limit Cycle
The limit cycle describes the long-term
behavior of the genomic network.
In a multicellular organism, it corresponds
to the cell type after differentiation.
Λ
Λ
Λ
┘
A BOOLEAN NETWORK
KAUFFMAN’S EXPERIMENTS
WITH RANDOM k, n NETWORKS
k  Number of inputs to each gate
n  Number of gates
For each gate:
2k
1. Choose its function from the 2 Boolean
functions of k arguments uniformly at
random (u.a.r)
2. Choose its k inputs u.a.r.
3. Choose its starting state u.a.r.
Run the network deterministically
CLASSIFICATION OF BEHAVIOR
Ordered:
1. Most gates stabilize (stop changing state)
quickly.
2. Most gates can be perturbed without
affecting the limit cycle entered.
3. Limit cycle is small.
Chaotic:
1. Many unstable gates.
2. Sensitivity to initial conditions.
3. Large limit cycle.
• Ordered behavior is characteristic of
genomic and metabolic networks: they
quickly settle down into periodic patterns of
activity that resist disturbance.
• Chaotic behavior is characteristic of many
non-biological complex systems: sensitivity
to initial conditions, long transients, and very
large limit cycles (strange attractors).
RESULTS OF KAUFFMAN’S
SIMULATIONS
• When k  3 , the network behaved chaotically.
• When k  2 , the network exhibited stable
behavior.
• Specifically, limit cycle sizes were 2 n when k  3
and n when k  2 .
• This is analogous to a phase transition in
dynamical systems.
Was the ordered behavior of 2, n networks
due to the high proportion of constant Boolean
functions?
A Boolean function is constant if it ignores its
inputs and always outputs the same value, i.e.,
f  x1 , x2   0 or f  x1 , x2   1
22
Two out of the 2  16 two argument Boolean
functions are constant, so about 1/8 of the
gates will be assigned constant Boolean
functions.
Kauffman also ran simulations of 2, n
networks without constant gates: for each
gate, choose its function from the 14 nonconstant Boolean functions of two arguments.
Simulations indicated that behavior was similar
to random 2, n Boolean networks that used all
16 Boolean functions of two arguments.
Can these results be taken as evidence that:
• Biological systems exist at the edge of
chaos?
• Self-organization occurs spontaneously in
living systems?
• Other researchers have made similar
claims:
– Bak (self-organized criticality)
– Langton
– Packard
– Wolfram
MATHEMATICS OF RANDOM
BOOLEAN NETWORKS
The behavior of random k, n networks when
k  1 or k  n was already known:
• 1, n networks consist of disjoint cycles of 1input gates (identity, negation, and constant
gates). They are very stable in all three
senses.
• n, n networks behave like random functions
n
2
on
elements. They are very unstable in all
three senses. Average state cycle size is
 n/ 2
2
8
MORE RECENT RESULTS
• We define a very general class of random
Boolean networks that includes the k, n
networks as special cases.
• We obtain partial results about the three
measures of order on networks in this class.
• Some of our results corroborate Kauffman’s
simulations, but some do not.
DEFINITION OF RANDOM
BOOLEAN NETWORK
• Let 1 , 2 ,be an ordering of all finite Boolean
functions.
• For each i , let p i be a probability, and let mi
be the number of arguments of  i .
• We need some symmetry conditions: pi  p j
whenever  i and  j are the same functions, but with
re-ordered arguments, or  i    j .

• Also
p
i 1
i
 1 and


i 1
pi m i  
2
(mean and variance of the number of arguments is
finite).
CONSTRUCTING A RANDOM
BOOLEAN NETWORK WITH
n GATES
For each gate j  1,  , n ,
1. Assign a Boolean function to j , where pi is
the probability that  i is assigned to j .
2. Choose the mi inputs to j uniformly at
random.
3. Choose the initial state of j uniformly at
random.
This kind of random Boolean network includes
as special cases:
• Kauffman’s random k, n networks
• Networks with classical random graph
topology (Erdős and Rényi) and edge
1
probability  cn
• Networks with power law degree distribution
c
 d , c  1 , or smallworld topology
DEFINITIONS
• A gate j is forced to y  0,1 in t steps if its
state at any time  t is y , regardless of the
initial state of the network.
• Specifically, let   x1 ,, xm  be the Boolean
function assigned to j .
• j is forced to y in 0 steps if  is the
constant function   x1 ,, xm   y .
• Recursively, j is forced to y in t  1 steps if,
letting j1 ,, jm be its inputs, there is a set
K  1,, m such that for every k  K , jk is
forced to y k in t steps, and for every x1 ,, xm
satisfying xk  yk for all k  K ,   x1 ,, xm   y.
For example:
Forced to 1 in t+1 steps
Λ
Forced to 1 in t steps
Note that j is forced in t steps implies j stabilizes
within t steps.
• Let j be a gate in a Boolean network with n

gates. Let x be the initial state of the
network, and t  0 . We say that j is t -weak

on input x if the state of the network at time t
is not affected by changing the state of j at
time 0.

• Note that j is t -weak on input x implies

that perturbing j on input x will not affect
the limit cycle.
• We will give estimates on the number of
gates that are forced in t steps and t –weak
gates, where t  Olog n , based on the
distribution p1 , p2 ,.
• In the cases where almost all gates are
forced in t steps and are t –weak, this
implies two forms of ordered behavior: most
gates will stabilize and most gates can be
perturbed without affecting the limit cycle,.
• In some cases we also have estimates on the
limit cycle size.
A PROPERTY OF BOOLEAN
FUNCTIONS
Let  be a Boolean function with m arguments.

Let x  x1 ,, xm be a sequence of m 0’s and
1’s.
For j  1,  , m we say that argument j affects


j
 on input x if   x    x  where x k  x kj when
k  j and x j  1  x jj .
EXAMPLES
• Argument 2 affects x1  x2 on input 0,1 but
not on input 1,1 .
• Argument 1 affects x1  x2 mod 2 on all
inputs.
m


x j affects  on input x
j 1
2m
Let     
   is the average number of arguments that
affect  on a random input.

Then
   pi  i 
i 1
is the average number of arguments that affect
a random Boolean function on a random input.
 IS A THRESHOLD FOR
FORCED AND WEAK GATES
There is a constant  determined by the
distribution p1 , p2 ,, such that
• If   1, then with high probability almost all
gates are forced in  log n steps and are
 log n -weak.
• If   1 , then with high probability there are
at least  n gates that are not forced in  log n
steps and at least  n gates that are not  log n
-weak, where   0 is a constant determined
by the distribution p1 , p2 ,.
APPLICATIONS TO
2, n NETWORKS
• When all 16 Boolean functions of two
arguments are equally likely,   1
 most gates stabilize and are weak.
• When only the 14 non-constant Boolean
functions of two arguments are used,   1
 instability and sensitivity to initial
conditions in the first  log n steps.
RESULTS ON LIMIT CYCLES IN
2, n NETWORKS
• When   1 , with high probability, the
limit cycle size is bounded by a
constant.
• But when   1 , with high probability,
the limit cycle is larger than any
polynomial in n.
COMPARISON TO KAUFFMAN’S
SIMULATIONS
• When all 16 2-argument Boolean functions are equally
likely,   1.
– Agreement regarding sensitivity to initial conditions and stable
gates.
– Disagreement over size of limit cycles: superpolynomial vs.
n .
• When only the 14 non-constant functions are used,   1 .
– Our results show disorder in the first  log n steps.
– But simulations behaved like the case with all 16 Boolean
functions.
– This is not necessarily disagreement: the network may settle
down into ordered behavior after  log n steps.
SOME PROOF IDEAS
I. FORCED GATES
• The in-neighborhood of radius  log n of
almost all gates is a tree.
AN IN-NEIGHBORHOOD OF RADIUS 3
• Let N be the  log n in-neighborhood of a
gate j . Assuming N is a tree, we extend the
notion of “affects” to gates in N :
• Gate j affects itself if its Boolean function is
not a constant.
• Recursively, assume the notion of “affects”
has been extended to all gates in N that are
a distance t from j . Let k be such a gate,
  x1 ,, xm  be its Boolean function, and
k1 , , k m its inputs. For i  1,  , m , ki affects j
if its corresponding argument x i affects  .
• Still assuming N is a tree, j is forced in
 log n steps  there does not exist a gate
in N that affects j .
• The recursive definition of “affects” defines
a branching process:
– For each gate in N that affects j , its children are
its inputs that affect j .
• The expected number of children is  .
• By branching process theory:
– If   1 then with probability 1 the process
becomes extinct
 with high probability, almost all gates are not
affected by any gate in their  log n
in-neighborhood
 they are forced in  log n steps.
– If   1 then with probability 1 the process will not
become extinct
 with high probability, approximately  n
gates are affected by some gate in their  log n
in-neighborhood
 they are not forced in  log n steps.
II. WEAK GATES
• The out-neighborhood of radius  log n of
almost all gates is a tree.
• This means that the effect of most
perturbations is approximated by a branching
process.
• Assume that the  log n out-neighborhood
of a gate is a tree.
• The probability that perturbing a gate in this
out-neighborhood affects k of its children is
k
•
k!
e

 the expected number of children affected
by the gate is
.
• Again by branching process theory:
– If   1 then with probability 1 the process
becomes extinct
 with high probability, for almost all gates, the
effect of the perturbation disappears.
– If   1 then with probability   0 the process
will not become extinct
 with high probability, for approximately  n
gates, the effect of a perturbation will persist for at
least  log n steps.
OPEN PROBLEMS
• Do many perturbations of the initial state cause
permanent changes in the state when   1 ?
• What is the limit cycle size when   1?
• Networks with external inputs and outputs:
– What kinds of functions can be computed?
– Is   1 a region where complex functions are
computed?
• More general kinds of networks:
–
–
–
–
Real-valued states of gates
Asynchronous dynamics
Continuous dynamics
Probabilistic dynamics
SUMMARY
• Simulations of complex systems may not be
reliable. If possible, they should be verified
with analytic results.
• Dynamical systems approach needs to be
applied to more realistic, detailed models.
– In particular, the notion of “complexity at the edge
of chaos” should be tested against specific
systems, such as models of self-assembling
membranes or other cellular organelles.
• More generally, we’ve presented a form of
Individual-Based Model, where the
individuals are gates, the population is
described by the functions of the gates and
their connections, and we are interested in
statistical properties of its dynamics.
• Individual-Based Models are now being used
to model populations at all scales in biology:
– Bray & Firth: StochSim stochastic simulator of
molecular reactions
– Romey: fish & whirligigs
• Can a theory of the dynamics of IndividualBased Models be developed?