Skip to main content
main-content

Über dieses Buch

The study of the genetic basis for evolution has flourished in this century, as well as our understanding of the evolvability and programmability of biological systems. Genetic algorithms meanwhile grew out of the realization that a computer program could use the biologically-inspired processes of mutation, recombination, and selection to solve hard optimization problems. Genetic and evolutionary programming provide further approaches to a wide variety of computational problems. A synthesis of these experiences reveals fundamental insights into both the computational nature of biological evolution and processes of importance to computer science. Topics include biological models of nucleic acid information processing and genome evolution; molecules, cells, and metabolic circuits that compute logical relationships; the origin and evolution of the genetic code; and the interface with genetic algorithms and genetic and evolutionary programming.

Inhaltsverzeichnis

Frontmatter

Genome System Architecture and Natural Genetic Engineering

Abstract
Molecular genetics reveals three aspects of genome organization and reorganization that provide opportunities for formulating new views of the evolutionary process:
1
Organization of the genome as a hierarchy of systems (not units) determining many aspects of genetic function (only some of which are specifying protein and RNA sequences);
 
2
The presence of many repetitive DNA elements in the genome which do not encode protein or RNA structure but serve as the physical basis for functional integration; and
 
3
The operation of regulated cellular natural genetic engineering systems capable of rearranging basic genomic components throughout the genome in a single cell generation.
 
Thus, concerted, non-random changes in the genome guided by cellular computing networks are plausible at the molecular level.
James A. Shapiro

Evolutionary Computation as a Paradigm for DNA-Based Computing

Abstract
Evolutionary Computation focuses on probabilistic search and optimization methods gleaned from the model of organic evolution. Genetic algorithms, evolution strategies, and evolutionary programming are three independently developed representatives of this class of algorithms, with genetic programming and classifier systems as additional paradigms in the field.
This paper focuses on the link between evolutionary computation and DNA-based computing by discussing the relevant aspects of evolutionary computation both from a practical and a theoretical point of view. In particular, theoretical results concerning the calculation of convergence velocities and the derivation of optimal schedules for mutation rates, respectively steps sizes, are presented.
The potential for cross-fertilization between the fields of DNA-based computing and evolutionary computation is outlined both from a fundamental point of view and by means of an experimental investigation concerning the NP-hard maximum clique problem. A simple evolutionary approach to maximum clique is introduced and the hypothesis whether the increase in population size possible by realizing evolutionary computation with DNA yields the expected improvement in solution quality is tested. Results obtained for a limited range of population sizes up to 105 indicate that the hypothesis holds for about two-thirds of the investigated problem instances (which were taken from the DIMACS library).
Thomas Bäck, Joost N. Kok, Grzegorz Rozenberg

Evolution at the Edge of Chaos: A Paradigm for the Maturation of the Humoral Immune Response

Abstract
We study the maturation of the antibody population following primary antigen presentation as a global optimization problem. Emphasis is placed on the trade-off between the safety of mutations that lead to local improvements to the antibody’s affinity and the necessity of eventual mutations that result in global reconfigurations in the antibody’s shape. The model described herein gives evidence of the underlying optimization process from which the rapidity and consistency of the biologic response could be derived.
Patricia K. Theodosopoulos, Theodore V. Theodosopoulos

The Evolutionary Unfolding of Complexity

Abstract
We analyze the population dynamics of a broad class of fitness functions that exhibit epochal evolution—a dynamical behavior, commonly observed in both natural and artificial evolutionary processes, in which long periods of stasis in an evolving population are punctuated by sudden bursts of change. Our approach—statistical dynamics—combines methods from both statistical mechanics and dynamical systems theory in a way that offers an alternative to current “landscape” models of evolutionary optimization. We describe the population dynamics on the macroscopic level of fitness classes or phenotype subbasins, while averaging out the genotypic variation that is consistent with a macroscopic state. Metastability in epochal evolution occurs solely at the macroscopic level of the fitness distribution. While a balance between selection and mutation maintains a quasistationary distribution of fitness, individuals diffuse randomly through selectively neutral subbasins in genotype space. Sudden innovations occur when, through this diffusion, a genotypic portal is discovered that connects to a new subbasin of higher fitness genotypes. In this way, we identify evolutionary innovations with the unfolding and stabilization of a new dimension in the macroscopic state space. The architectural view of subbasins and portals in genotype space clarifies how frozen accidents and the resulting phenotypic constraints guide the evolution to higher complexity.
James P. Crutchfield, Erik van Nimwegen

Genetic Programming: Biologically Inspired Computation That Creatively Solves Non-trivial Problems

