Physical aspects of evolutionary optimization and adaptation

A Two-Level, Intramutant Spectrum Haplotype Profile of Hepatitis C Virus Revealed by Self-Organized Maps

RNA viruses replicate as complex mutant spectra termed viral quasispecies. The frequency of each individual genome in a mutant spectrum depends on its rate of generation and its relative fitness in the replicating population ensemble. The advent of deep sequencing methodologies allows for the first-time quantification of haplotype abundances within mutant spectra. There is no information on the haplotype profile of the resident genomes and how the landscape evolves when a virus replicates in a controlled cell culture environment. Here, we report the construction of intramutant spectrum haplotype landscapes of three amplicons of the NS5A-NS5B coding region of hepatitis C virus (HCV). Two-dimensional (2D) neural networks were constructed for 44 related HCV populations derived from a common clonal ancestor that was passaged up to 210 times in human hepatoma Huh-7.5 cells in the absence of external selective pressures. The haplotype profiles consisted of an extended dense basal platform, from which a lower number of protruding higher peaks emerged. As HCV increased its adaptation to the cells, the number of haplotype peaks within each mutant spectrum expanded, and their distribution shifted in the 2D network. The results show that extensive HCV replication in a monotonous cell culture environment does not limit HCV exploration of sequence space through haplotype peak movements. The landscapes reflect dynamic variation in the intramutant spectrum haplotype profile and may serve as a reference to interpret the modifications produced by external selective pressures or to compare with the landscapes of mutant spectra in complex in vivo environments. IMPORTANCE The study provides for the first time the haplotype profile and its variation in the course of virus adaptation to a cell culture environment in the absence of external selective constraints. The deep sequencing-based self-organized maps document a two-layer haplotype distribution with an ample basal platform and a lower number of protruding peaks. The results suggest an inferred intramutant spectrum fitness landscape structure that offers potential benefits for virus resilience to mutational inputs.

Molecular evolution between chemistry and biology : The interplay of competition, cooperation, and mutation

Biological evolution is reduced to three fundamental processes in the spirit of a minimal model: (i) Competition caused by differential fitness, (ii) cooperation of competitors in the sense of symbiosis, and (iii) variation introduced by mutation understood as error-prone reproduction. The three combinations of two fundamental processes each, ([Formula: see text]) competition and mutation, ([Formula: see text]) cooperation and competition, and ([Formula: see text]) cooperation and mutation, are analyzed. Changes in population dynamics that are induced by bifurcations and threshold phenomena are discussed.

Quasispecies on Fitness Landscapes

Selection-mutation dynamics is studied as adaptation and neutral drift on abstract fitness landscapes. Various models of fitness landscapes are introduced and analyzed with respect to the stationary mutant distributions adopted by populations upon them. The concept of quasispecies is introduced, and the error threshold phenomenon is analyzed. Complex fitness landscapes with large scatter of fitness values are shown to sustain error thresholds. The phenomenological theory of the quasispecies introduced in 1971 by Eigen is compared to approximation-free numerical computations. The concept of strong quasispecies understood as mutant distributions, which are especially stable against changes in mutations rates, is presented. The role of fitness neutral genotypes in quasispecies is discussed.

Phylogeny and evolution of RNA structure

Darwin's conviction that all living beings on Earth are related and the graph of relatedness is tree-shaped has been essentially confirmed by phylogenetic reconstruction first from morphology and later from data obtained by molecular sequencing. Limitations of the phylogenetic tree concept were recognized as more and more sequence information became available. The other path-breaking idea of Darwin, natural selection of fitter variants in populations, is cast into simple mathematical form and extended to mutation-selection dynamics. In this form the theory is directly applicable to RNA evolution in vitro and to virus evolution. Phylogeny and population dynamics of RNA provide complementary insights into evolution and the interplay between the two concepts will be pursued throughout this chapter. The two strategies for understanding evolution are ultimately related through the central paradigm of structural biology: sequence ⇒ structure ⇒ function. We elaborate on the state of the art in modeling both phylogeny and evolution of RNA driven by reproduction and mutation. Thereby the focus will be laid on models for phylogenetic sequence evolution as well as evolution and design of RNA structures with selected examples and notes on simulation methods. In the perspectives an attempt is made to combine molecular structure, population dynamics, and phylogeny in modeling evolution.

