Accepted:
00/00/1994
| |
/vol01/green01/ | © Copyright 1994 | |||
| Volume 1 | Received: Accepted: |
00/00/1994 00/00/1994 |
|||
David G. Green
School of Environmental and Information Science
Charles Sturt University
PO Box 789, Albury, 2640, Australia
Email: dgreen@csu.edu.au
In no area of science is the saying "the whole is greater than the sum of its parts" [1] more evident than in biology. The mere term "organism" expresses the fundamental role that interactions, self-organization and emergent behavior play in all biological systems. How, for instance, do millions of almost identical cells organize themselves into living creatures? How does a single egg cell grow into a complete human being? Questions such as these remain some of the deepest mysteries, and greatest challenges, of modern science.
Biological organization arises from two sources: constraints from without, and interactions within a system. External constraints, such as biochemical gradients limiting cell activity or climate limiting species distributions, have been intensively studied and are relatively well understood. In contrast, we know relatively little about the ways in which global behavior emerges from local interactions within a system.
The most basic question we can ask about biological interactions is whether they occur at all. That is, are the elements of the system connected? In this discussion I show that patterns of connectivity, and changes in them, influence many biological processes.
Biological systems on many different scales exhibit emergent behaviour. Let us begin with some examples to show how connectivity, of different kinds and on different scales, can affect the overall behavior of a system. In each case, simulation results serve to demonstrate the effect of changes in connectivity.
A classic problem in developmental biology is the "French Flag Problem" [2]. That is, how do arrays of dividing cells synchronize their behavior to produce sharp boundaries between (say) bands of skin colour, or body segments? Models that treat cells as context-free automata [2] can generate realistic banding patterns. However, these models assume arbitrary changes in internal cell states for which no physical meaning has ever been demonstrated. Furthermore, experimental studies show that inter-cellular interactions do play a role in cell differentiation [5] [4] [3]. That is, the process is context-sensitive. Moreover it is often associated with biochemical gradients.
|
| Figure 1: Simulated development of cell banding. In each case successive vertical lines of cells grow from left to right, paralleling a biochemical gradient. (a) Probability is low of a cell appearing in a new state or of affecting its neighbours; (b) cells with neighbours in a new state always produce offspring in that new state; (c) as in (b), but state changes can also propagate sideways after cells form. |
Simulation (Figure 1) using cellular automata models demonstrates the mechanism suggested by experiment. Suppose that cells form in layers perpendicular to a biochemical gradient, and that the probability of a cell spontaneously changing state increases along the gradient. Without inter-cellular interactions, no edge forms (Figure 1a). Even if adjacent cells do interact, only a ragged edge forms (Figure 1b). Only if a change in state can propagate along an entire line of newly formed cells does the edge become sharp (Figure 1c).
Epidemic processes are common in biology. Besides the spread of diseases they also characterize such diverse processes as fire spread [6], starfish outbreaks [7] and invasions of exotic plants [8]. In all epidemic processes the interactions consist of point to point spread: one sick person infects another; one burning tree ignites another; water currents carry starfish larvae from one reef to another; and seeds spread from one site to another. The emergent property is the epidemic itself.
Epidemics can be characterized as invasion percolation [9]. The term percolation refers to flows through porous media [10]. Invasion percolation refers to flows that create their own channels through a medium. As with all percolation processes [10] epidemics display critical behaviour. That is, for some parameter V associated with the process, the process exhibits a "phase change", from non-spread to spread, at some critical value Vcritical. In this respect, epidemics resemble a large class of phenomena, ranging from collapsing sand hills to nuclear chain reactions [11]. For diseases, the critical parameter is the infection rate Rcritical, which is the probability that one sick individual will infect another. If R < Rcritical, then the epidemic dies out naturally; if R > Rcritical, then the epidemic spreads indefinitely (Figure 2).
|
| Figure 2: Spread of epidemics with differing infection rate: (a) sub-critical; (b) critical; (c) super-critical. In the simulation shown here, the neighbourhood of each cell consists of the four adjacent cells and the infection rate R is the probability that an infected cell will infect each neighbour. For this system Rcritical=0.59. |
Population dynamics were among the first systems to be recognized as exhibiting chaotic behaviour [12]; the discrete logistic x' = L x (1 - x) is one of the simplest. One of the surprising results to come from models of multi-species communities is that the more complex a model system is (that is, more species), the more likely it is to be unstable [13]. This theoretical result contradicts the traditional wisdom amongst field ecologists which has it that more complex ecosystems are necessarily more stable. An important clue in resolving this paradox is the observation that simulations of randomly formed complex systems are rarely viable: usually at least some species become extinct very quickly [14]. This result suggests that non-viable systems in nature disappear quickly and that the complex ecosystems we do see have persisted because they happen to be stable, not because they are complex.
The chief biotic interactions between sites in a landscape are "space-filling" processes, such as seed dispersal or animal migration, and "space-clearing" processes, such as fires, storms and other causes of mortality [8] [6]. Space-filling processes promote the formation of clumped distributions, which resist invasion from outsiders because of the super-abundance of local sources of seeds and other propagules [15] [8]. Clumping behavior promotes the persistence of species that would otherwise be eliminated by superior competitors. Consequences include maintenance of high diversity in tropical rainforests, formation of ecological "zones", resistance of existing communities to change and sudden, catastrophic changes in the composition of natural communities in response to clearing or fire [15] [8].
Although superficially different, many kinds of biological systems, including those described above, display patterns of connectivity that are essentially similar. We can show this by proving that the connectivity patterns inherent in the different ways we use to represent biological systems are all equivalent. Although these equivalences are widely recognized, and easy to show, their implications are so important that it is worthwhile stating them formally.
We use many different ways to model biological systems. These representations include: directed graphs (for example, decision trees, cluster analysis), matrix models (for example, linear systems, Markov processes), dynamical systems (that is, differential equations), and cellular automata [17] [16]. Between them, these representations account for models of a vast range of biological systems and processes, including all the models described in the previous section.
In each of the above representations, the patterns of connectivity reduce to objects with relationships between them. To prove this assertion we need the following formal definitions:
, where
is a set of
"vertices" (or "nodes") and
is a set of "edges".
can be defined by the mapping
,
where 
and
, which index the rows and columns
of the matrix,
are finite subsets of the integers
.
can be defined by
, where
denotes time
(or an equivalent underlying variable),
is a finite index set,
is a set of real-valued variables, and
is a set of functions such that:
in
dimensions consists of an array
and a neighbourhood function
. Here
, with
,
where the
are automata
with identical programming. The neighbourhood of a cell consists of
all other cells that interact with it.
| Theorem 1. The patterns of deendencies in matrix models, dynamical systems and cellular automata are all isomorphic to directed graphs. |
be any matrix. If we
consider its row and column indexes as nodes, then we can define the map
, where
, as follows:
and:
This map is a homomorphism because the mapping itself defines the
connectivity relation between the rows and columns of
.
By its construction, the map is both 1:1 and onto
and hence is an isomorphism. This isomorphism is general and applies
both to systems of linear equations, for which it treats the variables
as nodes of a directed graph, and to Markov processes, for which the
states of the system are treated as nodes.
Notice that, for any directed graph
,
we can define
the converse mapping
.
For all
,
we define the matrix entries by:
The other two results follow in similar vein. For a dynamical system
,
we can define the directed graph
,
where the relation
is given by:
For a cellular automaton
we can define the relation
. Then
is a directed graph and the identity map
is the
required isomorphism.
Note that, as for matrix models, reverse homomorphisms (graphs to
dynamical systems and graphs to cellular automata) can be defined
also [18]. The map
from graphs to cellular automata
is not immediately intuitive. It takes a graph's
nodes to be the vertices of an
-dimensional cube.
The neighbourhood of each vertex
consists of the vertices corresponding
to those nodes linked
to the node 
by edges of the graph.
The universal nature of connectivity patterns in directed graphs is further demonstrated by the following result, which shows that even the behavior of a system can be treated as a directed graph:
| Theorem 2. In any array of deterministic automata with a finite number of states, the state space forms a directed graph. |
Proof: First notice that any array of automata is itself an automaton. If an
array consists (say) of
identical automata, each exhibiting
possible states, then the array possesses
possible configurations.
This set of configurations is the state space for the array. If the
history of the array (for say
time intervals) affects its dynamics,
then the state space consists of
configurations.
In general, then, for any automaton
we can define the relation
by:
Since we consider only deterministic automata,
is well-defined
and the pair 
is thus a directed graph. Note also that because
we consider only the case where one state is the immediate successor
of another, the relation is always decidable.
Note, that we can extend the result to stochastic automata by defining an
edge 
to exist wherever there is a
non-zero probability of a
transition from to
.
To summarize, these results ensure that properties of connectivity patterns for directed graphs apply to many systems that are usually represented in different ways. Moreover, they apply both directly, to relationships between system elements, and indirectly, to the dynamics of the system.
Despite the similarities, we must recognize that differences in
the nature of connectivity do exist between the above systems.
In dynamical systems, for instance, not
only is the dependence of one variable on another
important, but also its magnitude and sign. In cellular automata only
cells within a local neighbourhood are ever connected. Also, the
neighbourhood function is usually symmetric. That is, if the graph
contains the edge 
, then it also
contains the edge 
.
Finally, notice that in state spaces any number of edges may lead
to a given node (state), but only one edge leads from it.
This observation leads to the following simple, but important, result:
| Theorem 3. Any deterministic automaton, or cellular automaton, with a finite number of states, ultimately falls into either a fixed state, or a limit cycle. |
Proof: This result is a corollary of the previous result. Because each state has a single successor, successive states form a chain that must either terminate or, since there is only a finite number of states, eventually return to some state that occurred earlier in the chain. Notice that, because attractors are always cycles, this result means that chaotic behavior is impossible in these systems. Notice also that the result breaks down for stochastic automata. When a stochastic system re-enters a state that it was in earlier, it is unlikely to follow the same sequence of states as it did previously.
Several important properties characterize connectivity in directed graphs
(cf. [19]).
The most basic properties concern the extent of connectivity within a graph.
We can say that two nodes in a graph are connected if there is a
sequence of edges that forms a path from one node to the other (ignoring
the direction of the edges). Thus defined, connectivity is an equivalence
relation on a graph: if
is connected to
and
is connected to
,
then is connected to
. Let us call a set of connected nodes a
patch. A graph is fully connected if it consists of a single patch.
The traversal time for a patch is the number of steps required for an
epidemic process to fill the entire patch. This number provides a measure
of communication within the patch and corresponds to the time required for
information about local events to spread everywhere.
An important question is how large are the patches within a graph? Suppose that edges in a graph are distributed randomly. The formation of patches can then be treated as percolation [10] and displays critical behavior as the number of edges increases (Figure 3).
|
| Figure 3. Critical changes in connectivity of a directed graph as the number of edges increases. (a) The size of the largest "patch" (connected subgraph). (b) Standard deviation in the size of the largest patch. (c) The number of disjoint patches. (d) Traversal time fo the largest patch. |
With less than a critical number of edges, the size of the biggest patch is usually small (Figure 3a). However, at the critical value the size of the patch increases rapidly and fills most of the graph [19].
Other properties associated with critical connectivity include the following:
All three variables (patch size, variance, and path length) display an elementary form of chaos. When the number of edges is near-critical, a small change in the number of edges results in a large change in the value of each of these variables. That is, each variable becomes sensitive to initial conditions at the critical point.
Note, too, that the patterns associated with critical connectivity described
above apply only to randomly constructed graphs. For
number of
nodes, we can always select
edges non-randomly so as to form a patch
containing 
nodes.
The above properties of connectivity in directed graphs are at their most obvious in the epidemic processes described earlier. However, Theorems 1 and 2 above imply that these patterns affect the structure and function of many biological systems.
As Theorem 2 shows, critical changes in connectivity can occur within the state spaces of automata. Operationally, low connectivity in the state space ("cool" models) means that a model produces few changes to its starting configuration (Figure 4).
|
| Figure 4. Changes in system configuration that accompany the transition from "cool" to "hot" cellular automata. Each CA Starts from a random configuration and includes more rules (slected at random) than the one before it. The numbers below each image indicate the approximate percentage of configurations that the model changes. |
That is, most starting configurations lead the model either to "freeze" into a fixed configuration, or else to cycle with short periodicity [21] [20]. High connectivity ("hot" models) means that configurations are continually altered, so large-scale patterns have no chance to emerge. Models for which the state space has near-critical connectivity are the most likely to produce "interesting" patterns.
In systems for which a network of finite state automata is a valid representation, Theorem 3 ensures that the system's behavior will ultimately reduce either to fixed states or else to limit cycles. One such case is the class of genetic nets studied by Kauffman [23] [22]. In Kauffman's model, genes act as binary switches - they may be active ("on") or inactive ("off") - that not only code for the production of proteins, but also affect the states of other genes. Development, he argues, is largely controlled by the design of this network of switches. Although the state space for such nets is huge, even for a small number of genes (the nodes), simulations confirm that the periodicity of state cycles is relatively short in most randomly constructed nets. Kauffman suggests that these cycling periods determine the timing of critical events, such as cell division. Moreover the cycles act as attractors, so ensuring that development produces the same end result (that is, a working organism) in spite of any disturbances that may disrupt the process.
For natural communities, the critical nature of connectivity suggests that ecosystems fall into two distinct classes: poorly connected and richly connected. In poorly connected ecosystems, most population interactions are negligible and interactions involve only small numbers of species. This pattern means that even if some interactions are wildly unstable, only small numbers of species will be lost from the system. In general terms, poor connectivity most often occurs in broken or varied environments, where species do not physically come into contact with one another. In uniform environments, communities are generally more richly connected. One reason for this is the special nature of ecosystems, in which the food chain normally forms a link between most of the species.
Richly connected ecosystems, such as rainforests and coral reefs, pose great problems for modellers because it is virtually impossible to determine values of the relevant parameters with any degree of confidence. However, Levins [24] has argued that we can explain many emergent processes, and make useful predictions, by analyzing the patterns of biotic interaction in qualitative terms. His "loop analysis" consists chiefly of identifying the feedback loops that arise from species interactions. By tracing the sign of each interaction (positive interactions promote population growth; negative interactions inhibit it) we can determine whether feedback is positive or negative. From this we can deduce the emergent properties of the system - namely, whether or not it is stable.
On a landscape scale, isolation is one of the chief mechanisms of speciation. That is, a population that is physically isolated from the rest of the species accumulates genetic and physionomic changes until it is no longer capable of breeding with the rest of the species. Biologists have usually assumed that this genetic isolation must arise from substantial landscape barriers, such as rivers and mountains, that cut off a population from all outside contact. However, the implication of critical connectivity (Figure 3a) is that such extreme isolation may not be necessary. It is sufficient for connectivity in the landscape to be reduced to a level where communication between population elements is low enough to produce environmental "patches" for which the level of communication between patches is substantially lower than communication within each patch.
Besides playing a role in evolution, the fragmentation of a landscape into isolated environmental patches has severe implications for biodiversity. It is now widely recognized that in environments altered by human activity, the extent of communication between landscape units is crucial [15] [8]. There are two effects: separate areas available to a species must be sufficiently well-connected to allow "gene flow" (that is, the movement of animals or seeds) between them. Secondly, interaction between reserves and (say) farmland needs to be minimized to protect threatened species from competition with introduced species. The solution to both issues is to have a few, very large reserves, rather than many small ones. An important implication of our earlier theoretical results is that the viability of endangered species is likely to be a critical phenomenon. That is, even a small reduction in range may be enough to endanger a previously safe population.
The results above also help us to identify reasons for the apparent contradiction, mentioned earlier, that complex systems in nature are often stable, whereas model systems are usually not even viable [13]. Several mechanisms immediately suggest themselves:
It should be noted that the issues discussed here extend far more widely than biological systems alone. As we saw earlier, critical changes in connectivity produce an elementary form of chaos. Theorem 2 suggests that this elementary source of chaos is common to many processes. Note, for instance, the similarity to the Mandelbrot set [25]. This set is generated by an automaton whose states are points in the complex plane, and is given by x' = x2+a. The famous pattern formed by the automaton is associated with the switchover between two extreme behaviors of the automaton - spiralling inwards to the origin versus spiralling outwards indefinitely.
An interesting question that is raised by the above discussion is how common in biology are processes in which the degree of connectivity, either between elements or between states, changes with time or location? Certainly we need to ask this question about any system in which we see contrasting extremes. Darwinian evolution, for instance, involves changes in the balance between unrestrained mutation on the one hand, and the constraints on variation imposed by selection on the other.
Another important question is to what extent does evolution act on biological systems, as well as individual species? The systems may be suites of interacting species ("group selection"), biological processes, such as development, or even system dynamics. Taken in the broadest sense, we can understand variation to mean changes in components or connectivity, either of a system or its state space. We can interpret selection as constraints that either prevent variation or else push it in a particular direction.
That the variance of patch size is greatest when connectivity reaches a critical level leads to the conjecture that changes in connectivity may be an important source of variety in biology. For instance, interactions in the form of competition (either between species or between individuals) are likely to be much stronger in harsh environments, where food is scarce, than in mild environments, where food is plentiful. So fluctuating environments (say with good rainfall alternating with droughts) will cause sharp changes in biotic connectivity. The combinations of species that interact this way are likely to vary from place to place (and from one drought to the next).
Finally, it is worthwhile asking just how widely applicable are the results obtained here. For instance, what bearing does the degree of connectivity have on neural systems? Is the appearance of consciousness itself a critical phenomenon? For social systems, we can assess the influence of information exchange (the "edge") between individuals or groups (the "nodes"). One implication of our present discussion is that the maintenance of a culture may depend on some critical level of communication. By "communication" here, we mean the exchange of artefacts, ideas and people between geographically separated groups. For instance, an important role of early cities may have been to act as foci for concentrating the exchange of knowledge and ideas above some critical level necessary for the appearance of civilization.
This research was supported by an Australian Research Council Senior Fellowship. I am grateful to the Australian National University's Centre for Information Science Research for access to the Connection Machine Supercomputer (CM2), which I used to run some of the cellular automata models described here.