How it works

A test rather than a chemistry: given a catalytic reaction system and a food set, is there a self-sustaining subset? A set is reflexively autocatalytic if every reaction in it has a catalyst the set itself can make, and food-generated if every reactant can be built from the food; a RAF is both. The striking result is how cheap this is - the maximal RAF can be found in polynomial time, and the catalysis needed for one to appear grows only linearly with system size rather than exponentially.

S

any catalytic reaction system Q = (X, R, C) plus a designated food set F; by default X = all strings up to length n over an alphabet of size B (Kauffman's binary polymer model) and F = all strings up to length t · explicit

R

a set R' is RA if every reaction in R' has a catalyst in cl_R'(F); F-generated if every reactant of R' is in cl_R'(F); RAF = both. Default reactions: the reversible cleavage/ligation pairs A + B <-> AB of the binary polymer model, each catalysed by molecule E (A + B + E -> AB + E) with probability p = f / |R| · arity variable

A

n/a - static graph analysis · n/a

Parameters

What to look for

• polynomial-time detection of the unique maximal RAF (O(|R|^2 log|R|) worst case, sub-quadratic in practice)
• only LINEAR growth of the catalysis level with system size is needed for RAFs to appear: f(n) = 1.0970 + 0.0189 n at probability 0.5, i.e. 1-2 reactions catalysed per molecule up to n = 20, against Kauffman's exponential expectation
• sharp transition in the probability of a RAF with f: at n = 10 no RAFs at all below f = 1.20 and RAFs almost surely a little above it
• maxRAF size grows linearly with f while the size of an irreducible RAF stays roughly constant; a maxRAF can contain exponentially many irrRAFs

Implementation decisions

• The 2011 (modified) definition is implemented: the RA condition asks for a catalyst in cl_R'(F) rather than in supp(R'), so a reaction catalysed only by a food molecule can be part of an RAF. Hordijk, Kauffman & Steel prove (Lemma 3.1) every RAF of the 2004 definition is one here.
• Cleavage and ligation form a single reversible reaction, as in the model papers, so the closure applies both directions and the F-generated test asks for every reactant AND product of a reaction to be in the closure.
• The level of catalysis f = p |R| is the parameter rather than p, since the published results are stated in f; p = f / |R| is recorded in extras.analysis. Catalysis events are drawn exactly: their number is Binomial(|X||R|, p) and the pairs a uniform subset of that size.
• Only catalysed reactions can belong to an RAF, so by default the network contains just the catalysed reactions (catalyst on both sides, one reaction per catalyst - the 'expanded CRS' of the papers); reactions='all' adds the uncatalysed cleavage/ligation pairs.
• The irrRAF search is the published deletion search (try to remove the reactions of the maxRAF in a random order, keeping any removal whose remaining maxRAF is non-empty); the 2004 paper that first states it is paywalled, so it was reconstructed from its description in the 2013 and 2015 papers.
• Inhibition (u-RAFs, NP-hard in general, fixed-parameter tractable in the number of inhibitors) is not implemented; the v1 parameter allow_inhibition is dropped rather than left as a flag that does nothing.
• No rates and no dilution: the framework is explicitly static. The food set is recorded in extras.food and, since it is assumed freely available, also in extras.buffered.

Sources

• W. Hordijk and M. Steel. Detecting autocatalytic, self-sustaining sets in chemical reaction systems. Journal of Theoretical Biology 227(4):451-461, 2004. https://doi.org/10.1016/j.jtbi.2003.11.020 (paywalled; its definitions, algorithm and results are restated in the open sources below)
• W. Hordijk, S. A. Kauffman and M. Steel. Required levels of catalysis for emergence of autocatalytic sets in models of chemical reaction systems. Int. J. Mol. Sci. 12(5):3085-3101, 2011. https://doi.org/10.3390/ijms12053085 - modified RAF definition (sec. 3.1), the RAF algorithm used here (sec. 3.2), Table 1 and Figures 2-3
• W. Hordijk, J. Hein and M. Steel. Autocatalytic sets and the origin of life. Entropy 12(7):1733-1742, 2010. https://doi.org/10.3390/e12071733 - the 1-2 reactions per molecule result
• M. Steel, W. Hordijk and J. Smith. Minimal autocatalytic networks. J. Theor. Biol. 332:96-107, 2013. arXiv:1212.4450 https://arxiv.org/abs/1212.4450 - maxRAF/subRAF/irrRAF definitions, the algorithm as a fixed point, and the n = 10 size data of Figure 4
• W. Hordijk, J. I. Smith and M. Steel. Algorithms for detecting and analysing autocatalytic sets. Algorithms for Molecular Biology 10:15, 2015. https://doi.org/10.1186/s13015-015-0042-8 - pseudo-RAFs, the irrRAF sampling, and the p values that give P_n = 0.5 for n = 8, 10, 12
• W. Hordijk and M. Steel. Autocatalytic sets extended: dynamics, inhibition, and a generalization. J. Syst. Chem. 3:5, 2012. arXiv:1206.1017 https://arxiv.org/abs/1206.1017 - the worked 4-reaction example and the u-RAF/inhibition results

Banzhaf & Yamamoto, Artificial Chemistries (2015), §6.3.1

Preview at default parameters

254 species · 746 reactions · status complete · seed 1

2 0 + 001 -> 00 + 001
00 + 001 -> 2 0 + 001
2 0 + 010 -> 00 + 010
00 + 010 -> 2 0 + 010
01 + 0 + 1111101 -> 010 + 1111101
010 + 1111101 -> 01 + 0 + 1111101
01 + 1 + 00111 -> 011 + 00111
011 + 00111 -> 01 + 1 + 00111
1 + 01 + 001111 -> 101 + 001111
101 + 001111 -> 1 + 01 + 001111
10 + 1 + 010001 -> 101 + 010001
101 + 010001 -> 10 + 1 + 010001
1 + 10 + 0100110 -> 110 + 0100110
110 + 0100110 -> 1 + 10 + 0100110
11 + 0 + 1010100 -> 110 + 1010100
110 + 1010100 -> 11 + 0 + 1010100
0 + 000 + 101000 -> 0000 + 101000
0000 + 101000 -> 0 + 000 + 101000
000 + 1 + 01010 -> 0001 + 01010
0001 + 01010 -> 000 + 1 + 01010
000 + 1 + 1111111 -> 0001 + 1111111
0001 + 1111111 -> 000 + 1 + 1111111
001 + 0 + 00101 -> 0010 + 00101
0010 + 00101 -> 001 + 0 + 00101
010 + 0 + 100011 -> 0100 + 100011
0100 + 100011 -> 010 + 0 + 100011
0 + 101 + 1010011 -> 0101 + 1010011
0101 + 1010011 -> 0 + 101 + 1010011
01 + 10 + 1001110 -> 0110 + 1001110
0110 + 1001110 -> 01 + 10 + 1001110
01 + 11 + 0111111 -> 0111 + 0111111
0111 + 0111111 -> 01 + 11 + 0111111
1 + 000 + 11 -> 1000 + 11
1000 + 11 -> 1 + 000 + 11
100 + 0 + 1100110 -> 1000 + 1100110
1000 + 1100110 -> 100 + 0 + 1100110
1 + 011 + 0001111 -> 1011 + 0001111
1011 + 0001111 -> 1 + 011 + 0001111
1 + 101 + 00100 -> 1101 + 00100
1101 + 00100 -> 1 + 101 + 00100
… 706 more

Generated by the uploader with chemart push; the hub never runs uploaded code.