Realistic three dimensional fitness landscapes generated by self organizing maps for the analysis of experimental HIV-1 evolution

Human Immunodeficiency Virus type 1 (HIV-1) because of high mutation rates, large population sizes, and rapid replication, exhibits complex evolutionary strategies. For the analysis of evolutionary processes, the graphical representation of fitness landscapes provides a significant advantage. The experimental determination of viral fitness remains, in general, difficult and consequently most published fitness landscapes have been artificial, theoretical or estimated. Self-Organizing Maps (SOM) are a class of Artificial Neural Network (ANN) for the generation of topological ordered maps. Here, three-dimensional (3D) data driven fitness landscapes, derived from a collection of sequences from HIV-1 viruses after “in vitro” passages and labelled with the corresponding experimental fitness values, were created by SOM. These maps were used for the visualization and study of the evolutionary process of HIV-1 “in vitro” fitness recovery, by directly relating fitness values with viral sequences. In addition to the representation of the sequence space search carried out by the viruses, these landscapes could also be applied for the analysis of related variants like members of viral quasiespecies. SOM maps permit the visualization of the complex evolutionary pathways in HIV-1 fitness recovery. SOM fitness landscapes have an enormous potential for the study of evolution in related viruses of “in vitro” works or from “in vivo” clinical studies with human, animal or plant viral infections.

ViennaRNA Package 2.0

Background

Secondary structure forms an important intermediate level of description of nucleic acids that encapsulates the dominating part of the folding energy, is often well conserved in evolution, and is routinely used as a basis to explain experimental findings. Based on carefully measured thermodynamic parameters, exact dynamic programming algorithms can be used to compute ground states, base pairing probabilities, as well as thermodynamic properties.

Results

The ViennaRNA Package has been a widely used compilation of RNA secondary structure related computer programs for nearly two decades. Major changes in the structure of the standard energy model, the Turner 2004 parameters, the pervasive use of multi-core CPUs, and an increasing number of algorithmic variants prompted a major technical overhaul of both the underlying RNAlib and the interactive user programs. New features include an expanded repertoire of tools to assess RNA-RNA interactions and restricted ensembles of structures, additional output information such as centroid structures and maximum expected accuracy structures derived from base pairing probabilities, or z-scores for locally stable secondary structures, and support for input in fasta format. Updates were implemented without compromising the computational efficiency of the core algorithms and ensuring compatibility with earlier versions.

Conclusions

The ViennaRNA Package 2.0, supporting concurrent computations via OpenMP, can be downloaded from http://www.tbi.univie.ac.at/RNA.

In silico evolution of early metabolism

We developed a simulation tool for investigating the evolution of early metabolism, allowing us to speculate on the formation of metabolic pathways from catalyzed chemical reactions and on the development of their characteristic properties. Our model consists of a protocellular entity with a simple RNA-based genetic system and an evolving metabolism of catalytically active ribozymes that manipulate a rich underlying chemistry. Ensuring an almost open-ended and fairly realistic simulation is crucial for understanding the first steps in metabolic evolution. We show here how our simulation tool can be helpful in arguing for or against hypotheses on the evolution of metabolic pathways. We demonstrate that seemingly mutually exclusive hypotheses may well be compatible when we take into account that different processes dominate different phases in the evolution of a metabolic system. Our results suggest that forward evolution shapes metabolic network in the very early steps of evolution. In later and more complex stages, enzyme recruitment supersedes forward evolution, keeping a core set of pathways from the early phase.

Mathematical modeling of evolution. Solved and open problems

