-= Research =-

Simple living systems are populations of self-replicating entities that harbor information in the form of coded symbols, subject to external and internal noise. Canonical examples are replicating macromolecules of RNA, viruses in a host environment, bacteria replicating in a Petri dish, or special-purpose computer programs replicating in core memory. For the last instance (pioneered by Ray with the tierra software) it is assumed that the basic principles governing simple living systems are independent of the substrate, and can be recreated in a computational medium. Ray's system was developed further by the avida group to the avida system: a full-fledged research platform with the flexibility to address diverse questions relating to the physics of the living state.

The principles governing natural evolving systems as laid down forcefully by Darwin are, in the scientific arena, uncontested. However, a comprehensive account of these principles from the point of view of physics is lacking, as are many of the microscopic details that give rise to Darwin's ``effective'' theory. From this point of view the situation can, with respect to our understanding of the principles underlying the evolution of complexity, be likened to the development of the theory of chaotic systems prior to the discovery of the logistic map. Many instances of chaos in natural and artificial systems were known, but the absence of a unifying point of view obscured the importance of the concept. Following this analogy, it is thought that the impact of simple artificial living systems such as avida on the development of a microscopic understanding of the physics of the living state can parallel the impact that the discovery of the logistic map has had on the development of the theory of chaos.

Our research focuses on the spatial and temporal dynamics of simple living systems and should provide important insights on the nature of the evolutionary and adaptive process, as well as the properties of the environment that the adaptation takes place in. From the point of view of a physicist, simple living systems offer the opportunity to study life in its abstraction, devoid of the complications that obscure the fundamental processes which govern the evolution of complexity and the maintenance of information, over periods of time exceeding by many orders of magnitude the natural coherence of the information-bearing substrate. The latter qualities distinguish simple living systems from non-living statistical ensembles.

Research Areas

Adaptation

Adaptation is a process that can be viewed from a strictly information-theoretical point of view--the establishment of correlations between code and the environment it evolves in--or from a dynamical point of view in which the fitness of the dominant type increases in leaps and bounds. We investigated this dynamics of "learning" first in the tierra system, by studying how these self-replicating programs evolve computational capabilities if the code evolves in a world in which computational capabilities are rewarded ("you get what you select for"). In [ADAMI 95a], programs developed the ability to perform integer addition, some with algorithms so abstruse that they could not have been written by a human programmer. Also within tierra, we studied adaptation in terms of self-organized "avalanches" [ADAMI 95b]. Similar dynamics was observed in populations of E. coli bacteria adapting under controlled circumstances by the Bacterial Evolution group at MSU [ELENA 96]. We are now collaborating with this group to compare their results with more extensive experiments using Avida, to pinpoint the role of epistasis in the development of sex [LENSKI 99], and the role of chance, history, and contingency in evolution.

Evolution of Biological Complexity

Even though it used to be an accepted notion that complexity increases in evolution, this fact has come under attack for various reasons, mostly however because complexity seems as hard to define as it is to measure. In [ADAMI 99a], we introduced a new measure of physical complexity for the complexity of symbolic sequences such as genomes, based on Information Theory and Automata Theory. Physical complexity measures the amount of information that a sequence stores about its environment, and thus is conditional on it. This measure is subsequently applied to tRNA nucleotide sequence data obtained from the EMBL sequence library as a test. With such a measure in hand, the question about the evolution of complexity can be addressed in earnest, and we show in [ADAMI 99b] that complexity must increase in evolution given a fixed environment, simply because mutations under natural selection operate like a natural Maxwell Demon, keeping mutations that increase the information about the environment, but discarding those that don't. In a companion paper [OFRIA 99c], we show that an information theoretic treatment of the pressures underlying code evolution reveals a third evolutionary pressure besides r- and K-selection, which is the selection for neutrality. This selection can be oberved for example in the evolution of genetic organization [OFRIA 99a] and of differentiation [OFRIA 99b].

Ecology and evolution