Abstract
This paper describes a biologically inspired domain-independent technique, called genetic programming, that automatically creates computer programs to solve problems. Starting with a primordial ooze of thousands of randomly created computer programs, genetic programming progressively breeds a population of computer programs over a series of generations using the Darwinian principle of natural selection, recombination (crossover), mutation, gene duplication, gene deletion, and certain mechanisms of developmental biology. The technique is illustrated by its application to a non-trivial problem involving the automatic synthesis (design) of a lowpass filter circuit. The evolved results are competitive with human-produced solutions to the problem. In fact, four of the automatically created circuits exhibit human-level creativity and inventiveness, as evidenced by the fact that they correspond to four inventions that were patented between 1917 and 1936.
John R. Koza, Forrest H. Bennett, David Andre, Martin A. Keane

Is Ours the Best of All Possible Codes?

Abstract
Although evidence is accumulating that the genetic code arose through stereochemical interactions between individual amino acids and oligonucleotides, its subsequent evolution remains contentious. On the one hand, the present structure of the code may be an end-point of natural selection such that codon assignments are organised to minimise the deleterious phenotypic effects of genetic error. On the other hand, the structure of the code may simply reflect its history, whereby novel amino acids were synthesised as the by-products of metabolism and subsequently incorporated into the code by capturing a subset of the codons previously assigned to their biosynthetic precursors. Both processes could potentially produce a code in which similar amino acids are assigned to similar codons. Here I argue for the plausibility of the adaptive (‘error minimisation’) interpretation of code structure and present quantitative evidence for this model. I further demonstrate that this evidence cannot be explained away as an artifact of a biosynthetic model of code evolution.
Stephen J. Freeland

The Impact of Message Mutation on the Fitness of a Genetic Code

Abstract
The standard genetic code (SGC) is organized in such a way that similar codons encode similar amino acids. One of the earliest explanations for this was that the SGC is the result of natural selection to reduce the fitness cost, or “load,” from mutations in and mistranslation of protein-coding genes. However, it was later argued on both empirical and conceptual grounds that the SGC could not have evolved to reduce load. We claim that the empirical evidence has been misinterpreted and review how the pattern of amino acid similarities in the SGC are consistent with the “load minimization hypothesis” or “LM hypothesis.” We then present a model which addresses a second classical objection to the load minimization hypothesis: that selection for load minimization must be indirect or weak because it acts across generations. In this model, individual fitness is determined by a protein distribution resulting from the translation of its genetic message using a genetic code. Amino acids contribute independently and multiplicatively to the fitness of the protein distribution, which is defined relative to a fixed target protein. We show that in mutation-selection balance a fitness can be associated with a population of individuals with the same genetic code, and illustrate that structure-preserving codes that assign similar codons to similar amino acids confer higher fitness. We also show that in mutation-selection balance the total message of any individual behaves like a population of sites. That is, the usage of codons in a message in almost any individual reflects the codon frequencies across the population for a site of a given type, and consequently the fitness of almost all individuals is equal to the population fitness associated with their genetic code. We thereby establish that selection for load minimization in genetic codes acts at the level of an individual in a single generation. Comparing the fitness of two genetic codes, one more structure-preserving than the other, we find that the more structure-preserving code is associated with lower load and consequently higher fitness, despite the fact that the equilibrium fraction of mutant codons in its mutation-selection balance is larger; these results are explained and conjectured to hold in general. We conclude with comments on the origin of the genetic code from the perspective of a model of this kind, including its shortcomings and advantages over other hypotheses as a comprehensive explanation for the origin of the SGC.
Guy Sella, David H. Ardell

Genetic Code Evolution in the RNA World and Beyond

Abstract
Although the translation apparatus presumably arose in an RNA world, subsequent modifications obscure its origins. The genetic code, fixed in the Last Universal Ancestor may contain clues about the types of chemical interaction that led to early correspondences between RNA and protein. The extent to which contemporary translation reflects these primordial influences depends on the processes that have shaped the genetic code since its inception: stereochemical interaction between amino acids and RNA, historical constraints ensuring continuity between successive codes, and optimization to minimize the effects of errors caused by translation and mutation. This chapter explains how these processes, typically presented as mutually antagonistic, may actually be viewed as complementary on different timescales, and I suggest how the “first” codons could have been established in the context of an RNA world.
Robin D. Knight

Imposing Specificity by Localization: Mechanism and Evolvability

Abstract
Cells detect extracellular signals by allostery and then give those signals meaning by “regulated localization”. We suggest that this formulation applies to many biological processes and is particularly well illustrated by the mechanisms of gene regulation. Analysis of these mechanisms reveals that regulated localization requires simple molecular interactions that are readily used combinatorially. This system of regulation is highly “evolvable”, and its use accounts, at least in part, for the nature of the complexities observed in biological systems.
Mark Ptashne, Alexander Gann

Towards a Predictive Biology: The Example of Bacteriophage T7