Evolution is a highly complex multilevel process and mathematical modeling of evolutionary phenomenon requires proper abstraction and radical reduction to essential features. Examples are natural selection, Mendel's laws of inheritance, optimization by mutation and selection, and neutral evolution. An attempt is made to describe the roots of evolutionary theory in mathematical terms. Evolution can be studied in vitro outside cells with polynucleotide molecules. Replication and mutation are visualized as chemical reactions that can be resolved, analyzed, and modeled at the molecular level, and straightforward extension eventually results in a theory of evolution based upon biochemical kinetics. Error propagation in replication commonly results in an error threshold that provides an upper bound for mutation rates. Appearance and sharpness of the error threshold depend on the fitness landscape, being the distribution of fitness values in genotype or sequence space. In molecular terms, fitness landscapes are the results of two consecutive mappings from sequences into structures and from structures into the (nonnegative) real numbers. Some properties of genotype-phenotype maps are illustrated well by means of sequence-structure relations of RNA molecules. Neutrality in the sense that many RNA sequences form the same (coarse grained) structure is one of these properties, and characteristic for such mappings. Evolution cannot be fully understood without considering fluctuations--each mutant originates form a single copy, after all. The existence of neutral sets of genotypes called neutral networks, in particular, necessitates stochastic modeling, which is introduced here by simulation of molecular evolution in a kind of flowreactor.

Mutate now, die later. Evolutionary dynamics with delayed selection

We analyze here the evolutionary consequences of selection with delay in a population genetics context. In the classical works on evolutionary dynamics, an individual produces off-springs in direct proportion to its fitness, a process in which mutations may occur. In the present scenario of delayed selection, individuals that acquire deleterious mutations can still reproduce unharmed for several generations. During this time delay, the damage passed on to off-springs can potentially be repaired by subsequent compensatory mutations. In the absence of such a repair, the individual becomes sterile. Here we study the population-genetic effects of such a time delay by means of both numerical simulations and theoretical modeling. The results show that delayed selection lowers the extinction threshold, endangering the survival of the population. Surprisingly, however, no traces of this delay effect are encountered in the sequence diversity of the population. These conclusions suggest that delayed selection is hard to detect in genetic data and thus could be a wide-spread but rarely detected phenomenon.

Error thresholds and stationary mutant distributions in multi-locus diploid genetics models

We study multi-locus models for the accumulation of disadvantagenous mutant alleles in diploid populations. The theory used is closely related to the quasi-species theory of molecular evolution. The stationary mutant distribution may either be localized close to a peak in the fitness landscape or delocalized throughout sequence space. In some cases there is a sharp transition between these two cases known as an error threshold. We study a multiplicative fitness landscape where the fitness of an individual withjhomozygous mutant loci andkheterozygous loci iswjk= (1 −s)j(1 −hs)k. For a sexual population in this landscape there are two types of solution separated by an error threshold. For a parthenogenetic population there may be three types of solution and two error thresholds for some values ofh. For a population reproducing by selfing the solution is independent ofh, since the frequency of heterozygous individuals is negligible. The mean fitnesses of the populations depend on the reproductive method even for the multiplicative landscape. The sexual may have a higher or lower fitness than the parthenogen, depending on the values ofhandu/s. Selfing leads to a higher mean fitness than either sexual reproduction or parthenogenesis. We also study a fitness landscape with epistatic interactions withwjk= exp(−s(2j+k)α). The sexual population has a higher fitness than the parthenogen when α > 1. This confirms previous theories that sexual reproduction is advantageous in cases of synergistic epistasis. The mean fitness of a selfing population was found to be higher than both the sexual and the parthenogen over the range of parameter values studied. We discuss these results in relation to the theory of the evolution of sex. The fitness of the stationary distribution in cases where unfavourable mutations accumulation is one factor which could explain the observed prevalence of sexual reproduction in natural populations, although other factors may be more important in many cases.

Evolutionary self-organization in complex fluids

This paper explores the ability of molecular evolution to take control of collective physical phases, making the first decisive step from independent replicators towards cell-like collective structures. We develop a physical model of replicating combinatorial molecules in a ternary fluid of hydrocarbons, amphiphiles and water. Such systems are being studied experimentally in various laboratories to approach the synthesis of artificial cells, and are also relevant to the origin of cellular life. The model represents amphiphiles by spins on a lattice (with Ising coupling in the simplest case), coupled to replicating molecules that may diffuse on the lattice and react with each other. The presence of the replicating molecules locally modulates the phases of the complex fluid, and the physical replication process and/or mobility of the replicating molecules is influenced by the local amphiphilic configuration through an energetic coupling. Consequently, the replicators can potentially modify their environment to enhance their own replication. Through this coupling, the system can associate hereditary properties, and the potential for autonomous evolution, to self-assembling mesoscale structures in the complex fluid. This opens a route to analyse the evolution of artificial cells. The models are studied using Monte Carlo simulation, and demonstrate the evolution of phase control. We achieve a unified combinatorial framework for the description of isotropic families of spin-lattice models of complex phases, opening up the physical study of their evolution.

