Physical models of biological evolution
Vandewalle N.(+) and Ausloos M.(*)
S.U.P.R.A.S., Institut de Physique B5, Université de Liège, B-4000 Liège, Belgium
Abstract:
Combined statistical physics and computation modelling give new instruments for the study of evolutionary systems. The simulated patterns show some complex features as in biological systems. Various evolution motivated models have been invented like the "Game of Life" cellular automaton or the recent model of Bak and Sneppen. Self-organized criticality (also called the "edge of chaos") is found to be a paradigm in the study of such models. This suggests that in nature non-linear processes organize biological systems into structures that appear to have order on all length scales. To imagine possible mechanisms responsible for natural complexity allow physicists to dream that they contribute to the understanding of LIFE!
1. Introduction
With the advent of computer modelling, physicists can now simulate large (but finite) biological systems with sizes which can be stored and manipulated by computers. For example, this is possible for the human genome which contains about one million of elements, the human body made of some billion of cells and the humanity size reaching actually 5 billion individuals. No need to say that an adequate understanding of nature rules/laws a priori requires much more than finding mathematical laws.
On the other hand, new concepts for the dynamics of large systems have been developed recently for various natural systems like sandpiles, earthquakes, immunology, high-Tc superconductors, evolution, ...
Here, we will review some biological evolution motivated computer models. We will point out that "self-organized criticality" [1] seems to be a natural rule for evolution. The latter concept is of high physical and philosophical interest because it suggests that natural systems evolves spontaneously towards complex temporal and/or spatial structures which are ordered on all scales [2,3].
2. Cellular automata as biologically motivated models
Cellular automata [4] are defined on lattices for which each cell can present
q different states. At each time step, the state of each cell is updated
following deterministic or stochastic rules taking into account K input cell
states. These latter K cells are assumed to be the immediate neighbours or are
chosen far away on the lattice. The total number R=
of different possible cellular automaton rules becomes quite large even for
small integer q and K values. The cellular automaton is said to be synchronous
when all cells of the lattice are updated simultaneously or asynchronous
otherwise. The oldest cellular automaton is probably the well known Pascal's
triangle. A good review of simple cellular automata can be found in Ref.[4].
Various applications of cellular automata to biology are thus found in ref. [5], e.g. self-reproduction with sexuality, immunology and AIDS models, evolution, cell differentiation, growth of bacterian cell colonies and tumors,... Both ordered and chaotic behaviours emerge from these biologically relevant cellular automata. The interest of cellular automata resides in the sensibility of the process to small perturbations, i.e. the damage spreading. This is crucial for the present discussion since evolution is thought to be driven by mutation events, due to perturbations from ecology,... and resulting in rapid bursts of life activity on a geological timescale [6].
Let us present a biologically motivated cellular automaton, the "Game of Life", which is a synchronous deterministic cellular automaton simulating the evolution of a society of living organisms. Introduced by Conway as a mathematical toy [7], the "Game of Life" is well studied as a paradigm of an evolving ecosystem. Particular rules simulate biological-like loneliness and overcrowding process but also simulate spreading of life on dead sites. Efficient algorithms can be found in Refs. [8,9].
The game is defined on a square lattice where each cell can be "dead" or "alive". Finite systems of size LxL are used using periodic boundary conditions. At each computation time step, the living or dead state of all cells are updated as follows taking into account the state of the K=8 nearest neighbours. A living cell dies if the number of alive neighbouring cells is strictly less than 2 (loneliness) or strictly greater than 3 (overcrowding); the cell remains alive otherwise. A dead cell turns into the living state if the number of living neighbours is exactly 3 (spreading of life); the cell remains dead otherwise.
These irreversible rules generate numerous local stationary configurations indicating the emergence of a variety and complexity of local societies. Figure 1 shows six successive steps (labelled in alphabetic order from a to e) of the evolution on a 20x20 pattern. Five local societies can be found in Figure 1: (i) a static configuration made of 4 living cells is seen in the upper-left corner of the pattern, (ii) another static society is seen below the latter one and is constituted by an annular configuration of 6 cells, (iii) a large society is seen in the upper right corner and is cycling with a period 3, (iv) a small cycling society of period two is seen just below the latter and (v) a moving society called a glider which has moved by one lattice unit to the left and one unit to the bottom after 5 simulation steps.
Figure 1
Evolution of a 20x20 resting pattern for the "Game of Life" cellular automaton.
Stable and cyclic local configurations are illustrated.
After many steps, the process is found to reach always cyclic and static local configurations constituting of roughly 3% of living cells on the lattice [10]. In such a steady-state, the gliders carrying life activity through the lattice have disappeared. The entire system is then resting. Because the process reaches always such a stable attractor without any external tunable parameter, the process is said to be self-organized.
If one perturbs the resting pattern by flipping a dead state into a living state, surrounding local configurations are perturbed and gliders are re-created carrying the perturbation far away on the lattice. The perturbation is thus carried in a kind of avalanche process towards a new steady-state. Both size and duration distribution of avalanches follow power law behaviours [2,10]. The process is said to belong to a self-organized critical regime. It is also said to be on the "edge of chaos" since a small perturbation can cause an accidentally and unpredictible endless dissipation. Such a kind of dynamical regime is known to occur in sandpiles [11], earthquakes [12], immunology [13], vortex motion in type-II superconductors [14],...
"Self-organized criticality" is to be contrasted with critical phase transitions where the fine tuning of a parameter is needed to obtain scale invariant temporal and spatial structures. Self-organized criticality characterizes systems which spontaneously drives the order parameter towards the critical value 0+ [15]. This sort of dynamical process seems to be natural for evolution since scale invariant structures are recognized to develop more "complexity" than chaotic and ordered structures [16].
The most fundamental question is whether such a phenomenon is widespread in realistic models. In this respect, one should remark that it is not possible to study the complete set of rules for the "Game of Life": if a supercomputer takes only one microsecond to investigate one single rule, the investigation of all two-dimensional rules will take about 10135 times the age of the universe!
3. The Bak and Sneppen model
Recently, Bak and Sneppen [17] introduced a model of evolution for an ecosystem with a constant number N of interacting species. Species are represented by the sites of a d-dimensionnal hypercubic lattice. At each species i is associated a scalar bi which is a random number taken out a flat distribution between zero and one. The quantity bi is the "fitness" or a measure of the "barrier against mutation". The higher the fitness, the more adapted is the species to its environment (the ecology). At each time step, the j species having the minimum bj fitness value is supposed to make an adaptative move: the fitness bj is updated by a new random number together with the fitness values of the 2d nearest neighbours.
The algorithm of the Bak and Sneppen model (BS) does not require a lot of operations. The fitness values are simply stored in a d-dimensional array of floating point numbers. For each Monte-Carlo step, a simple routine finds the minimum fitness value out of the array and updates the latter element and its nearest neighbours.
The stochastic process is found to reach always an apparent steady-state in which all mutations turn out to take place through fitnesses which are less than a critical (blocking) value bc=0.66702+/-0.00003 independently of the choice of the initial configuration of fitness values. Figure 2 presents the distribution of fitness values of N=1024 species after 5000 mutations, - the process being started from a flat distribution of fitness values.
Figure 2
The distribution of fitness values after 5000 steps for an ecosystem of N=1024 species.
Let us suppose that all species have a fitness value larger or equal to bc at a given step. The j species having the minimum fitness value (very close to bc) is thus chosen and makes an adaptative move. This implies new random values for 2d+1 species (the mutating ones and the neighbours) and certainly leads to some species having a fitness which are less than bc immediately or after some other Monte Carlo timesteps. The latter species will be chosen in the next steps and will create new "active" species [18] until all fitnesses are anew larger or equal to bc. This process of extremal dynamics could be regarded as an intermittency of avalanches, avalanches being defined as causally connected sequences of mutation activity through fitness values below the threshold bc. The size s of an avalanche is the number of mutations occuring in the avalanche and is equivalent to the avalanche duration. The size distribution n(s) of avalanches of "life activity" is numerically found to follow a power law behaviour n(s)~s-[[tau]] with an exponent [[tau]]=1.07+/-0.01 [17]. The absence of a characteristic scale means that the process is critical, i.e. the dynamics of the Bak and Sneppen model is self-organized critical.
In the paleontological record, bursts of activity of all sizes are found to be separated by long periods of quiescence [6]. The intermittent nature of evolution in the Bak and Sneppen model thus describes the reported punctuated equilibrium features of biological evolution [19]. The latter notion is in opposition to the Darwin gradualism for which speciation events takes place continuously and slowly [20].
4. The tree-like model of evolution
Very recently [21], we have extended the BS model to a branching process in order to study an evolution as a succession of speciations events. Our tree-like model of evolution considers the growth of trees where all living species are located on the extremities (leaves) of the trees. The "distance" between two living species m and n is the minimum number of segments to connect the m species to the n species. Such trees are similar to the phylogenetic trees regularly used by biologists and paleontologists. A small part of such a tree showing five living species is drawn in Figure 3.
A random number between zero and one (the fitness as defined above) is assigned to each species. The growth process is defined as follows. At each step, the species having the minimum fitness value is selected. Because this species is the more sensible to its environment, a speciation (a branching event) occurs and leads to the formation of two offsprings which compete with each other. The two new species can be considered as geographically or genetically differenciated. Both offsprings receive a new random fitness value. Because of interactions between the species, this branching event affects the fitness of other species in the ecology. In the tree-like model of evolution, all the species which are lying at a distance less than k from the selected (branching) species are assumed to receive a new random fitness value. As an example for k=3, a speciation occuring on the species labelled 2 will lead to two new species and will affect the species 3, 4 and 5 while the rest of the tree remains unchanged. One should note that the k=1 case is a decorrelated process where all branching events are disconnected from each other. Obviously, this particular case is not of biological interest.
Figure 3
A small part of a phylogenetic-like tree showing five living species which are labelled.
A simulated tree starting from a single ancestor is presented in Figure 4. The tree contains 4000 living species and has evolved through about 250 avalanches [22]. Starting from any arbitrary configuration, the tree growth process self-organizes the fitness distribution towards a step-like distribution as for the BS model. The value of the threshold bc is here a function of k. This k-dependence is plotted in Figure 5 showing a non-trivial (neither an exponential nor power law) decay towards zero for very large k values. In fact, the self-organization is observed for all finite values of k. The process is obviously chaotic for k->+[[infinity]] but the latter situation is irrelevant for biological evolution since the disparition of an insect species in Amazonia does not really affect the life of polar bears.
Figure 4
A tree grown from a single root. The tree is made of 4000 living species and has evolved through the intermittency of about 250 avalanches.
Figure 5
The threshold value bc as a function of the parameter k.
As for the BS model, the process can be described by an intermittency of avalanches, intermittency which is relevant for the punctualism view of evolution (see the previous section). The size-distribution n(s) of avalanches is numerically found to be a power law with an exponent [[tau]] which is strongly dependent of the parameter k. The exponent [[tau]] is 3/2 for k=2 and seems to tend to 1 for k->+[[infinity]] [21]. Self-organized criticality is thus recovered for all finite values of k.
The geometry of the self-organizing trees is also of interest. We found numerically that such trees are fractal with a fractal dimension ranging from 2 to infinity as k is tuned from 2 to +[[infinity]] [21]. Unfortunately, it is difficult to investigate the fractality of phylogenetic trees since these trees built by paleontologists are too small in order to test the scale invariance.
5. Discussion
The above models have not the ambition to explain the mechanisms of the biological evolution from a genetic point of view. However, their interest is that they mimic well some features of biological evolution from simple rules. Furthermore, interesting generalizations can be developed. The BS and the tree-like models show both punctualist processes (avalanches) and power law size distribution of events as observed in the paleontological record. The numerical values of the exponent [[tau]] are however different from the one observed in the paleontological record which is about 2 [23].
A major finding of research work on this field is that all processes generated by these models present self-organized critical behaviours. Some variants could lead to chaotic processes or to ordered patterns which cannot describe real biological processes. This leads to wonder which physical and universal rules lead to the emergence of complexity and living organisms. One should e.g. look if additional biological constraints bring or not the evolution processes out of self-organized criticality. More recent developments of the above models show that self-organized criticality is robust against more realistic rules [24], like a non-zero probability of extinction of the less adapted species.
There are numerous evidences of the presence of power laws in Nature like the 1/f noise spectrum, the earthquake Richter's law, fractals,... Fundamental and philosophical questions about evolution and origins of life are thus raised [25]. It is also necessary to test what "perturbations" force natural systems to evolve towards one or another "steady-state".
6. Conclusion
We have seen hereabove that simple and somewhat realistic algorithms model biological evolution.The process is driven by the dynamics of self-organized criticality features leading to the emergence of scale-invariant ("complex") structures. This suggests to us that nature works in a similar way in order to develop complexity. The principles underlying the growth of complexity driving evolution and the philosophy of complexity are discussed elsewhere by Heylighen [26] and Edmonds [27] respectively. We are only on the verge of a huge domain of investigations and a new way of thinking [28].
7. Acknowledgements
The invitation to the "Evolution of Complexity" symposium is gratefully acknowledged.
Part of this work was financially supported through the Impulse Program on High Temperature Superconductors of the Belgium Federal Services for Scientific, Technical and Cultural (SSTC) Affairs under contract SU/02/013. This work was also supported through the ARC (94-99/174) contract of the University of Liège. N.V. thanks the Belgium Research Funds for Industry and Agriculture (FRIA, Brussels). A special grant from FNRS/LOTTO allowed us to perform specific numerical work.
References
(+) e-mail address: vandewal@gw.unipc.ulg.ac.be
(*) e-mail address: ausloos@gw.unipc.ulg.ac.be
[1] Bak, P., Tang C. and Wiesenfeld K., Phys. Rev. Lett. 59, 381 (1987)
[2] Bak, P., Chen K. and Creutz M., Nature 342, 780 (1989)
[3] Bak, P. and Paczuski M.,
Proc. Nat. Acad. Sci. (USA) 92, 6689 (1995)
[4] Wolfram, S., Rev. Mod. Phys. 55, 601 (1983)
[5] Baer, R. and Martinez H., in Automata and Biology,
Ann. Rev. Biophys. 3, 255 (1974)
[6] Eldregdge, N. and Gould S.J., in Models in Paleobiology,
Schopf T.J.M. ed. (Freeman, San Fransisco, 1972) pp.82-115
[7] Berlekamp, E.R., Conway J.H. and Guy R.K., Winning Ways for
Your Mathematical Plays (Academic, New York, 1982) Vol.2
[8] Niemiec, M., Byte 4, 90 (1979)
[9] Gosper, R.W., Physica D 10, 75 (1984)
[10] Alstrøm, P. and Leao J., Phys. Rev. E 49, R2507 (1994)
[11] Dhar, D. and Ramaswamy R., Phys. Rev. Lett. 63, 1659 (1989)
[12] Sornette, A. and Sornette D., Europhys. Lett. 9, 197 (1989)
[13] Bonabeau, E., Physica A 208, 336 (1994)
[14] Pla, O. and Nori F., Phys. Rev. Lett. 67, 919 (1991)
[15] Sornette, D., Johansen A. and Dornic I.,
J. Phys. I (France) 5, 325 (1995)
[16] Zhang, Y.C., J. Phys. I (France) 1, 971 (1991)
[17] Bak, P. and Sneppen K., Phys. Rev. Lett. 71, 4083 (1993)
[18] Vandewalle, N. and Ausloos M., Physica D, in press (1996)
[19] Sneppen, K., Physica A 221, 168 (1995)
[20] Darwin, C., The Origin of Species , (John Murray, London, 1859)
[21] Vandewalle, N. and Ausloos M., J. Phys. I (France) 5, 1011 (1995)
[22] Ausloos, M. and Vandewalle N., Europhysics News 26, 55 (1995)
[23] Sneppen, K., Bak P., Flyvbjerg H., and Jensen M.H.,
Proc. Nat. Acad. Sci. (USA) 92, 5209 (1995)
[24] Vandewalle, N. and Ausloos M., Europhys. Lett. 32, 613 (1995)
[25] Vandewalle, N. and Ausloos M., in Annual Reviews of Computational Physics, D. Stauffer ed. (World Scientific, Singapore, 1996) vol. 3
[26] Heylighen, F., Einstein meets Magritte, Aerts D. ed.,
Kluwer Academic Publishers, New York, 1995
[27] Edmonds, B., Einstein meets Magritte, Aerts D. ed.,
Kluwer Academic Publishers, New York, 1995
[28] West, B.J. and Deering B., The Lure of Modern Science ,
(World Scientific, Singapore, 1995)