Hordijk Wim, Smith Joshua I, Steel Mike
SmartAnalytiX.com, Lausanne, Switzerland.
Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand.
Algorithms Mol Biol. 2015 Apr 28;10:15. doi: 10.1186/s13015-015-0042-8. eCollection 2015.
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.
自催化集被认为是生命起源的基础。此前关于这些集合的存在性和性质的理论及计算工作依赖于一种用于检测化学反应系统中自我维持的自催化集的快速算法。在此，我们引入并应用了该基本算法的一个修改版本及若干扩展：（i）一项旨在减少对算法中计算成本最高部分调用次数的修改；（ii）应用此前引入的基本算法扩展来对反应网络内可能最小的自催化集进行采样，并应用一种统计检验，该检验能给出此类最小集合数量的可能下限；（iii）引入并应用基本算法的另一个扩展，以在分子也能抑制（以及催化）反应的反应系统中检测自催化集；（iv）对搜索自催化集背后理论的进一步、更抽象的扩展。
（i）修改后的算法在对计算成本最高的程序的调用次数方面优于原始算法，在某些情况下这也会使总体运行时间显著缩短；（ii）我们的统计检验有力支持了在一个经过充分研究的聚合物模型中存在大量（甚至数百万个）最小自催化集，这些最小集合平均约有一半的反应是共享的；（iii）在允许抑制的反应系统中可以找到“无抑制”的自催化集，但其数量和大小取决于抑制水平与催化水平的相对关系。
（i）通过使用算法的修改版本，在搜索自催化集时可能会在总体运行时间上得到改善；（ii）大量最小自催化集的存在可能对自催化集的可能进化能力产生重要影响；（iii）只要抑制剂的总数较少，就能有效处理抑制问题。
