Algorithms for detecting and analysing autocatalytic sets
- PDF / 626,284 Bytes
- 17 Pages / 595 x 794 pts Page_size
- 40 Downloads / 165 Views
Hordijk et al. Algorithms for Molecular Biology (2015)10:15 DOI 10.1186/s13015-015-0042-8
RESEARCH
Open Access
Algorithms for detecting and analysing autocatalytic sets Wim Hordijk1* , Joshua I Smith2 and Mike Steel2
Abstract Background: 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 detecting self-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. Results: (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. Conclusions: (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. Keywords: Autocatalytic sets, Algorithms, Origin of life
Background The concept of autocatalytic sets was introduced by Kauffman [1-3] to study the idea of life as a functionally closed and self-sustaining chemical reaction system. This concept is closely related to other such models and ideas [4-7] and is believed to have played a crucial role in the origin of life. It was later formalized mathematically in the form of RAF theory [8-10]. To briefly review RAF theory, we first define a chemical reaction system (CRS) as a tuple (X, R, C) consisting of a set of molecule types X, a set of (possible or allowed) *Correspondence: [email protected] 1 SmartAnalytiX.com, Lausanne, Sw
Data Loading...