Question 1: origin of life and the living state

The aim of this article is to discuss four topics: First, the origin of molecular reproduction. Second, the origin of agency - the capacity of a system to act on its own behalf. Agency is a stunning feature of human and some wider range of life. Third, to discuss a still poorly articulated feature of life noticed by the philosopher Immanuel Kant over 200 years ago: A self propagating organization of process. We have no theory for this aspect of life, yet it is central to life. Fourth, I will discuss constraints, as in Schroedinger's aperiodic crystal (Schroedinger E, What is life? The physical aspect of the living cell, 1944), as information, part of the total non-equilibrium union of matter, energy, work, work cycles, constraints, and information that appear to comprise the living state.

Adaptive walk on complex networks

We investigate the properties of adaptive walks on an uncorrelated fitness landscape which is established in sequence spaces of complex structure. In particular, we perform numerical simulations of adaptive walks on random graphs and scale-free networks. For the former, we also derive some analytical approximations for the density of local optima of the fitness landscape and the mean length walk. We compare our results with those obtained for regular lattices. We obtain that the density of local optima decreases as 1/z, where z is the mean connectivity, for all networks we have investigated. In random graphs, the mean length walk L reaches the asymptotic value e - 1 for large z, which corresponds to the result for regular networks. Although we could not find an exact estimate, we derive an underestimated value for L. Unlike random graphs, scale-free networks show an upper asymptotic value of L.

Directed evolution of nucleic acid enzymes

Just as Darwinian evolution in nature has led to the development of many sophisticated enzymes, Darwinian evolution in vitro has proven to be a powerful approach for obtaining similar results in the laboratory. This review focuses on the development of nucleic acid enzymes starting from a population of random-sequence RNA or DNA molecules. In order to illustrate the principles and practice of in vitro evolution, two especially well-studied categories of catalytic nucleic acid are considered: RNA enzymes that catalyze the template-directed ligation of RNA and DNA enzymes that catalyze the cleavage of RNA. The former reaction, which involves attack of a 2'- or 3'-hydroxyl on the alpha-phosphate of a 5'-triphosphate, is more difficult. It requires a comparatively larger catalytic motif, containing more nucleotides than can be sampled exhaustively within a starting population of random-sequence RNAs. The latter reaction involves deprotonation of the 2'-hydroxyl adjacent to the cleavage site, resulting in cleaved products that bear a 2',3'-cyclic phosphate and 5'-hydroxyl. The difficulty of this reaction, and therefore the complexity of the corresponding DNA enzyme, depends on whether a catalytic cofactor, such as a divalent metal cation or small molecule, is present in the reaction mixture.

On the evolution of primitive genetic codes

The primordial genetic code probably has been a drastically simplified ancestor of the canonical code that is used by contemporary cells. In order to understand how the present-day code came about we first need to explain how the language of the building plan can change without destroying the encoded information. In this work we introduce a minimal organism model that is based on biophysically reasonable descriptions of RNA and protein, namely secondary structure folding and knowledge based potentials. The evolution of a population of such organism under competition for a common resource is simulated explicitly at the level of individual replication events. Starting with very simple codes, and hence greatly reduced amino acid alphabets, we observe a diversification of the codes in most simulation runs. The driving force behind this effect is the possibility to produce fitter proteins when the repertoire of amino acids is enlarged.

Quasi-independence, homology and the unity of type: a topological theory of characters

