chemart / raf

hub:
  repo_type: generator
  builtin: raf
  tags:
  - banzhaf-yamamoto
chemistries:
- id: raf
  name: RAF sets (reflexively autocatalytic, F-generated)
  intuition: '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.

    '
  origin: Hordijk & Steel, 2004-2015
  book: 6.3.1
  refs:
  - '[400]'
  - '[402]'
  - '[599]'
  family: origin-of-life
  kind: analysis
  constructive: false
  S:
    repr: 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
    definition: explicit
  R:
    definition: explicit
    arity: variable
    scheme: '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|'
  A:
    reactor: n/a - static graph analysis
    dilution: n/a
    notes: 'no dynamics: the RAF framework is purely structural. Food molecules are treated as held at
      constant concentration (extras.buffered)'
  params:
  - name: n
    type: int
    default: 7
    min: 1
    max: 14
    range: the papers go to n = 20 on a cluster; n = 8, 10, 12 carry published results
    role: structural
    meaning: maximum polymer length; the system has B^1 + ... + B^n molecules and (n-2) 2^(n+1) + 4 cleavage/ligation
      reactions for B = 2
  - name: t
    type: int
    default: 2
    min: 1
    max: 6
    range: t = 2 throughout the RAF papers, giving |F| = 6 for B = 2
    role: population
    meaning: the food set F is every polymer of length at most t
  - name: B
    type: int
    default: 2
    min: 2
    max: 4
    range: all published RAF results use the binary model B = 2
    role: structural
    meaning: alphabet size of the polymers
  - name: f
    type: float
    default: 1.5
    min: 0
    max: 1000
    range: RAFs appear around f = 1-2 for n up to 20; f(n) = 1.0970 + 0.0189 n gives probability 0.5
    role: structural
    meaning: 'level of catalysis: the average number of reactions catalysed by one molecule, f = p |R|,
      from which the per-pair catalysis probability p is derived'
  - name: irreducible_rafs
    type: int
    default: 1
    min: 0
    max: 100
    role: stochastic
    meaning: how many irreducible RAFs to sample inside the maximal RAF (each run of the deletion search
      can return a different one); 0 skips the search
  - name: reactions
    type: enum
    default: catalysed
    choices:
    - catalysed
    - all
    role: structural
    meaning: 'which reactions of the CRS the returned network contains: only the catalysed ones (the only
      ones an RAF can contain) or every cleavage/ligation pair as well'
  - name: system
    type: dict
    default: {}
    role: structural
    meaning: 'analyse a user-supplied catalytic reaction system instead of the polymer model: {''food'':
      [ids], ''reactions'': [{''id'', ''reactants'', ''products'', ''catalysts'', ''reversible''}]}; empty
      means use the polymer model'
  provides:
  - topology
  - stoichiometry
  - catalysts
  - mass-conservation
  fidelity: reconstructed
  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'
  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.'
  reference_impl: Hordijk's RAF implementation (used for the published simulations); not public
  phenomena:
  - 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
  notes: 'An ANALYSIS to expose alongside chemical organisation theory: it runs on any catalytic reaction
    system (parameter `system`), including the network of `kauffman-autocatalytic-sets`. Note the scope
    limits the authors themselves state: no dynamics, no compartments, no heredity/selection.

    '