22 Sex and symbiogenesis
(ns meme-constructor.adaptation.post-iii5-sex-and-symbiogenesis
(:require [scicloj.kindly.v4.kind :as kind]
[meme-constructor.adaptation.coarseness :as c]
[meme-constructor.adaptation.recombination :as r]
[meme-constructor.figures :as fig]))Post III.5 of Part III, “A Constructor Theory of Adaptation”.
Sex speeds up design only when new small points arise while others are still sweeping; then it was up to 2.5 times faster. A merge of two lineages is not a faster operator: it is a crossover across lineages, and it wins only by importing selection that happened elsewhere.
Mutation varies one constructor. Sex and symbiogenesis make a new constructor out of two. This post reads both as variation constructors and tests them in the toy world of small points. On the way it measures the unit on which selection acts, the genome without sex and the allele with it.
22.1 1. Sex as recombining variation
This section is about sex as recombining variation (AD9), read in the frame of the adaptive synthesis task (C5) of post I.5.
Definition III.5.1 (Recombination). A recombination constructor takes two variants \(a\) and \(b\) from the current population and returns a variant each of whose blocks is the corresponding block of \(a\) or of \(b\). Uniform crossover takes each block from \(a\) or \(b\) with probability 1/2. One-point crossover takes the blocks before a random cut from \(a\) and the rest from \(b\). Mutation follows.
Its law depends on the population only, so variation stays unspecific (A1′). It is strongly structured: it only combines parts that are already present, and under selection those parts have already passed selection once. Relative to it, two variants can be neighbours that no single mutation connects, so it jumps gaps in the ridge of post III.4. Unlike a step of algorithmic variation (C6), its reach depends on the rest of the population.
What is known. The classical results on the advantage of sex:
- without sex the waits for independent points add up
- with sex only the longest counts
- an asexual population searches for all remaining points at once
- so it waits just as long; then each point needs its own sweep
Proposition III.5.2 (Sweeps add, waits do not; Crow & Kimura 1965, Maynard Smith 1971). Take \(k\) small points in independent blocks, with additive log-fitness. Each missing point is found and established as a Poisson process of rate \(\lambda\), and an established point takes time \(\tau\) to reach frequency 1/2. With sex the blocks stay in linkage equilibrium. Without sex \(\lambda\tau \ll 1\), and a point established outside the sweeping genome is lost. Then, with \(H_k\) the harmonic number, the expected time \(T\) until every point is above 1/2 is
\[ \begin{aligned} E[T_\text{sex}] &= \frac{H_k}{\lambda} + \tau, \qquad E[T_\text{asex}] \approx \frac{H_k}{\lambda} + k\tau,\\ R &= \frac{E[T_\text{asex}]}{E[T_\text{sex}]} \approx \frac{H_k + k\lambda\tau}{H_k + \lambda\tau}. \end{aligned} \]
Sketch. With sex, \(T\) is the maximum of \(k\) independent exponential waits plus one sweep, and the maximum has mean \(H_k/\lambda\). Without sex, once \(j\) points are fixed the next is established at rate \((k-j)\lambda\), which gives the same total wait, followed by \(k\) separate sweeps. ∎
So sex needs \(\lambda\tau\) not small, which is Fisher’s condition. For \(\lambda\tau \gg 1\) the asexual assumption fails, since new points arise inside the sweeping clone, and the formula overstates \(R\).
In the toy, a point is hit by a block jump with probability \(u\,2^{-b}\) per copy, for blocks of \(b\) bits. With the relative fixation rate \(r(S)\) of Proposition III.3.2 in post III.3 (Kimura 1962) and \(S = 2N\sigma\) for a haploid population of \(N\) copies,
\[ \lambda = \frac{u}{2^b}\, r(S), \qquad \tau = \frac{\ln\bigl(r(S) - 1\bigr)}{\sigma}, \]
the logistic time from frequency \(1/r(S)\) to 1/2 (r/predict).
22.2 2. The sex-versus-asexual experiment
Conjecture III.5.4 (Sex-versus-asexual experiment (Y8)). The advantage of sex \(R\) is near 1 where \(\lambda\tau\) is small and grows with \(\lambda\tau\), as Proposition III.5.2 says. A small asexual population runs Muller’s ratchet. Refutation: no advantage of recombination at large \(\lambda\tau\). We fixed this prediction before the sweep.
The toy. The landscape of post 5 (pop/make-landscape) has six point blocks of 4 bits, each point worth \(\sigma = 0.1\) in \(F_\text{real}\). Parents are drawn with weight \(e^{F_\text{real}}\) in a Wright–Fisher population of \(N\). The step is pop/reconstruct with only block jumps, \(u = 0.002\). Runs start from the empty variant. \(N\) goes from 50 to 12,800, which moves \(\lambda\tau\) from 0.03 to 25. Asex has one parent; uniform and one-point have two and always recombine. Seeds 1 to 20, cached in results/postIII5/. With recombination off, r/next-generation reproduces run-wf of post III.1 bit for bit (tested). We looked at three seeds per setting while building the model, before fixing the grid.
(def y8-opts
{:k 6 :block-size 4 :sigma 0.1 :u 0.002 :landscape-seed 1
:ns [50 200 800 3200 12800] :modes [:asex :uniform :one-point]
:seeds (vec (range 1 21))
:max-gen {50 20000 200 10000 800 5000 3200 3000 12800 3000}})(def y8 (c/cached "results/postIII5/y8.edn" y8-opts r/y8-sweep))(def mode-colour {:asex "#d95f02" :uniform "#1b9e77" :one-point "#7570b3"})(defn rows-of [mode] (filterv #(= mode (:mode %)) y8))(kind/plotly
{:data (into (vec (for [mode [:asex :uniform :one-point]]
{:type "scatter" :mode "markers" :name (name mode)
:marker {:color (mode-colour mode) :size 10}
:x (mapv :n (rows-of mode)) :y (mapv :median (rows-of mode))}))
[{:type "scatter" :mode "lines" :name "predicted, asex"
:line {:color (mode-colour :asex) :dash "dash"}
:x (mapv :n (rows-of :asex)) :y (mapv :t-asex (rows-of :asex))}
{:type "scatter" :mode "lines" :name "predicted, sex"
:line {:color (mode-colour :uniform) :dash "dash"}
:x (mapv :n (rows-of :asex)) :y (mapv :t-sex (rows-of :asex))}])
:layout {:title "Median time until all 6 points have frequency > 1/2 (seeds 1–20)"
:height 420 :xaxis {:title "N" :type "log"} :yaxis {:title "generations" :type "log"}}})(defn ratio-row [n]
(let [row (fn [mode] (first (filter #(and (= n (:n %)) (= mode (:mode %))) y8)))
a (row :asex) u (row :uniform) o (row :one-point)]
{:n n :lambda-tau (format "%.2f" (:lambda-tau a))
:median-asex (:median a) :median-uniform (:median u) :median-one-point (:median o)
:R-observed (format "%.2f" (/ (:median a) (:median u)))
:R-predicted (format "%.2f" (:ratio a))
:censored (+ (:censored a) (:censored u) (:censored o))}))(def y8-table (mapv ratio-row (:ns y8-opts)))(kind/table y8-table)| n | lambda-tau | median-asex | median-uniform | median-one-point | R-observed | R-predicted | censored |
|---|---|---|---|---|---|---|---|
| 50 | 0.03 | 2043.5 | 1891.0 | 1864.5 | 1.08 | 1.06 | 0 |
| 200 | 0.18 | 768.0 | 591.0 | 523.5 | 1.30 | 1.35 | 0 |
| 800 | 1.01 | 382.0 | 185.0 | 157.0 | 2.06 | 2.46 | 0 |
| 3200 | 5.17 | 250.0 | 99.5 | 98.5 | 2.51 | 4.39 | 0 |
| 12800 | 25.11 | 187.0 | 78.0 | 78.5 | 2.40 | 5.56 | 0 |
Observation III.5.5 (seeds 1–20, table above). No run was censored. \(R\) was 1.08 at \(\lambda\tau = 0.03\) (predicted 1.06, far inside the spread across seeds), 1.30 at 0.18 (predicted 1.35) and 2.06 at 1 (predicted 2.46). Above that it levelled off at 2.5 and 2.4, where the formula, used outside its assumptions, gives 4.4 and 5.6. The sexual times follow \(H_k/\lambda + \tau\) within about 12 % at every \(N\). One-point crossover was as fast as uniform, or slightly faster. The data fit the prediction up to \(\lambda\tau \approx 1\).
The unit on which selection acts. Without sex, a point in one genome competes with a point in another, since only one clone wins. That shows as a negative correlation between “carries point \(i\)” and “carries point \(j\)”, the linkage disequilibrium of Hill and Robertson. r/pair-correlations computes it for pairs of points that both segregate (frequency 0.05 to 0.95), averaged over all generations.
(kind/table
{:column-names ["N" "mean r, asex" "mean r, uniform" "mean r, one-point"]
:row-vectors (vec (for [n (:ns y8-opts)]
(into [n] (for [mode [:asex :uniform :one-point]]
(format "%.3f" (:ld (first (filter #(and (= n (:n %)) (= mode (:mode %))) y8))))))))})| N | mean r, asex | mean r, uniform | mean r, one-point |
|---|---|---|---|
| 50 | -0.011 | -0.008 | 0.002 |
| 200 | -0.120 | 0.000 | 0.002 |
| 800 | -0.190 | 0.000 | 0.000 |
| 3200 | -0.151 | 0.000 | 0.001 |
| 12800 | -0.114 | -0.000 | -0.000 |
Observation III.5.6 (same runs). Without sex the mean correlation is −0.11 to −0.19 for \(N \ge 200\). With either crossover it is within 0.002 of zero. At \(N = 50\) it is −0.01, because two points rarely segregate at the same time. Without sex, points compete as parts of whole genomes; with sex, only with the other patterns of their own block.
- mean correlation −0.11 to −0.19 for N ≥ 200
- a point competes with points in other genomes: only one clone wins
- within 0.002 of zero
- a point competes only with the other patterns of its own block
22.2.1 Muller’s ratchet
Now the population starts with every point and loses them: 15 point blocks of 4 bits, \(\sigma = 0.1\), \(u = 0.01\). The genomic rate of destroying a point is
\[U = 15 \cdot 0.01 \cdot \tfrac{15}{16} \approx 0.14.\]
In Haigh’s (1978) analysis the least-loaded class has about \(N e^{-U/s}\) members, about 13 at \(N = 50\) with \(s = e^{0.1} - 1\). Back mutation is 15 times rarer. The load is the number of missing points. Seeds 1 to 10, 6000 generations, asex against uniform crossover.
(def ratchet-opts
{:k 15 :block-size 4 :sigma 0.1 :u 0.01 :landscape-seed 1
:ns [20 50 200] :modes [:asex :uniform] :seeds (vec (range 1 11))
:generations 6000 :sample 25})(def ratchet (c/cached "results/postIII5/ratchet.edn" ratchet-opts r/ratchet-by-n))(kind/plotly
{:data (vec (for [mode [:asex :uniform] [k dash label] [[:mean-load "solid" "mean load"] [:min-load "dot" "least-loaded genome"]]]
(let [v (get-in ratchet [50 mode])]
{:type "scatter" :mode "lines" :name (str (name mode) ", " label)
:line {:color (mode-colour mode) :dash dash}
:x (:t v) :y (k v)})))
:layout {:title "N = 50: missing points over time (mean of seeds 1–10)" :height 400
:xaxis {:title "generation"} :yaxis {:title "points missing (of 15)" :rangemode "tozero"}}})(defn- avg [xs] (/ (reduce + 0.0 xs) (count xs)))#'meme-constructor.adaptation.post-iii5-sex-and-symbiogenesis/avg(kind/table
{:column-names ["N" "S = 2Nσ" "final mean load, asex" "final min load, asex"
"final mean load, sex" "final min load, sex"]
:row-vectors (vec (for [[n m] ratchet]
[n (* 2 n 0.1)
(format "%.1f" (avg (:final-mean (:asex m)))) (format "%.1f" (avg (:final-min (:asex m))))
(format "%.1f" (avg (:final-mean (:uniform m)))) (format "%.1f" (avg (:final-min (:uniform m))))]))})| N | S = 2Nσ | final mean load, asex | final min load, asex | final mean load, sex | final min load, sex |
|---|---|---|---|---|---|
| 20 | 4.0 | 9.5 | 8.8 | 7.3 | 6.3 |
| 50 | 10.0 | 5.4 | 4.1 | 1.9 | 0.3 |
| 200 | 40.0 | 2.2 | 0.4 | 1.6 | 0.0 |
Observation III.5.7 (seeds 1–10). At \(N = 50\) the asexual least-loaded genome loses about 4 points within 900 generations and then stays near that (mean genome 5.4 missing). With sex it keeps nearly everything (0.3 missing), and the mean load stays at 1.9, near the mutation–selection balance of about 1.3. At \(N = 200\) the ratchet hardly turns. At \(N = 20\), where \(S = 4\), both lose most points (9.5 and 7.3 missing): sex does not rescue a population below the threshold of post III.3. The ratchet is that threshold applied to whole genomes; sex moves it back to single sites. The asexual plateau, where back mutation balances the ratchet, was not predicted.
22.3 3. Symbiogenesis as merging constructors
This section is about symbiogenesis as merging constructors (AD10). Margulis, publishing as Lynn Sagan (1967), argued that mitochondria and plastids descend from free-living bacteria taken up by another cell: two whole constructors became one. Watson (2006) showed that variation which combines pre-adapted material (sex, gene transfer, symbiotic encapsulation) is algorithmically distinct from point mutation: modules are found separately and then composed.
Definition III.5.8 (Merge constructor). Let two lineages \(A\) and \(B\) evolve on separate resources. A merge takes one variant \(a\) of \(A\) and one variant \(b\) of \(B\) and returns a single variant that carries both modules and is copied as one unit from then on. It is unspecific (A1′) as long as the choice of \(a\) and \(b\) does not consult the joint task.
Proposition III.5.9 (A merge is a crossover across lineages). In a genome whose modules occupy fixed, disjoint blocks, the merge of \(a\) and \(b\) equals a one-point crossover of \(a\) and \(b\) at the module boundary. Proof. Both return \(a\) on module A’s blocks and \(b\) on module B’s blocks. ∎
This is nearly trivial, and that is its use. The operator adds nothing that crossover lacks. If a merge beats recombination, the gain lies in the selection that \(a\) and \(b\) underwent before. The information bound (S1′) of post I.5 says the same in bits: a short step can carry much design only if selection paid for it elsewhere.
22.4 4. The symbiogenesis experiment
Conjecture III.5.10 (Symbiogenesis experiment (Y9)). For designs that need two independently working modules, a merge step is faster than mutation and recombination, once the modules can be selected one by one. Refutation: no difference, or the merge is slower.
The toy. Two modules A and B of three point blocks each, \(\sigma = 0.1\) per point, \(u = 0.004\), and 200 births per generation in every process:
Additive joint task: every point counts, so modules can also be selected in the joint population. Synergy: the joint task pays \(6\sigma\) only for the complete pair, so modules can be selected only in the niches. Budget 4000 generations, seeds 1 to 20.
(def y9-opts
{:m 3 :block-size 4 :sigma 0.1 :u 0.004 :n 200 :q 0.02 :landscape-seed 1
:joints [:additive :synergy]
:processes [:asex :uniform :one-point :merge :blind-merge]
:seeds (vec (range 1 21)) :max-gen 4000})(def y9 (c/cached "results/postIII5/y9.edn" y9-opts r/y9-sweep))(kind/plotly
{:data (vec (for [proc (:processes y9-opts)]
{:type "box" :name (name proc) :boxpoints "all" :jitter 0.4
:x (vec (mapcat (fn [j] (repeat 20 (name j))) (:joints y9-opts)))
:y (vec (mapcat (fn [j] (map #(or % 4000)
(:times (first (filter #(and (= j (:joint %)) (= proc (:process %))) y9)))))
(:joints y9-opts)))}))
:layout {:title "Generations until both modules are carried (censored runs at 4000)"
:boxmode "group" :height 440 :yaxis {:title "generations" :rangemode "tozero"}}})(defn superiority
"Fraction of pairs of runs in which xs is faster than ys; ties 1/2."
[xs ys]
(let [f #(or % 4000)]
(/ (reduce + (for [x xs y ys] (let [x (f x) y (f y)] (cond (< x y) 1.0 (= x y) 0.5 :else 0.0))))
(* (count xs) (count ys)))))(kind/table
{:column-names ["joint task" "process" "median" "censored" "merge faster (pairs)"]
:row-vectors (vec (for [row y9]
(let [merge (first (filter #(and (= (:joint row) (:joint %)) (= :merge (:process %))) y9))]
[(name (:joint row)) (name (:process row)) (:median row) (:censored row)
(if (= :merge (:process row)) "–"
(format "%.2f" (superiority (:times merge) (:times row))))])))})| joint task | process | median | censored | merge faster (pairs) |
|---|---|---|---|---|
| additive | asex | 507.5 | 0 | 0.33 |
| additive | uniform | 285.0 | 0 | 0.11 |
| additive | one-point | 253.5 | 0 | 0.06 |
| additive | merge | 626.5 | 0 | – |
| additive | blind-merge | 701.5 | 0 | 0.60 |
| synergy | asex | 4000.0 | 20 | 1.00 |
| synergy | uniform | 4000.0 | 20 | 1.00 |
| synergy | one-point | 4000.0 | 20 | 1.00 |
| synergy | merge | 761.5 | 0 | – |
| synergy | blind-merge | 4000.0 | 20 | 1.00 |
Observation III.5.11 (seeds 1–20).
- Additive joint task. The medians are 508 (asex), 285 (uniform), 254 (one-point), 627 (merge) and 702 (blind merge). The merge was faster than asex in only 33 % of pairs of runs, and faster than crossover in 11 % and 6 %. The refutation condition occurred: the merge was slower.
- Synergy joint task. No run of asex, uniform, one-point or blind merge finished within 4000 generations. All 20 merge runs finished, with a median of 762.
The first result has a simple reason. Each partner population has a quarter of the births, so it finds its points at a quarter of the rate, while a sexual population of 200 already composes points from different lines. The second holds by construction, and the blind merge shows why: the operator fed with unselected partners never assembled the pair. What worked was selection in the niches, carried across by the merge, as Proposition III.5.9 says. Symbiogenesis is not a faster way to vary. It is a way to use selection that happened elsewhere, and it wins exactly where the joint task cannot select the modules one by one.
22.5 5. The unit of competition
Definition III.5.12 (Unit of competition). A substrate type \(U\) is the unit of competition of a selection mechanism if the variants that cannot all be copied from the resource are copies of \(U\): a part of \(U\) succeeds or fails only with the \(U\) that carries it. Without sex \(U\) is the genome, with free recombination the allele at a block, after a merge the merged cell.
Competition (A2) is not a condition of design (post I.5), but where a mechanism that implements selection has it, its unit matters and can be measured: the correlation of Observation III.5.6 reads it off. At the wrong unit it costs. Clonal interference, competition between genomes that each carry a good part, slowed the collection of points by up to a factor of 2.5 (Observation III.5.5).
The merge partners do not compete, since they draw on separate resources. The merged cell then competes with unmerged hosts on the joint resource, so the unit moves one level up.
22.6 Summary
- Recombination is a two-parent variation constructor that does not read the task (A1′).
- Without sex only the sweeps add, not the waits (Proposition III.5.2, after Crow & Kimura 1965 and Maynard Smith 1971). In the sex-versus-asexual experiment (Y8) the advantage of sex rose from 1.08 to about 2.5 with \(\lambda\tau\), and at \(N = 50\) sex stopped Muller’s ratchet.
- Where selection works through competition, its unit is measurable from linkage disequilibrium: the genome without sex, the allele with it. At the wrong unit it slowed design by up to a factor of 2.5.
- A merge is a crossover across lineages (Proposition III.5.9). In the symbiogenesis experiment (Y9) it was slower when the joint task rewarded each module, and the only success when it rewarded only the pair. The gain came from the niches, not the operator.
22.7 Open problems
- Nested sweeps. There is no formula for \(\lambda\tau \gg 1\), where the sketch overstates the advantage about twofold, and none for the plateau of the asexual ratchet.
- A graded unit of competition. Definition III.5.12 treats the unit as all or nothing, while linkage disequilibrium is graded.
- Alternatives for populations. The alternatives condition (D2) is stated for a step relation on single constructors. The reach of recombination and of a merge depends on the rest of the population.
- Other merge set-ups. Each partner got a quarter of the births and modules sat in fixed blocks; other splits and merge rates were not tried.
- Hill–Robertson interference was measured only as linkage disequilibrium, not separated from clonal interference.
- Recombining ideas. The analogue of sex for conjectures held by different people is untested.
22.8 References
- Crow, J. F. & Kimura, M. (1965). Evolution in sexual and asexual populations. American Naturalist 99, 439–450. (verified: bibliographic data and the content of the comparison)
- Felsenstein, J. (1974). The evolutionary advantage of recombination. Genetics 78, 737–756. (verified)
- Fisher, R. A. (1930). The Genetical Theory of Natural Selection. Clarendon Press, Oxford. Chapter VI. (verified: bibliographic data and the content of the argument; paraphrased, not quoted)
- Haigh, J. (1978). The accumulation of deleterious genes in a population: Muller’s ratchet. Theoretical Population Biology 14, 251–267. (verified)
- Hill, W. G. & Robertson, A. (1966). The effect of linkage on limits to artificial selection. Genetical Research 8, 269–294. (verified)
- Kimura, M. (1962). On the probability of fixation of mutant genes in a population. Genetics 47, 713–719. (verified)
- Maynard Smith, J. (1971). What use is sex? Journal of Theoretical Biology 30, 319–335. (verified: bibliographic data)
- Muller, H. J. (1932). Some genetic aspects of sex. American Naturalist 66, 118–138. (verified)
- Muller, H. J. (1964). The relation of recombination to mutational advance. Mutation Research 1, 2–9. doi:10.1016/0027-5107(64)90047-8 (verified)
- Sagan, L. [Margulis, L.] (1967). On the origin of mitosing cells. Journal of Theoretical Biology 14, 225–274. (verified)
- Watson, R. A. (2006). Compositional Evolution: The Impact of Sex, Symbiosis, and Modularity on the Gradualist Framework of Evolution. Vienna Series in Theoretical Biology. MIT Press. (verified)
source: book2/notebooks/meme_constructor/adaptation/post_iii5_sex_and_symbiogenesis.clj