In this paper Lewontin's notion of "quasi-independence" of characters is formalized as the assumption that a region of the phenotype space can be represented by a product space of orthogonal factors. In this picture each character corresponds to a factor of a region of the phenotype space. We consider any region of the phenotype space that has a given factorization as a "type", i.e. as a set of phenotypes that share the same set of phenotypic characters. Using the notion of local factorizations we develop a theory of character identity based on the continuation of common factors among different regions of the phenotype space. We also consider the topological constraints on evolutionary transitions among regions with different regional factorizations, i.e. for the evolution of new types or body plans. It is shown that direct transition between different "types" is only possible if the transitional forms have all the characters that the ancestral and the derived types have and are thus compatible with the factorization of both types. Transitional forms thus have to go over a "complexity hump" where they have more quasi-independent characters than either the ancestral as well as the derived type. The only logical, but biologically unlikely, alternative is a "hopeful monster" that transforms in a single step from the ancestral type to the derived type. Topological considerations also suggest a new factor that may contribute to the evolutionary stability of "types". It is shown that if the type is decomposable into factors which are vertex irregular (i.e. have states that are more or less preferred in a random walk), the region of phenotypes representing the type contains islands of strongly preferred states. In other words types have a statistical tendency of retaining evolutionary trajectories within their interior and thus add to the evolutionary persistence of types.

Ensemble-based Control of Search Dynamics with Application to String Optimization

In this paper we demonstrate how ideas from thermodynamics as well as evolutionary biology can be combined to form powerful optimization strategies. These strategies however introduce new parameters to an already parameter dependent optimization task. By testing the introduced strategies with numerous optimization parameter settings for three model problems we develop a semi-automatic parameter adaption which allows an easy control of the free search parameters for potential users.

From Quasispecies to Universal Grammar

The perspective of this paper is to compare mathematical models for the evolutionary dynamics of genomes and languages. The quasispecies equation describes the evolution of genetic sequences under the influence of mutation and selection. A central result is an error threshold which specifies the minimum replication accuracy required for maintaining genetic information of a certain length. The language equation describes the evolution of communication, including the cultural evolution of grammar and the biological evolution of universal grammar. A central result is a coherence threshold which specifies certain conditions that universal grammar has to fulfill in order to induce coherent communication in a population.

Evolution in silico and in vitro: the RNA model

Theoretical concepts and experiments dealing with the evolution of molecules in vitro reached a state that allows for direct applications to the design of biomolecules with predefined properties. RNA evolution in vitro represents a basis for the development of a new and comprehensive model of evolution, focusing on the phenotype and its fitness relevant properties. Relations between genotypes and phenotypes are described by mappings from genotype space onto a space of phenotypes, which are many-to-one and thus give ample room for neutrality as expressed by the existence of extended neutral networks in genotype space. The RNA model reduces genotype-phenotype relations to mappings from sequences into secondary structures of minimal free energies and allows for derivation of otherwise inaccessible quantitative results. Continuity and discontinuity in evolution are defined through a new notion of accessibility in phenotype space that provides a basis for straight forward interpretation of computer simulations on RNA optimization; furthermore, it reveals the constructive role of random genomic drift in the search for phenotypes of higher fitness. The effects of population size on the course of evolutionary optimization can be predicted quantitatively by means of a simple stochastic model based on a birth-anddeath process with immigration.

Rational evolutionary design: the theory of in vitro protein evolution

