Editing DNA computing (section)

== History ==
[[Leonard Adleman]] of the [[University of Southern California]] initially developed this field in 1994.<ref name=":11">{{Cite journal | last1 = Adleman | first1 = L. M. | title = Molecular computation of solutions to combinatorial problems | doi = 10.1126/science.7973651 | journal = Science | volume = 266 | issue = 5187 | pages = 1021–1024 | year = 1994 | pmid =  7973651| bibcode = 1994Sci...266.1021A | citeseerx = 10.1.1.54.2565 }} &mdash; The first DNA computing paper. Describes a solution for the directed [[Hamiltonian path problem]]. Also available here: {{cite web |url= http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf |title= Archived copy |access-date= 2005-11-21 |url-status= dead |archive-url= https://web.archive.org/web/20050206144827/http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf |archive-date= 2005-02-06 }}</ref> Adleman demonstrated a [[proof-of-concept]] use of DNA as a form of computation which solved the seven-point [[Hamiltonian path problem]]. Since the initial Adleman experiments, advances have occurred and various [[Turing machine]]s have been proven to be constructible.<ref>{{Cite journal | last1 = Boneh | first1 = D. | last2 = Dunworth | doi = 10.1016/S0166-218X(96)00058-3 | first2 = C. | last3 = Lipton | first3 = R. J. | last4 = Sgall | first4 = J. Í. | title = On the computational power of DNA | journal = Discrete Applied Mathematics | volume = 71 | issue = 1–3 | pages = 79–94 | year = 1996 | doi-access = free }} &mdash; Describes a solution for the [[Boolean satisfiability problem]]. Also available here: {{cite web |url= http://www.cs.tau.ac.il/~kempe/TEACHING/SEMINAR-LENS-SPRING08/boneh95DNAcomputational.pdf |title= Archived copy |access-date=2011-10-14 |url-status= dead |archive-url= https://web.archive.org/web/20120406103849/http://www.cs.tau.ac.il/~kempe/TEACHING/SEMINAR-LENS-SPRING08/boneh95DNAcomputational.pdf |archive-date= 2012-04-06 }}
</ref><ref>{{cite journal |author1=Lila Kari |author2=Greg Gloor |author3=Sheng Yu |date=January 2000 |title=Using DNA to solve the Bounded Post Correspondence Problem |url=http://citeseer.ist.psu.edu/kari00using.html |journal=Theoretical Computer Science |volume=231 |issue=2 |pages=192&ndash;203 |doi=10.1016/s0304-3975(99)00100-0 |doi-access=free}} — Describes a solution for the bounded [[Post correspondence problem]], a hard-on-average NP-complete problem. Also available here: [http://www.csd.uwo.ca/~lila/pdfs/Using%20DNA%20to%20solve%20the%20Bounded%20Post%20Correspondence%20Problem.pdf]</ref>

Since then the field has expanded into several avenues. In 1995, the idea for DNA-based memory was proposed by Eric Baum<ref>{{Cite journal|last=Baum|first=E. B.|date=1995-04-28|title=Building an associative memory vastly larger than the brain|journal=Science|language=en|volume=268|issue=5210|pages=583–585|doi=10.1126/science.7725109|issn=0036-8075|pmid=7725109|bibcode=1995Sci...268..583B|doi-access=free}}</ref> who conjectured that a vast amount of data can be stored in a tiny amount of DNA due to its ultra-high density. This expanded the horizon of DNA computing into the realm of memory technology although the ''in vitro'' demonstrations were made after almost a decade.

The field of DNA computing can be categorized as a sub-field of the broader [[DNA nanotechnology|DNA nanoscience]] field started by Ned Seeman about a decade before Len Adleman's demonstration.<ref>{{Cite journal|last=Seeman|first=Nadrian C.|date=1982-11-21|title=Nucleic acid junctions and lattices|journal=Journal of Theoretical Biology|language=en|volume=99|issue=2|pages=237–247|doi=10.1016/0022-5193(82)90002-9|pmid=6188926|bibcode=1982JThBi..99..237S|issn=0022-5193}}</ref> Ned's original idea in the 1980s was to build arbitrary structures using bottom-up DNA self-assembly for applications in crystallography. However, it morphed into the field of structural DNA self-assembly<ref>{{Cite journal|last1=Tikhomirov|first1=Grigory|last2=Petersen|first2=Philip|last3=Qian|first3=Lulu|date=December 2017|title=Fractal assembly of micrometre-scale DNA origami arrays with arbitrary patterns|url=https://www.nature.com/articles/nature24655|journal=Nature|language=en|volume=552|issue=7683|pages=67–71|doi=10.1038/nature24655|pmid=29219965|bibcode=2017Natur.552...67T|s2cid=4455780|issn=1476-4687}}</ref><ref>{{Cite journal|last1=Wagenbauer|first1=Klaus F.|last2=Sigl|first2=Christian|last3=Dietz|first3=Hendrik|date=December 2017|title=Gigadalton-scale shape-programmable DNA assemblies|url=https://www.nature.com/articles/nature24651|journal=Nature|language=en|volume=552|issue=7683|pages=78–83|doi=10.1038/nature24651|pmid=29219966|bibcode=2017Natur.552...78W|s2cid=205262182|issn=1476-4687}}</ref><ref>{{Cite journal|last1=Ong|first1=Luvena L.|last2=Hanikel|first2=Nikita|last3=Yaghi|first3=Omar K.|last4=Grun|first4=Casey|last5=Strauss|first5=Maximilian T.|last6=Bron|first6=Patrick|last7=Lai-Kee-Him|first7=Josephine|last8=Schueder|first8=Florian|last9=Wang|first9=Bei|last10=Wang|first10=Pengfei|last11=Kishi|first11=Jocelyn Y.|date=December 2017|title=Programmable self-assembly of three-dimensional nanostructures from 10,000 unique components|journal=Nature|language=en|volume=552|issue=7683|pages=72–77|doi=10.1038/nature24648|pmid=29219968|pmc=5786436|bibcode=2017Natur.552...72O|issn=1476-4687}}</ref> which as of 2020 is extremely sophisticated. Self-assembled structure from a few nanometers tall all the way up to several tens of micrometers in size have been demonstrated in 2018.

In 1994, Prof. Seeman's group demonstrated early DNA lattice structures using a small set of DNA components. While the demonstration by Adleman showed the possibility of DNA-based computers, the DNA design was trivial because as the number of nodes in a graph grows, the number of DNA components required in Adleman's implementation would grow exponentially. Therefore, computer scientists and biochemists started exploring tile-assembly where the goal was to use a small set of DNA strands as tiles to perform arbitrary computations upon growth. Other avenues that were theoretically explored in the late 90's include DNA-based security and cryptography,<ref>{{Cite journal|last1=Leier|first1=André|last2=Richter|first2=Christoph|last3=Banzhaf|first3=Wolfgang|last4=Rauhe|first4=Hilmar|date=2000-06-01|title=Cryptography with DNA binary strands|url=http://www.sciencedirect.com/science/article/pii/S0303264700000836|journal=Biosystems|language=en|volume=57|issue=1|pages=13–22|doi=10.1016/S0303-2647(00)00083-6|pmid=10963862|bibcode=2000BiSys..57...13L |issn=0303-2647}}</ref> computational capacity of DNA systems,<ref>{{Cite journal|last1=Guarnieri|first1=Frank|last2=Fliss|first2=Makiko|last3=Bancroft|first3=Carter|date=1996-07-12|title=Making DNA Add|url=https://www.science.org/doi/10.1126/science.273.5272.220|journal=Science|language=en|volume=273|issue=5272|pages=220–223|doi=10.1126/science.273.5272.220|issn=0036-8075|pmid=8662501|bibcode=1996Sci...273..220G|s2cid=6051207}}</ref> DNA memories and disks,<ref>{{Cite journal|last1=Bancroft|first1=Carter|last2=Bowler|first2=Timothy|last3=Bloom|first3=Brian|last4=Clelland|first4=Catherine Taylor|date=2001-09-07|title=Long-Term Storage of Information in DNA|url=https://www.science.org/doi/10.1126/science.293.5536.1763c|journal=Science|language=en|volume=293|issue=5536|pages=1763–1765|doi=10.1126/science.293.5536.1763c|pmid=11556362|s2cid=34699434|issn=0036-8075}}</ref> and DNA-based robotics.<ref name=":10">{{Cite journal|last1=Yin|first1=Peng|last2=Yan|first2=Hao|last3=Daniell|first3=Xiaoju G.|last4=Turberfield|first4=Andrew J.|last5=Reif|first5=John H.|date=2004|title=A Unidirectional DNA Walker That Moves Autonomously along a Track|journal=Angewandte Chemie International Edition|volume=43|issue=37|pages=4906–4911|doi=10.1002/anie.200460522|pmid=15372637|issn=1521-3773}}</ref>

Before 2002, [[Lila Kari]] showed that the DNA operations performed by genetic recombination in some organisms are Turing complete.<ref name=bucke>{{citation|url=http://communications.uwo.ca/com/western_news/profiles/biocomputing_researcher_awarded_the_bucke_prize_20020321435998/ |title=Biocomputing researcher awarded the Bucke Prize |journal=Western News |publisher=[[University of Western Ontario]] |date=March 21, 2002}}</ref>

In 2003, John Reif's group first demonstrated the idea of a DNA-based walker that traversed along a track similar to a line follower robot. They used molecular biology as a source of energy for the walker. Since this first demonstration, a wide variety of DNA-based walkers have been demonstrated.