<p>The origin of life problem is the wide-ranging inquiry into the mechanisms underpinning the emergence of life, where one definition of life is "a self-sustained chemical system capable of undergoing Darwinian evolution" [1].</p>

<p>In one model - the "RNA world" hypothesis [2] - a sea of self-replicating RNA molecules are the precursors to cellular organisms. The mechanism behind the emergence of RNA from the prebiotic chemicals found on earth's surface is an open problem. However, in a series of groundbreaking results, the Sutherland Group at the University of Manchester described a plausible mechanism that combines prebiotic feedstock molecules to yield 2 of the 4 nucleotide types (ribocytidine, ribouridine) found in RNA [3].</p>

<p>From a computational complexity perspective, what can be said in general about the difficulty of reverse-engineering the remaining nucleotides found in RNA? That is, the problem of determining if a desired organic molecule is "reachable" using basic chemical reactions from the set of less-complex molecules thought to be abundant on the earth's surface. Are there any phase transition conditions which would make it easier or harder to reverse engineer a molecule, similar to the phase transitions found in satisfiability problems [4]?</p>

<p>The problem is related to retrosynthetic analysis (for which Elias James Corey received the Nobel Prize in chemistry in 1990) and computer-assisted organic synthesis, however when considering the origins of life, we tend to think of a primitive environment where the available building blocks and plausible pathways leading to good yields are constrained compared to a modern wetlab.</p>

<p>Another approach is the <em>metabolism first</em> model, where cyclical chemical reactions based on small molecules evolve to develop increasingly complex structures.</p>

<p>The generalized, abstract problem of determining reachable outcomes given a set of starting materials and allowable reactions is undecidable when the number of steps is unconstrained and NP-hard when bounded [5]. This observation however does not say how difficult the organic chemistry we actually see in our world is.</p>

<p>In general, basic organic chemistry is not Turing-complete because termination is decidable [6]. However, stochastic chemistry [7] can approximate Turing machines to arbitrary precision [8]. Arbitrary protein structure prediction (protein folding) is known to be NP-complete [9].</p>

<p>There are some machine learning methods for assessing whether or not a particular target compound or drug is likely to be synthesizable [10]. Does this approach say anything about RNA/DNA?</p>

<p>The problem of RNA formation may be completely tractable even if the more general problem of organic synthesis is intractable. This would mirror the situation in physics. Deducing the dynamical equations governing an arbitrary physical system is NP-hard [11], however the physics we encounter in our world is much easier to analyze and appears to be tractable (what has also been called "the unreasonable effectiveness of mathematics in the natural sciences" [12]).</p>

<pre><code>[1] http://originlife.org/
[2] http://en.wikipedia.org/wiki/RNA_world_hypothesis
[3] http://www.nature.com/nature/journal/v459/n7244/full/nature08013.html
[4] http://www.cs.ubc.ca/~kevinlb/papers/2012-PredictingSatisfiability.pdf
[5] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9276&amp;rep=rep1&amp;type=pdf
[6] http://dna.caltech.edu/Papers/sCRN_computation_2008.pdf
[7] http://demonstrations.wolfram.com/DeterministicVersusStochasticChemicalKinetics/
[8] http://lucacardelli.name/Talks/2009-05-08%20Biochemistry%20%28Warsaw%29.pdf
[9] http://www.bentribelhorn.com/files/cs524.pdf
[10] http://www.dtc.umn.edu/publications/reports/2010_02.pdf
[11] http://arxiv.org/pdf/1005.0005.pdf
[12] http://www.dartmouth.edu/~matc/MathDrama/reading/Wigner.html
</code></pre>