Directed evolution uses a combination of powerful search techniques to generate proteins with improved properties. Part of the success is due to the stochastic element of random mutagenesis; improvements can be made without a detailed description of the complex interactions that constitute function or stability. However, optimization is not a conglomeration of random processes. Rather, it requires both knowledge of the system that is being optimized and a logical series of techniques that best explores the pathways of evolution (Eigen et al., 1988). The weighing of parameters associated with mutation, recombination, and screening to achieve the maximum fitness improvement is the beginning of rational evolutionary design. The optimal mutation rate is strongly influenced by the finite number of mutants that can be screened. A smooth fitness landscape implies that many mutations can be accumulated without disrupting the fitness. This has the effect of lowering the required library size to sample a higher mutation rate. As the sequence ascends the fitness landscape, the optimal mutation rate decreases as the probability of discovering improved mutations also decreases. Highly coupled regions require that many mutations be simultaneously made to generate a positive mutant. Therefore, positive mutations are discovered at uncoupled positions as the fitness of the parent increases. The benefit of recombination is twofold: it combines good mutations and searches more sequence space in a meaningful way. Recombination is most beneficial when the number of mutants that can be screened is limited and the landscape is of an intermediate ruggedness. The structure of schema in proteins leads to the conclusion that many cut points are required. The number of parents and their sequence identity are determined by the balance between exploration and exploitation. Many disparate parents can explore more space, but at the risk of losing information. The required screening effort is related to the number of uphill paths, which decreases more rapidly for rugged landscapes. Noise in the fitness measurements causes a dramatic increase in the required mutant library size, thus implying a smaller optimal mutation rate. Because of strict limitations on the number of mutants that can be screened, there is motivation to optimize the content of the mutant library. By restricting mutations to regions of the gene that are expected to show improvement, a greater return can be made with the same number of mutants. Initial studies with subtilisin E have shown that structurally tolerant positions tend to be where positive activity mutants are made during directed evolution. Mutant fitness information is produced by the screening step that has the potential to provide insight into the structure of the fitness landscape, thus aiding the setting of experimental parameters. By analyzing the mutant fitness distribution and targeting specific regions of the sequence, in vitro evolution can be accelerated. However, when expediting the search, there is a trade-off between rapid improvement and the quality of the long-term solution. The benefit of neutrality has yet to be captured with in vitro protein evolution. Neutral theory predicts the punctuated emergence of novel structure and function, however, with current methods, the required time scale is not feasible. Utilizing neutral evolution to accelerate the discovery of new functional and structural solutions requires a theory that predicts the behavior of mutational pathways between networks. Because the transition from neutral to adaptive evolution requires a multi-mutational switch, increasing the mutation rate decreases the time required for a punctuated change to occur. By limiting the search to the less coupled region of the sequence (smooth portion of the fitness landscape), the required larger mutation rate can be tolerated. Advances in directed evolution will be achieved when the driving forces behind such proce

Molecular evolution of catalysis

In this paper, we consider the evolutionary dynamics of catalytically active species with a distinct genotype-phenotype relationship. Folding landscapes of RNA molecules serve as a paradigm for this relationship with essential neutral properties. The landscape itself is partitioned by phenotypes (realized as RNA secondary structures). To each genotype (represented as a sequence) a structure is assigned in a unique way. The set of all sequences which map into a particular structure is modeled as a random graph in sequence space (the so-called neutral network). A catalytic network is realized as a random digraph with maximal out-degree two and secondary structures as vertex sets. A population of catalytic RNA molecules shows significantly different behavior compared to a deterministic description: hypercycles are able to co-exist and out-compete a parasite with superior catalytic support. A "switching" between different dynamic organizations of the network can be observed, dynamical stability of hypercyclic organizations against errors and the existence of an error-threshold of catalysis can be reported.

RNA shape space topology

The distinction between continuous and discontinuous transitions is a long-standing problem in the theory of evolution. Because continuity is a topological property, we present a formalism that treats the space of phenotypes as a (finite) topological space, with a topology that is derived from the probabilities with which one phenotype is accessible from another through changes at the genotypic level. The shape space of RNA secondary structures is used to illustrate this approach. We show that evolutionary trajectories are continuous if and only if they follow connected paths in phenotype space.

Neutral evolution of mutational robustness

We introduce and analyze a general model of a population evolving over a network of selectively neutral genotypes. We show that the population's limit distribution on the neutral network is solely determined by the network topology and given by the principal eigenvector of the network's adjacency matrix. Moreover, the average number of neutral mutant neighbors per individual is given by the matrix spectral radius. These results quantify the extent to which populations evolve mutational robustness-the insensitivity of the phenotype to mutations-and thus reduce genetic load. Because the average neutrality is independent of evolutionary parameters-such as mutation rate, population size, and selective advantage-one can infer global statistics of neutral network topology by using simple population data available from in vitro or in vivo evolution. Populations evolving on neutral networks of RNA secondary structures show excellent agreement with our theoretical predictions.

Genotypes with phenotypes: Adventures in an RNA toy world