Abstract
I examine a relatively simple and well-characterized virus, bacteriophage T7, as a platform for advancing the development of a predictive system-level biology This examination results in a non-fitted mechanistic simulation capable of predicting the virus’ growth cycle resolved at the level of unique intracellular species. From this effort I hope to approach the following questions. How good are the predictions from such a simulation? Can we evaluate our level of understanding for a biological system by comparing such quantitative predictions to observations? What new questions regarding evolved biological systems become addressable using such a simulation? Finally, if the behavior of an evolved biological system can be predicted, can the same abilities be applied to design novel biological systems?
Drew Endy

Using Artificial Reagents to Dissect Cellular Genetic Networks

Abstract
I describe work from the laboratory that promises to improve our ability to analyze the networks of genes that govern biological phenomena. By deepening our understanding of the genetic networks that govern gene expression and signal transduction, these experiments should speed the day when we can quantitatively predict the behaviors of these systems and understand how the particular ways that cells use to perform computations arose. In the process, the technologies we use to explore these systems may provide useful starting points to help build new ones.
Roger Brent

Computational Aspects of Gene (Un)Scrambling in Ciliates

Abstract
Ciliates, a very ancient group of organisms, have evolved extraordinary ways of organizing, manipulating, and replicating the DNA in their micronuclear genomes. The way that ciliates transform genes from their micronuclear (storage) form into their macronuclear (expression) form constitutes a very interesting case of “DNA computing in vivo”. In this paper we investigate in detail one aspect of this transformation, viz., gene (un)scrambling. In particular, we use the formal framework of pointer reduction systems to investigate the computational aspects of gene (un)scrambling.
Andrzej Ehrenfeucht, David M. Prescott, Grzegorz Rozenberg

Universal Molecular Computation in Ciliates

Abstract
How do cells and nature “compute”? They read and “rewrite” DNA all the time, by processes that modify sequences at the DNA or RNA level. In 1994, Adleman’s elegant solution to a seven-city Directed Hamiltonian Path problem using DNA [1] launched the new field of DNA computing, which in a few years has grown to international scope. However, unknown to this field, ciliated protozoans of genus Oxytricha and Stylonychia had solved a potentially harder problem using DNA several million years earlier. The solution to this “problem”, which occurs during the process of gene unscrambling, represents one of nature’s ingenious solutions to the problem of the creation of genes. Here we develop a model for the guided homologous recombinations that take place during gene rearrangement and prove that such a model has the computational power of a Turing machine, the accepted formal model of computation. This indicates that, in principle, these unicellular organisms may have the capacity to perform at least any computation carried out by an electronic computer.
Laura F. Landweber, Lila Kari

Toward in vivo Digital Circuits

Abstract
We propose a mapping from digital logic circuits into genetic regulatory networks with the following property: the chemical activity of such a genetic network in vivo implements the computation specified by the corresponding digital circuit. Logic signals are represented by the synthesis rates of cytoplasmic DNA binding proteins. Gates consist of structural genes for output proteins, fused to promoter/operator regions that are regulated by input proteins. The modular approach for building gates allows a free choice of signal proteins and thus enables the construction of complex circuits. This paper presents simulation results that demonstrate the feasibility of this approach. Furthermore, a technique for measuring gate input/output characteristics is introduced. We will use this technique to evaluate gates constructed in our laboratory. Finally, this paper outlines automated logic design and presents BioSpice, a prototype system for the design and verification of genetic digital circuits.
Ron Weiss, George E. Homsy, Thomas F. Knight

Evolution of Genetic Organization in Digital Organisms

Abstract
We examine the evolution of expression patterns and the organization of genetic information in populations of self-replicating digital organisms. Seeding the experiments with a linearly expressed ancestor, we witness the development of complex, parallel secondary expression patterns. Using principles from information theory, we demonstrate an evolutionary pressure towards overlapping expressions causing variation (and hence further evolution) to sharply drop. Finally, we compare the overlapping sections of dominant genomes to those portions which are singly expressed and observe a significant difference in the entropy of their encoding.
Charles Ofria, Christoph Adami

Toward Code Evolution by Artificial Economies

Abstract
We have begun exploring code evolution by artificial economies. We implemented a reinforcement learning machine called Hayek2 consisting of agents, written in a machine language inspired by Ray’s Tierra, that interact economically. The economic structure of Hayek2 addresses credit assignment at both the agent and meta levels. Hayek2 succeeds in evolving code to solve Blocks World problems, and has been more effective at this than our hillclimbing program and our genetic program (GP). Our hillclimber and our GP also performed well, learning algorithms as strong as a simple search program that incorporates hand-coded domain knowledge. We made efforts to optimize our hillclimbing program and it has features that may be of independent interest. Our GP using crossover performed far better than a version utilizing other macro-mutations or our hillclimber, bearing on a controversy in the genetic programming literature.
Eric B. Baum, Igor Durdanovic

Backmatter

Weitere Informationen