CC BY-SA 3.0
2012-06-09T23:45:11.763Z
So you want to say that we have a set of Chemical Materials(Molecules) and Chemical Operations as their operations. We want to derive a specific Molecule like RNA or DNA using these operations from some base or random molecules ?!
Kamran Amini
CC BY-SA 3.0
2012-06-11T15:16:26.607Z
it seems fair to say, as a rough lower bound, this problem is easily at least as hard as the [protein folding problem](http://en.wikipedia.org/wiki/Protein_folding_problem) which has been proven NP complete in somewhat-toy models. and conservatively, the complexity is much harder.
vzn
CC BY-SA 3.0
2012-06-11T15:20:45.790Z
the question also seems vague or poorly defined. "That is, the problem of determining if a desired organic molecule is "reachable" using basic chemical reactions from the set of less-complex molecules thought to be abundant on the earth's surface." but RNA/DNA definitely already fit that definition. they are built out of less complex molecules (than the proteins) that are abundant on earth's surface. actually that definition holds for all biologically-constructed proteins also. therefore, suggest the question be edited/clarified.
vzn
CC BY-SA 3.0
2012-06-11T15:21:28.910Z
I'm uncomfortable with the mix of "computational complexity" (which is a purely mathematical formalization of limiting behavior as problem sizes grow to infinity) and the insistence on "chemistry we actually see in our world".  Without a formal mathematical model of "real world chemistry", which allows for unboundedly complex molecules, the problem isn't well defined.  In particular, the assertion that "basic organic chemistry is decidable" is obviously wrong without _very_ strong assumptions about "basic organic chemistry", like "the number of atoms in the universe is finite".
Jeffε
CC BY-SA 3.0
2012-06-11T15:26:33.223Z
In particular, what excludes [DNA-based Wang tiles](http://www.dna.caltech.edu/~winfree/old_html/Papers/algSA_JBSD.pdf) from "basic organic chemistry"?
Jeffε
CC BY-SA 3.0
2012-06-12T15:47:58.467Z
the actual "origin of life" problem in chemistry/biology as I understand it is more how life could arise incrementally/near _spontaneously_ from chemicals at the earths surface through _random_ recombination/mixing and later, after a small basic complexity in structure is achieved that permits some rudimentary form of "inheritance", principles of evolution, not nec restricted to DNA type inheritance/evolution, but later that arising also.... ie in a sense how the highly ordered/animated structure of life could arise from unanimated materials through billions of years of chance mixing....
vzn
CC BY-SA 3.0
2012-06-12T15:54:07.413Z
in other words this is very borderline TCS question at best and definitely out of scope at worst. see eg [origin of life, chicken and egg problem solved](http://www.wired.com/wiredscience/2010/04/pre-life-paradox/) and [DNA and the Origin of Life:
Information, Specification, and Explanation](http://www.discovery.org/articleFiles/PDFs/DNAPerspectives.pdf) by steven c myer
vzn
CC BY-SA 3.0
2012-06-12T15:56:24.227Z
there _may_ be some TCS related questions related to the "origin of life" problem eg in protein folding dynamics, chemical reactions, DNA etc but the exact question has to be very carefully defined....
vzn
<cc.complexity-theory><big-picture><natural-computing><bioinformatics>
How hard is the origin of life problem?
Jim G
# How hard is the origin of life problem?

(Asked by: username_0 on 2012-06-07)

The origin of life problem is the wide-ranging inquiry into the mechanisms underpinning the emergence of life, where one definition of life is "a self-sustained chemical system capable of undergoing Darwinian evolution" [1].
In one model - the "RNA world" hypothesis [2] - a sea of self-replicating RNA molecules are the precursors to cellular organisms. The mechanism behind the emergence of RNA from the prebiotic chemicals found on earth's surface is an open problem. However, in a series of groundbreaking results, the Sutherland Group at the University of Manchester described a plausible mechanism that combines prebiotic feedstock molecules to yield 2 of the 4 nucleotide types (ribocytidine, ribouridine) found in RNA [3].
From a computational complexity perspective, what can be said in general about the difficulty of reverse-engineering the remaining nucleotides found in RNA? That is, the problem of determining if a desired organic molecule is "reachable" using basic chemical reactions from the set of less-complex molecules thought to be abundant on the earth's surface. Are there any phase transition conditions which would make it easier or harder to reverse engineer a molecule, similar to the phase transitions found in satisfiability problems [4]?
The problem is related to retrosynthetic analysis (for which Elias James Corey received the Nobel Prize in chemistry in 1990) and computer-assisted organic synthesis, however when considering the origins of life, we tend to think of a primitive environment where the available building blocks and plausible pathways leading to good yields are constrained compared to a modern wetlab.
Another approach is the metabolism first model, where cyclical chemical reactions based on small molecules evolve to develop increasingly complex structures.
The generalized, abstract problem of determining reachable outcomes given a set of starting materials and allowable reactions is undecidable when the number of steps is unconstrained and NP-hard when bounded [5]. This observation however does not say how difficult the organic chemistry we actually see in our world is.
In general, basic organic chemistry is not Turing-complete because termination is decidable [6]. However, stochastic chemistry [7] can approximate Turing machines to arbitrary precision [8]. Arbitrary protein structure prediction (protein folding) is known to be NP-complete [9].
There are some machine learning methods for assessing whether or not a particular target compound or drug is likely to be synthesizable [10]. Does this approach say anything about RNA/DNA?
The problem of RNA formation may be completely tractable even if the more general problem of organic synthesis is intractable. This would mirror the situation in physics. Deducing the dynamical equations governing an arbitrary physical system is NP-hard [11], however the physics we encounter in our world is much easier to analyze and appears to be tractable (what has also been called "the unreasonable effectiveness of mathematics in the natural sciences" [12]).
[1] http://originlife.org/
[2] http://en.wikipedia.org/wiki/RNA_world_hypothesis
[3] http://www.nature.com/nature/journal/v459/n7244/full/nature08013.html
[4] http://www.cs.ubc.ca/~kevinlb/papers/2012-PredictingSatisfiability.pdf
[5] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9276&rep=rep1&type=pdf
[6] http://dna.caltech.edu/Papers/sCRN_computation_2008.pdf
[7] http://demonstrations.wolfram.com/DeterministicVersusStochasticChemicalKinetics/
[8] http://lucacardelli.name/Talks/2009-05-08%20Biochemistry%20%28Warsaw%29.pdf
[9] http://www.bentribelhorn.com/files/cs524.pdf
[10] http://www.dtc.umn.edu/publications/reports/2010_02.pdf
[11] http://arxiv.org/pdf/1005.0005.pdf
[12] http://www.dartmouth.edu/~matc/MathDrama/reading/Wigner.html

**Tags:** cc.complexity-theory, big-picture, natural-computing, bioinformatics

> **Comments:**
> **username_1**: So you want to say that we have a set of Chemical Materials(Molecules) and Chemical Operations as their operations. We want to derive a specific Molecule like RNA or DNA using these operations from some base or random molecules ?!  
> **username_2**: it seems fair to say, as a rough lower bound, this problem is easily at least as hard as the [protein folding problem](http://en.wikipedia.org/wiki/Protein_folding_problem) which has been proven NP complete in somewhat-toy models. and conservatively, the complexity is much harder.  
> **username_2**: the question also seems vague or poorly defined. "That is, the problem of determining if a desired organic molecule is "reachable" using basic chemical reactions from the set of less-complex molecules thought to be abundant on the earth's surface." but RNA/DNA definitely already fit that definition. they are built out of less complex molecules (than the proteins) that are abundant on earth's surface. actually that definition holds for all biologically-constructed proteins also. therefore, suggest the question be edited/clarified.  
> **username_3**: I'm uncomfortable with the mix of "computational complexity" (which is a purely mathematical formalization of limiting behavior as problem sizes grow to infinity) and the insistence on "chemistry we actually see in our world".  Without a formal mathematical model of "real world chemistry", which allows for unboundedly complex molecules, the problem isn't well defined.  In particular, the assertion that "basic organic chemistry is decidable" is obviously wrong without _very_ strong assumptions about "basic organic chemistry", like "the number of atoms in the universe is finite".  
> **username_3**: In particular, what excludes [DNA-based Wang tiles](http://www.dna.caltech.edu/~winfree/old_html/Papers/algSA_JBSD.pdf) from "basic organic chemistry"?  
> **username_2**: the actual "origin of life" problem in chemistry/biology as I understand it is more how life could arise incrementally/near _spontaneously_ from chemicals at the earths surface through _random_ recombination/mixing and later, after a small basic complexity in structure is achieved that permits some rudimentary form of "inheritance", principles of evolution, not nec restricted to DNA type inheritance/evolution, but later that arising also.... ie in a sense how the highly ordered/animated structure of life could arise from unanimated materials through billions of years of chance mixing....  
> **username_2**: in other words this is very borderline TCS question at best and definitely out of scope at worst. see eg [origin of life, chicken and egg problem solved](http://www.wired.com/wiredscience/2010/04/pre-life-paradox/) and [DNA and the Origin of Life: Information, Specification, and Explanation](http://www.discovery.org/articleFiles/PDFs/DNAPerspectives.pdf) by steven c myer  
> **username_2**: there _may_ be some TCS related questions related to the "origin of life" problem eg in protein folding dynamics, chemical reactions, DNA etc but the exact question has to be very carefully defined....  

---

## 0 answers