Evolution has created the complexity of the animate world and deciphering the language of evolution is the key towards understanding nature. The dynamics of evolution is simplified by considering it as a superposition of three less sophisticated processes: population dynamics, population support dynamics, and genotype-phenotype mapping. Evolution of molecules in laboratory assays provides a sufficiently simple system for the quantitative analysis of the three phenomena. Coarse-grained notions of structures like RNA secondary structures are used as model phenotypes. They provide an excellent tool for a comprehensive analysis of the entire complex of molecular evolution. The mapping from RNA genotypes into secondary structures is highly redundant. In order to find at least one sequence for every common structures one need only search a (relatively) small part of sequence space. The existence of selectively neutral phenotypes plays an important role for the the success and the efficiency of evolutionary optimization. Molecular evolution found a highly promising technological application in the design of biomolecules with predefined properties.

Generic properties of combinatory maps: neutral networks of RNA secondary structures

Random graph theory is used to model and analyse the relationships between sequences and secondary structures of RNA molecules, which are understood as mappings from sequence space into shape space. These maps are non-invertible since there are always many orders of magnitude more sequences than structures. Sequences folding into identical structures form neutral networks. A neutral network is embedded in the set of sequences that are compatible with the given structure. Networks are modeled as graphs and constructed by random choice of vertices from the space of compatible sequences. The theory characterizes neutral networks by the mean fraction of neutral neighbors (lambda). The networks are connected and percolate sequence space if the fraction of neutral nearest neighbors exceeds a threshold value (lambda > lambda *). Below threshold (lambda < lambda *), the networks are partitioned into a largest "giant" component and several smaller components. Structures are classified as "common" or "rare" according to the sizes of their pre-images, i.e. according to the fractions of sequences folding into them. The neutral networks of any pair of two different common structures almost touch each other, and, as expressed by the conjecture of shape space covering sequences folding into almost all common structures, can be found in a small ball of an arbitrary location in sequence space. The results from random graph theory are compared to data obtained by folding large samples of RNA sequences. Differences are explained in terms of specific features of RNA molecular structures.

Smoothness within ruggedness: the role of neutrality in adaptation

RNA secondary structure folding algorithms predict the existence of connected networks of RNA sequences with identical structure. On such networks, evolving populations split into subpopulations, which diffuse independently in sequence space. This demands a distinction between two mutation thresholds: one at which genotypic information is lost and one at which phenotypic information is lost. In between, diffusion enables the search of vast areas in genotype space while still preserving the dominant phenotype. By this dynamic the success of phenotypic adaptation becomes much less sensitive to the initial conditions in genotype space.

Landscapes: complex optimization problems and biopolymer structures

The evolution of RNA molecules in replication assays, viroids and RNA viruses can be viewed as an adaptation process on a 'fitness' landscape. The dynamics of evolution is hence tightly linked to the structure of the underlying landscape. Global features of landscapes can be described by statistical measures like number of optima, lengths of walks and correlation functions. The evolution of a quasispecies on such landscapes exhibits three dynamical regimes depending on the replication fidelity: Above the "localization threshold" the population is centered around a (local) optimum. Between localization and "dispersion threshold" the population is still centered around a consensus sequence, which, however, changes in time. For very large mutation rates the population spreads in sequence space like a gas. The critical mutation rates separating the three domains depend strongly on characteristics properties of the fitness landscapes. Statistical characteristics of RNA landscapes are accessible by mathematical analysis and computer calculations on the level of secondary structures: these RNA landscapes belong to the same class as well known optimization problems and simple spin glass models. The notion of a landscape is extended to combinatory maps, thereby allowing for a direct statistical investigation of the sequence structure relationships of RNA at the level of secondary structures. Frequencies of structures are highly non-uniform: we find relatively few common and many rare ones, as expressed by a generalized form of Zipf's law. Using an algorithm for inverse folding we show that sequences sharing the same structure are distributed randomly over sequence space. Together with calculations of structure correlations and a survey of neutral mutations this provides convincing evidence that RNA landscapes are as simple as they could possibly be for evolutionary adaptation: Any desired secondary structure can be found close to an arbitrary initial sequence and at the same time almost all bases can be substituted sequentially without ever changing the shape of the molecule. Consequences of these results for evolutionary optimization, the early stages of life, and molecular biotechnology are discussed.

