21 Programs that can carry design
(ns meme-constructor.adaptation.post-iii4-design-carrying-programs
(:require [scicloj.kindly.v4.kind :as kind]
[meme-constructor.adaptation.rna :as rna]
[meme-constructor.figures :as fig]))Post III.4 of Part III, “A Constructor Theory of Adaptation”.
An adaptive process can find a design only if there is a ridge: from every level of partial success, some variant one step away does better. Whether the design itself sits in a large neutral network does not matter.
We show this in a small model of RNA folding, where sequences are genotypes, secondary structures are phenotypes, and neutral networks are real. A control map with the same phenotype frequencies but no neighbourhood structure gives no cumulative design. A target whose own neutral network we broke into scattered points was found as fast as a networked target of the same frequency. Model, maps and numbers are ours; the neutral-network picture is Schuster et al.’s (1994).
21.1 1. What a program needs
The design conditions (D1–D3) of post I.5 say what a design is. They do not say which designs a process that only varies and selects can reach.
Conjecture III.4.1 (Design-carrying programs (AD4)). This is post 7’s Conjecture 7.4, read relative to the step relation \(\leadsto_V\) of a variator V. A program can carry design that an adaptive process finds only if (a) its sites lie in information variables, (b) \(\leadsto_V\) is local, and (c) its working variants are connected under \(\leadsto_V\).
- and (b) make alternatives possible: there are variants one step away, and they still run. (c) makes them reachable. Maynard Smith
- put (c) as a word game: WORD, WORE, GORE, GONE, GENE, a meaningful word at every step. In the cumulative-selection proposition (S2) of post I.5 it is a waiting time: a climber is fast if every fitness level has a fair chance of stepping up.
For RNA, Schuster, Fontana, Stadler & Hofacker (1994) found that sequences folding into the same structure form neutral networks: “The sequence space is percolated by extensive neutral networks connecting nearest neighbours folding into identical structures”, with “relatively few common and many rare” structures. Wagner (2005) made this a thesis about evolvability: a large neutral network lets a population spread and meet many new phenotypes. The obvious reading of (c) is then that a design needs a large neutral network of its own. This post tests that reading and finds it wrong.
21.2 2. A small RNA world
A genotype is a sequence of length L over {A, C, G, U}. Its phenotype is the secondary structure of minimum energy in dot-bracket notation, computed by dynamic programming in the style of Zuker & Stiegler (1981). Base-pair maximisation (Nussinov & Jacobson 1980) has too many ties, so we use a small stacking-energy model. Energies are integers, in tenths of a unit:
The parameters are loosely Turner-like, not Turner’s. They were set once, before any walk was run, so that short sequences fold at all.
(mapv (fn [s] (assoc (rna/fold s) :sequence s))
["GGGGAAAACCCC" "GCGCAAAGCGCA" "GGGAAACCCGGGAAACCC" "GGAAAACC" "ACGUACGUACGU"])[{:structure "((((....))))", :energy -58, :sequence "GGGGAAAACCCC"}
{:structure "((((...)))).", :energy -60, :sequence "GCGCAAAGCGCA"}
{:structure "(((...)))(((...)))",
:energy -60,
:sequence "GGGAAACCCGGGAAACCC"}
{:structure "........", :energy 0, :sequence "GGAAAACC"}
{:structure "((((....))))", :energy -48, :sequence "ACGUACGUACGU"}]21.2.1 Exact census at L = 12
At L = 12 all \(4^{12} \approx 1.7 \times 10^7\) sequences can be folded. For every structure the census counts its members, its neutrality (the mean share of a member’s 36 point mutants with the same structure) and the connected components of its neutral network. rna/precompute-y3! wrote it into results/postIII4/.
(def census-12 (rna/load-edn "results/postIII4/census-12.edn"))(defn r3 [x] (if (double? x) (/ (Math/round (* 1000.0 x)) 1000.0) x))(kind/table
{:row-maps (vec (for [s (sort-by :size > (:structures census-12))]
(-> (select-keys s [:structure :size :freq :neutrality :components :largest])
(update-vals r3))))})| structure | size | freq | neutrality | components | largest |
|---|---|---|---|---|---|
| ............ | 11667706 | 0.695 | 0.862 | 1 | 11667706 |
| (((...)))... | 564707 | 0.034 | 0.531 | 8 | 73706 |
| ...(((...))) | 548834 | 0.033 | 0.524 | 8 | 72512 |
| (((....))).. | 534716 | 0.032 | 0.532 | 8 | 75028 |
| ..(((....))) | 524216 | 0.031 | 0.528 | 8 | 74196 |
| .(((...))).. | 355269 | 0.021 | 0.472 | 8 | 49708 |
| ..(((...))). | 353148 | 0.021 | 0.47 | 8 | 49200 |
| .(((....))). | 340312 | 0.02 | 0.47 | 8 | 48504 |
| (((.....))). | 330228 | 0.02 | 0.466 | 8 | 48900 |
| .(((.....))) | 328020 | 0.02 | 0.465 | 8 | 48900 |
| ((((...)))). | 317570 | 0.019 | 0.471 | 16 | 20448 |
| .((((...)))) | 314673 | 0.019 | 0.469 | 16 | 20388 |
| ((((....)))) | 308266 | 0.018 | 0.468 | 16 | 20480 |
| (((......))) | 252132 | 0.015 | 0.446 | 16 | 35133 |
| ((((...)).)) | 19069 | 0.001 | 0.276 | 106 | 1116 |
| ((.((...)))) | 18350 | 0.001 | 0.272 | 106 | 1072 |
Observation III.4.2 (exact, L = 12). There are 16 structures. The open chain takes 70 % of sequence space and is one component. A one-stem structure with \(k\) pairs has \(2^k\) components (8 for three pairs, 16 for four), except one three-pair structure with 16. The two rare structures with a bulge have 106 components each.
The count \(2^k\) has a simple cause.
Proposition III.4.3 (Pair classes split neutral networks). Under single point mutations the six canonical pairs fall into two classes, X = {GC, GU, AU} and Y = {CG, UG, UA}. A point mutation of one base of a pair either keeps the pair in its class or makes it non-canonical. So two members of a neutral network whose \(k\) pairs differ in class pattern are never connected, and the network has at least as many components as class patterns occur among its members, up to \(2^k\).
- GC ↔ GU (C ↔ U)
- GU ↔ AU (G ↔ A)
- CG ↔ UG
- UG ↔ UA
- X with the bases swapped
Proof. GC goes to GU (C to U); GU goes to GC (U to C) or AU (G to A); AU goes to GU (A to G). Every other single-base change of these three pairs gives a non-canonical pair. Y is X with the bases swapped. On a neutral path every pair stays canonical at every step, so it keeps its class. \(\square\)
We have not checked whether this is new. Grüner et al. (1996) enumerated neutral networks exhaustively and studied their components; the split may be there.
The point for design is that connectedness belongs to the step relation, not to the phenotype. A step that swaps the two bases of a pair, one short program, joins all \(2^k\) pieces.
21.3 3. The neutral-network experiment (Y3)
Conjecture III.4.4 (Design needs connected working variants, first form). Adaptive processes find target structures with large neutral networks and do not find isolated ones. A control map with the same phenotype frequencies but no neutral connectivity gives no cumulative design. Refutation: isolated targets are found as fast as networked ones of the same frequency.
Random sampling needs about \(1/f\) draws for a structure of frequency \(f\). Cumulative design means finding a target much faster than that.
Set-up, L = 16. The census uses \(10^7\) uniform random sequences (seed 1). Every structure seen at least 3 times, except the open chain, is a target. Neutrality is measured on up to 20 members per target, and a breadth-first search from 5 members, capped at 1,000 genotypes, checks for small components. Three maps:
Fitness is minus the base-pair distance to the target, the number of pairs in exactly one of the two structures. The step is one point mutation at a uniform site, which knows nothing of the target, so variation is unspecific (A1′). Three processes start from random sequences and stop at the first hit or after \(10^5\) evaluations:
- accepts a mutant only if strictly closer (Chaitin's regime, post I.4)
- accepts if at least as close
- so it drifts on neutral networks
- 30 genotypes, generational, parents by binary tournament
- it has competition (A2)
Seeds 1 to 10 per cell. (rna/precompute-y3! "results/postIII4" {}) takes about three minutes on 16 threads; the post reads its result.
(def y3 (rna/load-edn "results/postIII4/y3-16.edn"))(select-keys y3 [:L :n-sample :n-structures :open-chain-freq :budget :seeds :pop-size :thin]){:L 16,
:n-sample 10000000,
:n-structures 211,
:open-chain-freq 0.3262737,
:budget 100000,
:seeds [1 2 3 4 5 6 7 8 9 10],
:pop-size 30,
:thin 0.02}(def targets (:targets y3))(def target-by-code (into {} (map (juxt :code identity) targets)))(def thin (:thin y3))(defn cells
"Rows of one condition, one per target."
[m process & {:keys [variation fitness] :or {variation :point fitness :graded}}]
(filter #(and (= m (:map %)) (= process (:process %)) (= variation (:variation %))
(= fitness (:fitness % :graded)))
(:rows y3)))(defn eff-freq
"Target frequency on a map: the thinned map keeps a share p."
[m row]
(cond-> (:freq (target-by-code (:target row))) (= m :thinned) (* thin)))(defn band [f] (long (Math/floor (Math/log10 f))))(defn band-table
"Per frequency band: median of 1/f, share of runs that hit, and the
median over targets of the median evaluations."
[conditions]
(vec (for [[b rows-by-cond]
(->> (for [[label m p opts] conditions
row (apply cells m p (mapcat identity opts))]
[label m row])
(group-by (fn [[_ m row]] (band (eff-freq m row))))
(sort-by key))]
(into {:band (str "1e" b)
:targets (count (distinct (map (comp :target last) rows-by-cond)))
:random-search (Math/round (double (rna/median (map (fn [[_ m row]] (/ 1.0 (eff-freq m row))) rows-by-cond))))}
(for [[label rows] (group-by first rows-by-cond)
:let [rs (map last rows)]]
[label (str (Math/round (double (rna/median (map :median rs))))
" (" (Math/round (* 100.0 (/ (reduce + (map :hits rs)) (reduce + (map :runs rs))))) "%)")])))))21.3.1 The census at L = 16
(kind/plotly
{:data [{:type "scatter" :mode "markers" :name "RNA"
:x (mapv :freq targets) :y (mapv :neutrality targets)
:text (mapv :structure targets) :marker {:color "#1f77b4" :size 6}}
{:type "scatter" :mode "lines" :name "control (neutrality = f)"
:x [1e-7 0.03] :y [1e-7 0.03] :line {:color "#d62728" :dash "dash"}}]
:layout {:title "Frequency and neutrality of the target structures, L = 16"
:xaxis {:title "frequency f (10^7 samples)" :type "log"}
:yaxis {:title "neutrality (share of neutral point mutants)" :type "log"}
:height 420}})(let [cs (mapcat :components targets)]
{:targets (count targets)
:neutrality-range [(r3 (apply min (map :neutrality targets))) (r3 (apply max (map :neutrality targets)))]
:bfs-probes (count cs)
:probes-reaching-cap (count (filter #(= (:cap y3) %) cs))
:smallest-component-found (apply min cs)}){:targets 210,
:neutrality-range [0.244 0.552],
:bfs-probes 1050,
:probes-reaching-cap 1048,
:smallest-component-found 720}Observation III.4.5 (sampled census, L = 16, seed 1). There are 211 structures in \(10^7\) samples, the open chain at 33 %. The 210 targets span frequencies from \(3 \times 10^{-7}\) to 0.02. Neutrality rises with frequency, from about 0.25 to 0.55, as Wagner (2005) describes for real RNA, and lies orders of magnitude above the control’s value \(f\). Only 2 of the 1,050 search probes stopped below 1,000 genotypes. The RNA map has no naturally isolated targets at this length, so the thinned map is needed to test isolation at all.
21.3.2 Networked targets and the control
(kind/table
(band-table [["RNA strict" :rna :strict {}]
["RNA weak" :rna :weak {}]
["RNA population" :rna :population {}]
["control weak" :control :weak {}]
["control population" :control :population {}]]))| band | targets | random-search | RNA strict | RNA weak | RNA population | control weak | control population |
|---|---|---|---|---|---|---|---|
| 1e-6 | 2 | 107639 | 100000 (0%) | 4317 (100%) | 21041 (100%) | 100000 (0%) | 59678 (55%) |
| 1e-5 | 35 | 59172 | 100000 (0%) | 3092 (96%) | 13274 (99%) | 100000 (1%) | 36485 (84%) |
| 1e-4 | 76 | 2894 | 100000 (6%) | 451 (99%) | 1065 (100%) | 100000 (7%) | 2592 (100%) |
| 1e-3 | 76 | 232 | 100000 (34%) | 113 (100%) | 162 (100%) | 100000 (38%) | 166 (100%) |
| 1e-2 | 21 | 79 | 100000 (29%) | 68 (100%) | 67 (100%) | 51 (79%) | 43 (100%) |
Each cell is the median over the band’s targets of the median number of evaluations over 10 seeds, with the share of runs that hit in parentheses. A median of 100,000 means that most runs failed.
(defn scatter [label m p colour & opts]
(let [rs (apply cells m p opts)]
{:type "scatter" :mode "markers" :name label
:x (mapv #(/ 1.0 (eff-freq m %)) rs) :y (mapv :median rs)
:text (mapv #(:structure (target-by-code (:target %))) rs)
:marker {:color colour :size 5 :opacity 0.7}}))(def random-line
;; median of a geometric waiting time is about ln 2 / f
{:type "scatter" :mode "lines" :name "random search (median ≈ 0.69/f)"
:x [30 3e6] :y [(* 0.69 30) (* 0.69 3e6)] :line {:color "black" :dash "dot"}})(kind/plotly
{:data [random-line
(scatter "RNA, weak climber" :rna :weak "#1f77b4")
(scatter "RNA, population" :rna :population "#2ca02c")
(scatter "control, population" :control :population "#d62728")
(scatter "thinned target, weak climber" :thinned :weak "#ff7f0e")]
:layout {:title "Evaluations to the target (median over 10 seeds)"
:xaxis {:title "1/f on that map (random-search expectation)" :type "log"}
:yaxis {:title "median evaluations (capped at 10^5)" :type "log"}
:height 480}})Observation III.4.6 (seeds 1–10). On the RNA map the weak climber beats random search, and the gain grows with rarity: 113 evaluations against 232 around \(f = 10^{-3}\), about 3,100 against 59,000 around \(10^{-5}\) (a factor 19), and a factor of about 25 for the two rarest targets. It hits in 96 to 100 % of runs in every band. On the control the population behaves like random search, and the climbers find only common targets: once all 48 neighbours of a genotype have been tried and none is better, nothing changes. The control gives no cumulative design, as predicted.
The strict climber fails on the RNA map too: 0 % hits in the rare bands. From a random start one mutation almost never brings a stem closer, so a climber must cross plateaus of equal distance. Neutral networks are needed, but those of the intermediate structures.
21.3.3 The isolated target
(kind/table
(band-table [["thinned strict" :thinned :strict {}]
["thinned weak" :thinned :weak {}]
["thinned population" :thinned :population {}]]))| band | targets | random-search | thinned strict | thinned weak | thinned population |
|---|---|---|---|---|---|
| 1e-6 | 47 | 265111 | 100000 (0%) | 8622 (88%) | 39121 (84%) |
| 1e-5 | 70 | 46073 | 100000 (1%) | 2330 (99%) | 5113 (100%) |
| 1e-4 | 56 | 5576 | 100000 (3%) | 750 (100%) | 1280 (100%) |
Observation III.4.7 (thinned targets, seeds 1–10). A thinned target has about 0.4 neutral neighbours out of 48. Yet the weak climber finds it as fast as a networked target of the same frequency: around \(pf = 10^{-5}\) it needs about 2,300 evaluations against 46,000 for random search, where networked targets needed about 3,100. It hits in 88 to 100 % of runs. The refutation condition of the neutral-network experiment (Y3) occurred.
The climber does not need the target’s network. It needs to get near the target, and the structures one or two pairs away still have large networks to drift along. The ridge is intact up to the last step, and the last step costs little.
Take the grading away and the ridge goes with it.
Proposition III.4.8 (No ridge, no gain). Under needle fitness, which only tells the target from everything else, no process of this kind beats random search: before the first hit selection cannot tell variants apart, so every evaluated genotype is uniformly distributed. This is the information bound (S1′) of post I.5 in its simplest case, and the needle runs showed nothing else.
Conjecture III.4.10 (Design-carrying programs, restated). Part (c) of the design-carrying-programs conjecture (AD4) should read: for the task T, the variants at every level of accuracy below the design are connected, under \(\leadsto_V\) and through variants of equal accuracy, to variants of higher accuracy. Whether the design itself has a neutral network is irrelevant. We stated this after seeing the result. Test: a landscape that keeps the target’s network but cuts the ridge below it, for example by a moat of worse variants as in the population-competition experiment (X3), should be found only at random-search speed.
- at every level below the design, variants connect to better ones
- through variants of equal accuracy
- test: keep the target's network, cut the ridge with a moat
This is the fitness-level reading of the cumulative-selection proposition (S2): neutral networks at the intermediate levels keep the waiting times \(1/q_i\) small. It corrects the reading of Wagner’s thesis from which we started: evolvability lives on the ridge, not at the target.
21.4 4. Larger steps
Would a larger step replace the ridge? The RNA analogue of an algorithmic step (post I.4) is a stem step: copy the reverse complement of a segment of 3 to 5 bases to another place, one short program that can make a whole stem. The mixed variator does a point mutation or a stem step with probability ½ each.
(kind/table
(band-table [["RNA weak, point" :rna :weak {}]
["RNA weak, mixed" :rna :weak {:variation :mixed}]
["control weak, point" :control :weak {}]
["control weak, mixed" :control :weak {:variation :mixed}]]))| band | targets | random-search | RNA weak, point | RNA weak, mixed | control weak, point | control weak, mixed |
|---|---|---|---|---|---|---|
| 1e-6 | 2 | 107639 | 4317 (100%) | 4941 (100%) | 100000 (0%) | 100000 (0%) |
| 1e-5 | 35 | 59172 | 3092 (96%) | 4147 (94%) | 100000 (1%) | 100000 (14%) |
| 1e-4 | 76 | 2894 | 451 (99%) | 478 (99%) | 100000 (7%) | 100000 (48%) |
| 1e-3 | 76 | 232 | 113 (100%) | 60 (100%) | 100000 (38%) | 252 (89%) |
| 1e-2 | 21 | 79 | 68 (100%) | 57 (100%) | 51 (79%) | 54 (100%) |
(kind/table
(band-table [["thinned weak, point" :thinned :weak {}]
["thinned weak, mixed" :thinned :weak {:variation :mixed}]]))| band | targets | random-search | thinned weak, point | thinned weak, mixed |
|---|---|---|---|---|
| 1e-6 | 47 | 265111 | 8622 (88%) | 13000 (86%) |
| 1e-5 | 70 | 46073 | 2330 (99%) | 2443 (99%) |
| 1e-4 | 56 | 5576 | 750 (100%) | 873 (100%) |
Observation III.4.11 (mixed variation, seeds 1–10). On the RNA map the stem step helps only for common targets (60 against 113 evaluations around \(10^{-3}\)) and costs up to a third for rare ones (about 4,100 against 3,100 around \(10^{-5}\)). On thinned targets it is neutral or slower. On the control it frees the weak climber from its traps, from 7 % to 48 % hits around \(10^{-4}\), but only by drawing far-off genotypes, which is random search again.
The mixed variator contains the point steps, so it connects at least what point mutation connects, at a cost of at most a factor 2. It gains only where the point relation leaves gaps that a short program closes, and on the way to an RNA target there are none. Where there is no ridge, a large step that knows nothing of T can only jump, and jumping is sampling.
21.5 5. Drift, not competition
Observation III.4.12 (same runs). The tournament population needs 1.4 to 5 times as many evaluations as the weak climber in every band with \(f \le 10^{-3}\): about 13,300 against 3,100 around \(10^{-5}\). The strict climber, with neither drift nor a population, fails. The weak climber, with drift and no competition, is best.
A population spends its evaluations on many lines at once. What found the design was selection by the task plus the freedom to drift on neutral networks. This is the RNA version of what the competition experiment (E14) showed in post 7, and it fits post I.5’s reading of competition as a property, not a condition of design.
21.6 Summary
- The design-carrying-programs conjecture (AD4) is read relative to the variator’s step relation. Proposition III.4.3 shows why: point mutation splits an RNA neutral network into up to \(2^k\) pair-class components.
- In a small RNA folding model a weak climber finds rare targets up to 25 times faster than random search. A control map with the same frequencies gives no cumulative design.
- The neutral-network reading failed: a target scattered into isolated points was found as fast as a networked one (Y3). What counts is the ridge below the target (Conjecture III.4.10).
- Stem steps did not replace the ridge. Drift, not competition, carried the gain.
21.7 Open problems
- The moat test of Conjecture III.4.10: keep the target’s network, cut the ridge below it.
- Truly isolated targets. At L = 16 even the rarest structures have large networks. Only \(p = 0.02\) was run; a much smaller \(p\) must at some point make the last step expensive.
- Tasks that grade less generously. Base-pair distance rewards every correct pair. A task that rewards only function, as a ribozyme’s activity does, may have far fewer partly working intermediates.
- Larger models. Our energies, no multiloops and \(L \le 16\) give one- or two-stem structures. Schuster et al. used the full energy model and lengths up to 100.
- Keeping the design found. Whether a lineage keeps it under ongoing mutation, and whether that needs competition, is the open question of post I.5.
21.8 References
- Grüner, W., Giegerich, R., Strothmann, D., Reidys, C., Weber, J., Hofacker, I. L., Stadler, P. F. & Schuster, P. (1996). Analysis of RNA sequence structure maps by exhaustive enumeration I. Neutral networks. Monatshefte für Chemie 127, 355–374. (verified: bibliographic data; its content on components is not checked)
- Maynard Smith, J. (1970). Natural selection and the concept of a protein space. Nature 225, 563–564. (verified in post 7, including the WORD–GENE example)
- Nussinov, R. & Jacobson, A. B. (1980). Fast algorithm for predicting the secondary structure of single-stranded RNA. PNAS 77(11), 6309–6313. doi:10.1073/pnas.77.11.6309 (verified)
- Schuster, P., Fontana, W., Stadler, P. F. & Hofacker, I. L. (1994). From sequences to shapes and back: a case study in RNA secondary structures. Proc. R. Soc. Lond. B 255, 279–284. (verified; the quotations are from its summary, checked against the JSTOR scan)
- Wagner, A. (2005). Robustness and Evolvability in Living Systems. Princeton University Press. (verified: bibliographic data and the book’s topic; no page is cited)
- Zuker, M. & Stiegler, P. (1981). Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Research 9(1), 133–148. (verified)
source: book2/notebooks/meme_constructor/adaptation/post_iii4_design_carrying_programs.clj