Algorithms for detecting and analysing autocatalytic sets
Tóm tắt
Autocatalytic sets are considered to be fundamental to the origin of life. Prior theoretical and computational work on the existence and properties of these sets has relied on a fast algorithm for detectingself-sustaining autocatalytic sets in chemical reaction systems. Here, we introduce and apply a modified version and several extensions of the basic algorithm: (i) a modification aimed at reducing the number of calls to the computationally most expensive part of the algorithm, (ii) the application of a previously introduced extension of the basic algorithm to sample the smallest possible autocatalytic sets within a reaction network, and the application of a statistical test which provides a probable lower bound on the number of such smallest sets, (iii) the introduction and application of another extension of the basic algorithm to detect autocatalytic sets in a reaction system where molecules can also inhibit (as well as catalyse) reactions, (iv) a further, more abstract, extension of the theory behind searching for autocatalytic sets. (i) The modified algorithm outperforms the original one in the number of calls to the computationally most expensive procedure, which, in some cases also leads to a significant improvement in overall running time, (ii) our statistical test provides strong support for the existence of very large numbers (even millions) of minimal autocatalytic sets in a well-studied polymer model, where these minimal sets share about half of their reactions on average, (iii) “uninhibited” autocatalytic sets can be found in reaction systems that allow inhibition, but their number and sizes depend on the level of inhibition relative to the level of catalysis. (i) Improvements in the overall running time when searching for autocatalytic sets can potentially be obtained by using a modified version of the algorithm, (ii) the existence of large numbers of minimal autocatalytic sets can have important consequences for the possible evolvability of autocatalytic sets, (iii) inhibition can be efficiently dealt with as long as the total number of inhibitors is small.
Tài liệu tham khảo
Kauffman SA. Cellular homeostasis, epigenesis and replication in randomly aggregated macromolecular systems. J Cybernet. 1971; 1(1):71–96.
Kauffman SA. Autocatalytic sets of proteins. J Theor Biol. 1986; 119:1–24.
Kauffman SA. The Origins of Order. Oxford University Press: New York; 1993.
Gánti T. The Principles of Life. Oxford University Press: New York; 2003.
Eigen M, Schuster P. The Hypercycle. Springer: Berlin; 1979.
Maturana H, Varela F. Autopoiesis and Cognition: The Realization of the Living. Dordrecht: Reidel; 1980.
Dyson FJ. Origins of Life. Cambridge University Press: Cambridge; 1985.
Steel M. The emergence of a self-catalysing structure in abstract origin-of-life models. Appl Math Lett. 2000; 3:91–5.
Hordijk W, Steel M. Detecting autocatalytic, self-sustaining sets in chemical reaction systems. J Theor Biol. 2004; 227(4):451–61.
Hordijk W, Steel M, Kauffman S. Autocatalytic sets: The origin of life, evolution, and functional organization In: Pontarotti P, editor. Evolutionary Biology: Exobiology and Evolutionary Mechanisms. Springer: Berlin Heidelberg: 2013. p. 49–60.
Hordijk W, Kauffman SA, Steel M. Required levels of catalysis for emergence of autocatalytic sets in models of chemical reaction systems. Int J Mol Sci. 2011; 12(5):3085–101.
Hordijk W, Steel M. Predicting template-based catalysis rates in a simple catalytic reaction model. J Theor Biol. 2012; 295:132–8.
Kayala MA, Azencott C-A, Chen JH, Baldi P. Learning to predict chemical reactions. J Chem Inform Model. 2011; 51:2209–22.
Filisetti A, Graudenzi A, Serra R, Villani M, De Lucrezia D, Füchslin RM, et al. A stochastic model of the emergence of autocatalytic cycles. J Syst Chem. 2011; 2:2.
Vasas V, Fernando C, Santos M, Kauffman S, Sathmáry E. Evolution before genes. Biol Direct. 2012; 7:1.
Mossel E, Steel M. Random biochemical networks: The probability of self-sustaining autocatalysis. J Theor Biol. 2005; 233(3):327–36.
Hordijk W, Hein J, Steel M. Autocatalytic sets and the origin of life. Entropy. 2010; 12(7):1733–42.
Hordijk W, Wills PR, Steel M. Autocatalytic sets and biological specificity. Bull Math Biol. 2014; 76(1):201–24.
Smith J, Steel M, Hordijk W. Autocatalytic sets in a partitioned biochemical network. J Syst Chem. 2014; 5:2.
Hordijk W, Hasenclever L, Gao J, Mincheva D, Hein J. An investigation into irreducible autocatalytic sets and power law distributed catalysis. Nat Comput. 2014; 13(3):287–96.
Hordijk W, Steel M, Kauffman S. The structure of autocatalytic sets: Evolvability, enablement, and emergence. Acta Biotheoretica. 2012; 60(4):379–92.
Sievers D, von Kiedrowski G. Self-replication of complementary nucleotide-based oligomers. Nature. 1994; 369:221–4.
Ashkenasy G, Jegasia R, Yadav M, Ghadiri MR. Design of a directed molecular network. PNAS. 2004; 101(30):10872–7.
Lincoln TA, Joyce GE. Self-sustained replication of an RNA enzyme. Science. 2009; 323:1229–32.
Vaidya N, Manapat ML, Chen IA, Xulvi-Brunet R, Hayden EJ, Lehman N. Spontaneous network formation among cooperative RNA replicators. Nature. 2012; 491:72–7.
Hordijk W, Steel M. A formal model of autocatalytic sets emerging in an RNA replicator system. J Syst Chem. 2013; 4:3.
Sousa FL, Hordijk W, Steel M, Martin WF. Autocatalytic sets in the metabolic network of E. coli. J Syst Chem. 2015; 6:4.
Dittrich P, Speroni di Fenizio P. Chemical organisation theory. Bull Math Biol. 2007; 69:1199–231.
Steel M, Hordijk W, Smith J. Minimal autocatalytic networks. J Theor Biol. 2013; 332:96–107.
Bloom D. A birthday problem. Am Math Monthly. 1973; 80:1141–2.
Hordijk W, Steel M. Autocatalytic sets extended: Dynamics, inhibition, and a generalization. J Syst Chem. 2012; 3:5.
Dowling WF, Gallier JH. Linear-time algorithms for testing the satisfiability of propositional Horn formulae. Logic Program. 1984; 3:267–84.