RNA based evolutionary optimization

The notion of an RNA world has been introduced for a prebiotic scenario that is dominated by RNA molecules and their properties, in particular their capabilities to act as templates for reproduction and as catalysts for several cleavage and ligation reactions of polynucleotides and polypeptides. This notion is used here also for simple experimental assays which are well suited to study evolution in the test tube. In molecular evolution experiments fitness is determined in essence by the molecular structures of RNA molecules. Evidence is presented for adaptation to environment in cell-free media. RNA based molecular evolution experiments have led to interesting spin-offs in biotechnology, commonly called 'applied molecular evolution', which make use of Darwinian trial-and-error strategies in order to synthesize new pharmacological compounds and other advanced materials on a biological basis. Error-propagation in RNA replication leads to formation of mutant spectra called 'quasispecies'. An increase in the error rate broadens the mutant spectrum. There exists a sharply defined threshold beyond which heredity breaks down and evolutionary adaptation becomes impossible. Almost all RNA viruses studied so far operate at conditions close to this error threshold. Quasispecies and error thresholds are important for an understanding of RNA virus evolution, and they may help to develop novel antiviral strategies. Evolution of RNA molecules can be studied and interpreted by considering secondary structures. The notion of sequence space introduces a distance between pairs of RNA sequences which is tantamount to counting the minimal number of point mutations required to convert the sequences into each other. The mean sensitivity of RNA secondary structures to mutation depends strongly on the base pairing alphabet: structures from sequences which contain only one base pair (GC or AU are much less stable against mutation than those derived from the natural (AUGC) sequences. Evolutionary optimization of two-letter sequences in thus more difficult than optimization in the world of natural RNA sequences with four bases. This fact might explain the usage of four bases in the genetic language of nature. Finally we study the mapping from RNA sequences into secondary structures and explore the topology of RNA shape space. We find that 'neutral paths' connecting neighbouring sequences with identical structures go very frequently through entire sequence space. Sequences folding into common structures are found everywhere in sequence space.(ABSTRACT TRUNCATED AT 400 WORDS)

Statistics of RNA secondary structures

A statistical reference for RNA secondary structures with minimum free energies is computed by folding large ensembles of random RNA sequences. Four nucleotide alphabets are used: two binary alphabets, AU and GC, the biophysical AUGC and the synthetic GCXK alphabet. RNA secondary structures are made of structural elements, such as stacks, loops, joints, and free ends. Statistical properties of these elements are computed for small RNA molecules of chain lengths up to 100. The results of RNA structure statistics depend strongly on the particular alphabet chosen. The statistical reference is compared with the data derived from natural RNA molecules with similar base frequencies. Secondary structures are represented as trees. Tree editing provides a quantitative measure for the distance dt, between two structures. We compute a structure density surface as the conditional probability of two structures having distance t given that their sequences have distance h. This surface indicates that the vast majority of possible minimum free energy secondary structures occur within a fairly small neighborhood of any typical (random) sequence. Correlation lengths for secondary structures in their tree representations are computed from probability densities. They are appropriate measures for the complexity of the sequence-structure relation. The correlation length also provides a quantitative estimate for the mean sensitivity of structures to point mutations.

RNA multi-structure landscapes. A study based on temperature dependent partition functions

Statistical properties of RNA folding landscapes obtained by the partition function algorithm (McCaskill 1990) are investigated in detail. The pair correlation of free energies as a function of the Hamming distance is used as a measure for the ruggedness of the landscape. The calculation of the partition function contains information about the entire ensemble of secondary structures as a function of temperature and opens the door to all quantities of thermodynamic interest, in contrast with the conventional minimal free energy approach. A metric distance of structure ensembles is introduced and pair correlations at the level of the structures themselves are computed. Just as with landscapes based on most stable secondary structure prediction, the landscapes defined on the full biophysical GCAU alphabet are much smoother than the landscapes restricted to pure GC sequences and the correlation lengths are almost constant fractions of the chain lengths. Correlation functions for multi-structure landscape exhibit an increased correlation length, especially near the melting temperature. However, the main effect on evolution is rather an effective increase in sampling for finite populations where each sequence explores multiple structures.