How the Dimension of Space Affects the Products of Prebiotic Evolution: The Spatial Population Dynamics of Structural Complexity - PDF

Please download to get full document.

View again

of 10
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report

Graphics & Design


Views: 3 | Pages: 10

Extension: PDF | Download: 0

Related documents
How the Dimension of Space Affects the Products of Prebiotic Evolution: The Spatial Population Dynamics of Structural Complexity Steve T. Piantadosi James P. Crutchfield SFI WORKING PAPER: SFI Working
How the Dimension of Space Affects the Products of Prebiotic Evolution: The Spatial Population Dynamics of Structural Complexity Steve T. Piantadosi James P. Crutchfield SFI WORKING PAPER: SFI Working Papers contain accounts of scientific work of the author(s) and do not necessarily represent the views of the Santa Fe Institute. We accept papers intended for publication in peer-reviewed journals or proceedings volumes, but not papers that have already appeared in print. Except for papers by our external faculty, papers must be based on work done at SFI, inspired by an invited visit to or collaboration at SFI, or funded by an SFI grant. NOTICE: This working paper is included by permission of the contributing author(s) as a means to ensure timely distribution of the scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the author(s). It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may be reposted only with the explicit permission of the copyright holder. SANTA FE INSTITUTE Santa Fe Institute Working Paper 1-9-XXX [] How the Dimension of Space A ects the Products of Pre-Biotic Evolution: The Spatial Population Dynamics of Structural Complexity and The Emergence of Membranes Steve T. Piantadosi 1,,, 3, and James P. Crutchfield 1 Department of Brain and Cognitive Science, Massachusetts Institute of Technology, 43 Vassar Street, Cambridge, MA 139 Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM Complexity Sciences Center and Physics Department, University of California at Davis, One Shields Avenue, Davis, CA (Dated: October 5, 1) We show that autocatalytic networks of -machines and their population dynamics di er substantially between spatial (geographically distributed) and nonspatial (panmixia) populations. Generally, regions of spacetime-invariant autocatalytic networks or domains emerge in geographically distributed populations. These are separated by functional membranes of complementary -machines that actively translate between the domains and are responsible for their growth and stability. We analyze both spatial and nonspatial populations, determining the algebraic properties of the autocatalytic networks that allow for space to a ect the dynamics and so generate autocatalytic domains and membranes. In addition, we analyze populations of intermediate spatial architecture, delineating the thresholds at which spatial memory (information storage) begins to determine the character of the emergent auto-catalytic organization. Keywords: population dynamics, structural complexity, spatial dimension, autocatalytic network PACS numbers: h 87.3.Cc 87.3.Kg a Kd I. INTRODUCTION Almost certainly, the sophisticated mechanisms for self-replication found today in living cells were not present in the earliest replicators [1 3]. Instead, some hypothesized that the first replicators were autocatalytic networks of functional molecules that collectively were capable of self-reproduction [4, 5]. Numerous studies have been devoted to these and analogous networks with the hope of understanding pre-biotic evolution [6 8]. A particular class of such models represented network elements with mathematical constructs, including regular expressions, the -calculus [9], and, recently, -machines [1]. -Machines are especially useful since they support well defined and computable measures of structural complexity [11] and, equally important, these measures extend directly to networks of interacting -machines. Early models often assumed a Turing gas in which every network element has an equal chance of interacting with every other, thereby ignoring a network s spatial configuration. However, natural and engineered evolutionary systems are not architected this way since elements of physical systems always have some spatial relationship that determines which components interact. This observation led to studies of spatial pattern formation in evolutionary and autocatalytic systems [1 14]. Here, we consider networks of single-state Electronic address: Electronic address: -machines a simplifying initial focus that helps to highlight the role of population architecture. We show that the behavior of spatially distributed populations di ers substantially from that of the nonspatial Turing gas. More to the point, we determine the algebraic properties of the network that lead to the emergence of distinctive organizations. II. BACKGROUND -Machines serve as models of stochastic finite and infinite computation [15]. An -machine consists of a set S of causal states and a set of transitions between those states. In the particular variation used here ( -transducers), each transition is labeled by both an input symbol x Aand an output symbol y A. An -machine in state S reads an input symbol x and chooses from all transitions from the one labeled x. The -machine follows the chosen transition to a next state S while emitting the output symbol y corresponding to that transition. In this way, -machines can be viewed as mapping an input language to an output language, perhaps probabilistically. Following Ref. [1], we focus on single-state -machines over the input-output alphabet A = {, 1}. (Results for multi-state -machines appear in a sequel. Our goal here is to highlight the e ects of space, uncomplicated by the richness that comes with using multi-state -machines.) There are 16 such -machines and we denote the set of all them by T. Each -machine can be represented as a binary matrix M, wherem ij = 1 means that the -machine reads in symbol i 1 while emitting symbol j 1. We number the 16 -machines T {T,...,T 15 } by finding the decimal equivalent of the binary number M 11 M 1 M 1 M for each -machine. Thus, for example, -machine T 11 has the matrix representation: apple 1 M =. (1) 1 1 -Machine pairs interact in a population by composition, under which T is closed and forms a monoid [16]. With the matrix representation, -machine composition T b T a is simply matrix multiplication where, after multiplying, any positive matrix element is set to 1. From this, it is straightforward to compute the interaction matrix M, wheret a T b = T c if and only if M a+1,b+1 = c, wherea, b, c {,...,15}: M = III. -MACHINE SOUPS 3. () 7 5 A population, or simply a soup, is a configuration of an n n regular toroidal lattice. At each time t =, 1,,..., every lattice location (i, j) contains a single -machine, denoted t i,j T. The population size is N = n. Each location (i, j) is initialized to contain an -machine uniformly chosen at random from T. The population dynamics is specified by -machine composition, interaction, and update. We define a function : T T T! T by: ( T a T c if T a T c 6= T (T a,t b,t c )=. (3) otherwise T b We write (A, B, C) for sets A, B, C T as shorthand for the set { (a, b, c) :a A, b B,c C}. We must use to prevent the non- -machine T from being produced since the fact that T T a = T a T = T for all T a T implies that if T could be produced, it comes to dominate any population. Each time step t we choose a location (i, j) at random and set: 8 t t t i 1,j, i,j, i+1,j with probability 1 4 t t t t+1 i,j = i+1,j, i,j, i 1,j with probability 1 4 t t t i,j 1, i,j, i,j+1 with probability : 1 4 t t t i,j+1, i,j, i,j 1 with probability 1 4 t+1 (4) and set k,l = t k,l for all (k, l) 6= (i, j). Thus, two vertical or horizontal neighbors to i,j are chosen, composed, and the -machine resulting from their composition is t used to replace i,j, if it is not T. This replacement scheme is meant to be locally analogous to the replacement scheme used in Ref. [1], which will facilitate direct comparisons in the following. In addition, at each time step a certain amount of diffusion of -machines occurs due to spatial mixing. For this, let v be a Gaussian distribution with variance v and mean. At each time step, c -machines are chosen at random in and each is swapped with a random -machine at a distance chosen from the distribution v. For more generality, we allow c to be any real number and swap c -machines per time step on average. When v and c are large, there is considerable spatial mixing and one expects the dynamics to behave like a nonspatial population, where -machines have an equal chance of interacting with every other. However, when v and c are small, there is little spatial mixing and, as we shall see, the population dynamics change substantially. To summarize, as a stochastic dynamical system the soup s state at time t is the population s configuration t. While Eq. (4) determines the local probabilistic update at each site, we use to formally denote the global (probabilistic) update for the entire configuration over one time step: t+1 = t. (5) And so, one goal is to understand the trajectories {, 1,...}. Another is to analyze the structure inside the t. For this, we use bn to denote a spatial shift of the soup configuration: = bn, (6) where bn =( i, j) is the vector by which the configuration is shifted horizontally and vertically: k,l =( bn ) k,l = (i+ i) modn,(j+ j) modn. (7) Finally, we view the population either as a configuration of spatially positioned -machines or as a distribution f of -machine types without regard to spatial location. The fractions f = f 1,...,f 15 of -machines of type T a on are f a ( ) = Pr(T a ). 3 IV. THE PANMIXIA SOUP The least-spatial architecture of, where c N and v n, was previously studied in Ref. [1]. This is the case of a panmixia population, in which all -machines can interact with any other. When the size of is large, f(t) f( t ) follows a simple population dynamics. First, for large N the discrete-time dynamic is well approximated by continuous time, since each discrete time updates only a single lattice location and this means that changes to t and so to f(t) are relatively small (/ N 1 ). Second, the probability of adding an -machine T i is that of picking two -machines T a and T b, such that T a T b = T i, times the probability that the -machine replaced is not T i. Third, the probability of removing an -machine T i is that of picking two -machines, T a and T b, such that T a T b 6= T i and also T a T b 6= T,times the probability of picking a T i to replace. Thus, the rate of change of f i (t) is given by the di erential equation: df i dt = 1 f i X T a T b =T i f a f b f i X f T a T b 6=T i T a T b 6=T a f b, (8) where the sums run over all pairs satisfying their subscripted condition. That is, P T a T b =T i runs over all ordered pairs (T a,t b ) such that T a T b = T i. Equation (8) also determines the steady-state probability distributions of -machine types, which are simply solutions of: f df =. (9) dt t/n FIG. 1: Panmixia population evolution: -Machine-type distribution f as a function of replication time (t/n), with n =1 3, N =1 6, c =3,andv =1. Figure 1 shows the distribution f(t) over -machine types as a function of time (replication) for a simulation with c = 3 and v = 1. This is essentially the same population behavior reported in Ref. [1]. It was confirmed numerically that Eq. (8) closely predicts the results in Fig. 1. In Fig. 1, all 16 single-state -machines -Machine Type T 15 T 3,T 5,T 1,T 1 T 1,T,T 4,T 8 T 6,T 7,T 9,T 11,T 13,T 14 Behavior Class Fast Growth Medium Growth No Growth Fast Decay TABLE I: -Machine-type behavior classes in the panmixia soup of Fig. 1. are shown. They partition themselves into four classes such that those in the same class behave similarly; see Table I. Six -machines die away, while nine persist in a closed, self-maintaining, and dynamically stable metamachine, as shown in Ref. [1]. V. GENERAL REPLICATORS While these -machine classes can be understood by examining the solutions of Eq. (8) as done in Ref. [1], the results can also be directly predicted by examining the algebraic structure of the set T under the composition operator determined by M. And this observation is critical to predicting the behavior of alternate population architectures. First, we address the panmixia population. The central idea is to find subsets of -machine types that map onto themselves under the population dynamics; in other words, to identify M-invariant subsets of T. Definition 1. A set S of -machines is a general replicator (GR) if for all a T we have: and (T,a,S) [ (S, a, T) S [{a} (T,a,S) [ (S, a, T) 6= {a}. This parallels the definition of an ideal in semigroup theory, except that we must be more careful (and less elegant) with the definition since is not a binary relation [16]. In T there are many GRs, including T itself. We intentionally used to exclude the non- -machine T from being considered a GR. By design, T cannot be produced. GRs are important because they are the simplest form of replicator. Suppose S is a GR. As evolution progresses, elements in the soup are replaced with some element of (T,a,S) or (S, a, T). By the definition of a GR, though, (T,a,S) and (S, a, T) contain elements of S and so generally we expect elements of S to produce more elements of S. However, not all GRs are equal since some are subsets of others and therefore are produced more readily. There are, in fact, many GRs in T, but there is one GR, call it, that is minimal in that no subset of is a GR, but every GR contains. (Note that, generally, such a 4 set is not guaranteed to exist in a semigroup with a zero element [16].) Proposition 1. ={T 1,T,T 3,T 4,T 5,T 8,T 1,T 1,T 15 } is the minimal general replicator in T. Proof. By direct verification of Def. 1 and observing that, shortanyoneofits -machines, is not a GR. In the panmixia population, we expect that elements of come to dominate the soup. And this is what is observed in the simulations (Fig. 1 and Table I). While Eq. (8) explains the specific values of f, an understanding of M s structure leads to a direct explanation for why the set Fast Decay is removed from the soup: None of the -machines in Fast Decay are in. VI. THE SPATIAL SOUP The population that we consider next is that of a spatially configured soup where c = or v =. In these limits, no spatial mixing is added to the system and the model behaves essentially as an asynchronous, probabilistic cellular automaton. Specifically, each element is replaced by the composition of two of its neighbors if that composition does not result in T. The pair of neighbors composed is chosen with uniform probability, according to Eq. (4). f t/n FIG. : Spatial population dynamics: -Machine-type distribution f as a function of replication time with n =1 3, N =1 6,andc =. Figure shows the -machine-type distribution f(t) for c = and N = 1 6. Note that initially the population behaves quite similarly to the panmixia case. This is to be expected since the simulations begin with identical initial configurations so at t = the range of possible interactions is e ectively the same for both architectures. As in the panmixia population, elements not in are quickly removed from the soup. By t/n 3.4, however, the populations start to behave di erently. For example, the -machine T 15 that is most readily made in the panmixia case is also readily made in the spatial case, until t/n =3.4, when it begins to be removed from the population. Again, the -Machine Type Early Late T 15 Fast Growth Decay T 3,T 5,T 1,T 1 Medium Growth Decay T,T 4 Logistic Growth Saturation T 1,T 8 No Growth No Growth T 6,T 7,T 9,T 11,T 13,T 14 Fast Decay Removed TABLE II: -Machine-type behavior classes in the twodimensional spatial population for early and late times for Fig.. Early times: t/n 3.4; late times: t/n machines partition themselves into subsets whose elements behave similarly. At early times before t/n = 3.4, these are identical to those seen in the panmixia population except that T and T 4 undergo logistic growth, while T 1 and T 8 do not. Table II summarizes the overall behavior, for both early and late times. More striking than the evolution of the -machine-type distribution f(t), however, are the spatial patterns that emerge in t. Figure 3 shows a 7 7 region of t at increasing times and one 5 5 region at a late time. Regions of T and T 4 form stable domains that grow to dominate the soup. Within a region of T or T 4 there exist -machines that cannot be replaced, typically due to an elastic collision an interaction producing the non- -machine T that, by, simplyleavesthe -machine at the lattice location alone. When a region of T meets a region of T 4, -machines T 1 and T 8 form on the boundary, since T T 4 = T 1 and T 4 T = T 8. Moreover, T 1 T 1 = T 1 and T 8 T 8 = T 8 and so the boundaries are self-sustaining along the interface. The spatial soup exhibits many of the nontrivial spontaneous patternings common to reaction-di usion systems that exhibit Turing instability [17 ]. Finding a set of reaction-di usion partial di erential equations equivalent to this model and the spatial analog of Eq. 8, however, remains an open problem. Over a large number of time steps, the spatial population looks essentially like that at t/n =. in Fig. 3. If enough time passes, though, the soup eventually divides itself into two connected regions of T and of T 4, or one will take over completely. This requires an extremely large number of replications. Which -machine region dominates in the long run appears to be randomly determined. The overall process is highly reminiscent of spinodal decomposition in which a mixed solution separates into stable component phases [1]. A more direct connection to the predictions of that theory awaits further e ort. VII. SPATIAL-REPLICATOR DOMAINS AND THEIR MEMBRANES After time t/n 3.4, the characters of the spatial and panmixia populations begin to diverge substantially, with patterns emerging in the spatial. Those patterns consist of domains of nearly homogeneous -machines of type T or of type T 4. They are separated by domain 5 t/n =.1 t/n =3.4 t/n =9. t/n =. : 7 7 t/n =. : 5 5 FIG. 3: Emergent spatial replicators and their membranes: A 7 7 region of with n =1 3, N =1 6,andc = v =. The last image, however, is of a 5 5 region. Each color corresponds to one of the 16 -machine types: T is green, T 4 is dark gray, T 1 is yellow, T 8 is purple, and T 15 is blue. walls that consist of -machines T 1 and T 8. As we shall see, these walls play the role of functional membranes that actively translate between the domain -machines. To summarize, then, the first observation about the spatial population is that it is completely di erently organized. The persistent set of -machines di ers markedly from those found with panmixia, as do their roles and interactions. Why did they emerge when the population is embedded in space? We can explain the emergence of these structures by defining a mechanism in the interaction network M that a ects the population dynamics when there is su cient spatial memory. This mechanism is called a spatial replicator (SR). Definition. A set S of -machines is a spatial replicator (SR) if (S, S, (S, S, T)) S, (S, S, (T,S,S)) S, ( (S, S, T),S,S) S, and ( (T,S,S),S,S) S. Notice that this is similar to the definition of a GR, except that SRs require two applications of to produce an element of S. Due to this, SRs only replicate when there is spatial information storage: If S is a SR, an element of S must compose with an -machine in T to produce an -machine T y. T y must then compose with an element of S again to produce a new element of S. In the panmixia population there is no notion of adjacency. Therefore, T y does not have an increased chance of interacting with an element of S again. However, space allows a way for SRs to replicate: If by chance a sufficiently large domain of consists only of elements of some SR S, -machines on the domain border will be replaced by elements of (S, S, T) or (T,S,S). Later, these boundary -machines will be replaced with elements of (S, S, (S, S, T)) [ (S, S, (T,S,S)) [ ( (S, S, T),S,S) [ ( (T,S,S),S,S), (1) which are all
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks