Cargando…
Algorithms for detecting and analysing autocatalytic sets
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 detectingself-sustaining autocatalytic sets in chemical reaction systems. Here, we introduc...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
BioMed Central
2015
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4428007/ https://www.ncbi.nlm.nih.gov/pubmed/25969692 http://dx.doi.org/10.1186/s13015-015-0042-8 |
_version_ | 1782370820385931264 |
---|---|
author | Hordijk, Wim Smith, Joshua I Steel, Mike |
author_facet | Hordijk, Wim Smith, Joshua I Steel, Mike |
author_sort | Hordijk, Wim |
collection | PubMed |
description | 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 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. 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. |
format | Online Article Text |
id | pubmed-4428007 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2015 |
publisher | BioMed Central |
record_format | MEDLINE/PubMed |
spelling | pubmed-44280072015-05-13 Algorithms for detecting and analysing autocatalytic sets Hordijk, Wim Smith, Joshua I Steel, Mike Algorithms Mol Biol Research 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 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. 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. BioMed Central 2015-04-28 /pmc/articles/PMC4428007/ /pubmed/25969692 http://dx.doi.org/10.1186/s13015-015-0042-8 Text en © Hordijk et al.; licensee BioMed Central. 2015 This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated. |
spellingShingle | Research Hordijk, Wim Smith, Joshua I Steel, Mike Algorithms for detecting and analysing autocatalytic sets |
title | Algorithms for detecting and analysing autocatalytic sets |
title_full | Algorithms for detecting and analysing autocatalytic sets |
title_fullStr | Algorithms for detecting and analysing autocatalytic sets |
title_full_unstemmed | Algorithms for detecting and analysing autocatalytic sets |
title_short | Algorithms for detecting and analysing autocatalytic sets |
title_sort | algorithms for detecting and analysing autocatalytic sets |
topic | Research |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4428007/ https://www.ncbi.nlm.nih.gov/pubmed/25969692 http://dx.doi.org/10.1186/s13015-015-0042-8 |
work_keys_str_mv | AT hordijkwim algorithmsfordetectingandanalysingautocatalyticsets AT smithjoshuai algorithmsfordetectingandanalysingautocatalyticsets AT steelmike algorithmsfordetectingandanalysingautocatalyticsets |