Evolutionary dynamics in a simple model of self-assembly

We investigate the evolutionary dynamics of an idealized model for the robust self-assembly of two-dimensional structures called polyominoes. The model includes rules that encode interactions between sets of square tiles that drive the self-assembly process. The relationship between the model’s rule set and its resulting self-assembled structure can be viewed as a genotype-phenotype map and incorporated into a genetic algorithm. The rule sets evolve under selection for specified target structures. The corresponding complex fitness landscape generates rich evolutionary dynamics as a function of parameters such as the population size, search space size, mutation rate, and method of recombination. Furthermore, these systems are simple enough that in some cases the associated model genome space can be completely characterized, shedding light on how the evolutionary dynamics depends on the detailed structure of the fitness landscape. Finally, we apply the model to study the emergence of the preference for dihedral over cyclic symmetry observed for homomeric protein tetramers.

Figure 1

Illustration of a possible realization of physical polyomino assembly. Square tile building blocks interact with each other through complementary bonding between edges, here illustrated with interacting polymer chains. In addition, tiles experience an attractive interaction to a flat substrate, leading to growing polyomino structures on a surface.

Figure 2

Illustration of polyomino assembly for a rule set with $n_t=4,n_c=7$ and with the nucleus and interaction conventions described in the text. A binary representation of a rule set is translated to nucleus, tile, and interaction information. The nuclei are placed on a lattice in the initiation stage, and growth progresses stochastically, to a final output possessing shape and tile, but not orientational, determinism: The diagonal neighbors of the central tile have two possible orientations, as their 4 edge can bond to either of the two adjacent 3 edges.

Figure 3

(a) Unbound and (b) nondeterministic rule sets. The interactions in this case follow the convention in Eq. (1), so edge types $1$ and $2$ experience an attractive interaction and 0 is neutral. The rule set in (a) consists of one block that is capable of bonding to itself, thus creating an endless chain of repeated blocks. The rule set in (b) contains a block capable of bonding to more than one other, leading to tile nondeterminism depending on which bonding block is added first. In this case, the two different bonding tiles create different structures, leading to shape nondeterminism.

Figure 4

Illustration of some UND polyomino types resulting from growth of genomes with $n_t=2$, $n_c=8$. UND polyominoes form the majority of achievable structures. The two colors label the two different tile types that may be involved in assembly. Letters in brackets denote whether the structures are bound (b), unbound (u), deterministic (d), nondeterministic (nd), space-filling (sf), and periodic in one (1D) or two (2D) dimensions.

Figure 5

$61.1\%$ of the polyominoes that can be grown from genomes with $n_t=2,n_c=8$ are UND structures (X). The rest are bound, deterministic polyominoes. The number of genomes that encode for each polyomino are given; for sets of structures with identical values, each structure occurs the given number of times in genome space. Some structures are given names for ease of reference in the text.

Figure 6

Transitions between polyominoes in the ${\mathcal{S}}_{2,8}\hspace{0.5em}(n_t=2,n_c=8)$ system. (a) The value of a pixel denotes the total number of single-point mutations that result in a change from phenotype $x$ to phenotype $y$ over all genotypes in ${\mathcal{S}}_{2,8}$ that encode $x$ and $y$. (b) The value of a pixel denotes the average proportion of mutations that cause an $x\to y$ transition, where the average is taken over all occurrences of $x$ in ${\mathcal{S}}_{2,8}$. Pixels in the “no transitions” category denote transitions between phenotypes that cannot be accomplished with a single mutation.

Figure 7

Fitness curves during a typical evolutionary run. A population of genomes is evolved toward a structure of size $s⩾16$ using the fitness function in Eq. (2), at $\mu L=0.5$, $R=0$, $N=10$. The plot shows the mean (dashed) and maximal (solid) fitness within a population as time progresses.

Figure 8

Adaptation time $\tau$ (solid lines) and discovery time ${\tau }_D$ (dashed lines) in generations, in ${\mathcal{S}}_{2,8}$ evolving to $s^{*}⩾16$, with mutation rate $\mu$, at different $N$ and with $R=0$.

Figure 9

Fitness curves with time for simulations in ${\mathcal{S}}_{2,8}$ evolving to $s^{*}⩾16$, with $N=80,R=0$ and (a) $\mu L=0.1$, (b) $\mu L=0.5$, and (c) $\mu L=2$. Upper curves show the maximum fitness in the population and lower curves show the mean fitness. Adaptation, defined as the point where $50\%$ or more of the population has maximal fitness, occurred at generations 95 for (a) and 51 for (b). (c) Failed to adapt within the $20\hspace{0.5em}000$-generation cutoff.

Figure 10

Adaptation time $\tau$ (solid lines) and discovery time ${\tau }_D$ (dashed lines) in ${\mathcal{S}}_{6,8}$ evolving to $s^{*}⩾16$, with mutation rate $\mu$, at different $N$ and with $R=0$.

Figure 11

Adaptation time $\tau$ (solid lines) and discovery time ${\tau }_D$ (dashed lines) with random initial conditions in (a) ${\mathcal{S}}_{2,8}$ and (b) ${\mathcal{S}}_{6,8}$, evolving to $s^{*}⩾16$, with mutation rate $\mu$, at different $N$ and with $R=0$.

Figure 12

Adaptation time $\tau$ (solid lines) and discovery time ${\tau }_D$ (dashed lines) with $\epsilon =0.1$ for (a) ${\mathcal{S}}_{2,8}$ and (b) ${\mathcal{S}}_{6,8}$, with zero initial conditions. The increase in ${\tau }_D$ with high $\mu$ for $n_t=6$ has vanished, and all $\tau$ values are lower than the $\epsilon =0$ equivalents.

Figure 13

Illustration of $D_2$ and $C_4$ symmetries in homomeric tetramers.

Figure 14

Transition probabilities for ${{\mathcal{S}}^{\text{'}}}_{1,8}$. (a) Number of self-interacting colors $n_{\mathrm{si}}=2$ and (b) $n_{\mathrm{si}}=4$. (i) Transition probabilities between phenotype $x$ and phenotype $y$. (ii) Transition probabilities represented in a network between phenotypes. The edge widths are proportional to their probability.