The avida system allows us not only to study adaptation globally, but also how it affects certain clusters of similar creatures, the genotypes and species. In [ADAMI 95d], we measured the "historical" abundance distribution of genotypes (programs that share the same exact sequence) as well as the "ecological" one, and compared with a simple stochastic theory. We were also able to display that an "Age-Area" relationship holds in this artificial system, as well as a McArthur-Wilson law. We were also able to measure how fast a species spreads in real space by measuring the diffusion coefficient of information, as well as the speed of the wavefront of better adapted species. This analysis can be compared to a theoretical description, and we obtain complete agreement [ADAMI 96] This analysis pertains to populations living in a single homogenous niche. In the near future, we will create several niches for the programs, so that co-evolution can take place, and an ecology can develop when there was none before.

Robustness and Evolvability

One of the key questions in the search for the origins of life addresses the characteristics of our biochemistry that have resulted in robust and evolvable code. Equally importantly, we may ask whether the design criteria adopted in "biochemical microcode" (nucleic and amino acids) can be applied to digital life, to address the robustness and evolvability of computer languages. Supported by a gift from Microsoft Research, we have investigated the influence of certain design criteria for instruction sets, such as the usage of operands, template-based addressing, direct or complementary template matching, the presence or absence of labels, as well as the number of monomers (read: size of instruction set) on the robustness and evolvability of populations of programs. To study robustness of the code with respect to mutations, we studied the percentage of neutral, beneficial and lethal mutations, and the distribution of these percentages across many runs. For evolvability we measure the rate at which a population absorbs information from its environment: the capacity of the genetic channel. [ADAMI 98c]

Critical dynamics

In [ADAMI 95b] we addressed for the first time the possibililty that adaptation in living systems may proceed via self-similar avalanches, giving rise to ubiquitous power laws in abundance and age distributions. Such experiments have been carried out in avida also [ADAMI 95d] [ADAMI 98a], and the critical exponent obtained in such distributions was obtained as a function of the mutation rate in [ADAMI 98d]. There, we find that there are violations of scale-free behavior both at high and low mutation rates, which prompts us to investigate finite-size scaling corrections and experiments with different population sizes in the future. From a more theoretical ponit of view, we have developed a theory of branching processes [CHU 99a] which predicts these geometric laws under very general circumstances, and where a single parameter, the neutrality of the fitness landscape, determines the extent of violation of scale-free bahavior. By fitting this model to actual abundance distributions (obtained from the fossil record [CHU 99b], catalogued Flora and Fauna, ecological distributions, or populations of digital organisms) the neutrality, or level of competition within an ecological niche, can be estimated even if the taxon has long been extinct. Finally, the branching model provides a qualitative explanation for the power laws observed in the sandpile of Bak, Tang, and Wiesenfeld within a conventional picture of critical second-order phase transitions with an unstable critical point [CHU 99c].

Theory of molecular evolution

The theory of evolution, while mature in principle, is not a quantitative one. Not surpringly, there still appears to be consternation in some circles about how evolution manages not to contradict the second law of thermodynamics. A fundamental quantitative theory of molecular evolution is statistical in nature, such as Eigen's (1971). However, such theories are even more difficult to test experimentally as they are to solve analytically. With the help of the avida system, we are able to test theories of molecular evolution, and influence theory formation itself. In [ADAMI 95c], we describe what are the basic building blocks of a theory of simple living systems. A version of Eigen's theory but inspired by results from avida is presented in [ADAMI 97], which shows how evolution leads to longer and longer genomes, up to the limit imposed by Eigen's error threshold. In particular, it implies that there is an optimal relationship between sequence length and mutation rate in simple organisms [ADAMI 00].

Most of the work done by our group is also described in detail (along with many other aspects of Artificial Life) in the book Introduction to Artificial Life by Chris Adami.

References

[ADAMI 94]	Title: Evolutionary Learning in the 2D Artificial Life System "Avida" Authors: Chris Adami, C. Titus Brown Published: Proc. of "Artificial Life IV", MIT Press, p. 377-381.
[ADAMI 95a]	Title: Learning and Complexity in Genetic Auto-Adaptive Systems Author: Chris Adami Journal: Physica D 80 (1995) 154-170
[ADAMI 95b]	Title: Self-organized Criticality in Living Systems Author: Chris Adami Journal: Phys. Lett. A 203 (1995) 29-32
[ADAMI 95c]	Title: On Modeling Life Author: Chris Adami Journal: Artificial Life 1 (1994) 429.
[ADAMI 95d]	Title: Abundance Distributions in Artificial Life and Stochastic Models: "Age and Area" revisited Authors: C. Adami, C.T. Brown, M. Haggerty Published: Proc. of ECAL 95 conference, Lect. Notes. Artif. Intell. 929 (1995) 503-514.
[ADAMI 96]	Title: Propagation of Information in Populations of Self-Replicating Code Authors: Johan Chu, Chris Adami Journal: Proceedings of "Artificial Life V, p. 462-469."
[ADAMI 97]	Title: Driving Molecular Evolution to the Error Threshold Authors: C. Adami and H.G. Schuster
[ADAMI 98a]	Title: Introduction to Artificial Life Author: Chris Adami Published by Springer Verlag 1998 -- 402 pages, Hardcover ISBN 0-387-94646-2
[ADAMI 98c]	Title:Robustness and Evolvability of Computer Languages Authors: C. Adami, T.C. Collier, and C.A. Ofria (submitted to PNAS)
[ADAMI 98d]	Title: Critical Exponent of Species-Size Distribution in Evolution Authors: Chris Adami, Ryoichi Seki, Robel Yirdaw Published: Proc. of Artificial Life VI, p. 221-227.
[ADAMI 99a]	Title: Physical Complexity of Symbolic Sequences Authors: C. Adami and N.J. Cerf Journal: Physica D 137 (2000) 62-69.
[ADAMI 99b]	Title: Evolution of Biological Complexity Authors: C. Adami, C. Ofria, and T.C. Collier Journal: Proc. Nat. Acad. Sci. USA 97 (2000).
[ADAMI 00]	Title: Optimal Speed of Molecular Evolution Authors: C. Adami and H. G. Schuster Published: Submitted to PRL
[CHU 99a]	Title: Critical and Near-Critical Branching Processes Authors: J. Chu and C. Adami (submitted)
[CHU 99b]	Title: A Simple Explanation for Taxonomic Abundance Distributions Authors: J. Chu and C. Adami Journal: Proc. Nat. Acad. Sci. USA 96 (1999) 15017-15019.
[CHU 99c]	Title: Non-Critical Sandpiles Authors: J. Chu and C. Adami (submitted)
[ELENA 96]	Title: Punctuated Evolution Caused by Selection of Rare Beneficial Mutations Authors: S.F. Elena, V.S. Cooper, and R.E. Lenski Journal: Science 272 (1996) 1802.
[LENSKI 99]	Title: Genome Complexity, Robustness, and Genetic Interactions in Digital Organisms Authors: R.E. Lenski, C. Ofria, T.C. Collier, and C. Adami Journal: Nature 400 (1999) 661-664.
[OFRIA 99a]	Title: Evolution of Genetic Organization in Digital Organisms Authors: C. Ofria and C. Adami Published: Proceedings DIMACS Workshop on Evolution as Computation, Jan 11-12, Princeton University, L. Landweber and E. Winfree, eds., Springer-Verlag, N.Y. (1999) p. 167.
[OFRIA 99b]	Title: Evolution of Differentiated Expression Patterns in Digital Organisms Authors: C. Ofria, C. Adami, T.C. Collier, and G. Hsu Published: Proc. 5th European Conf. on Artificial Life (ECAL99), Lect. Notes Artif. Intell. 1674 (1999) 129-138.
[OFRIA 99c]	Title: Selective Pressures on Genomes in Evolution Authors: C. Ofria, C. Adami, and T.C. Collier Published: Submitted to Nature

Page maintained by Charles Ofria
Send all comments to charles@krl.caltech.edu