DNA computing: Difference between revisions

Revision as of 15:08, 22 February 2023

Revision as of 14:43, 25 February 2023

Line 3:

'''DNA computing''' is an emerging branch of [[unconventional computing]] which uses [[DNA]], [[biochemistry]], and [[molecular biology]] hardware, instead of the traditional [[electronic computing]]. Research and development in this area concerns theory, experiments, and applications of DNA computing. Although the field originally started with the demonstration of a computing application by [[Leonard Adleman|Len Adleman]] in 1994, it has now been expanded to several other avenues such as the development of storage technologies,<ref name=":7">{{Cite journal|last1=Church|first1=G. M.|last2=Gao|first2=Y.|last3=Kosuri|first3=S.|date=2012-08-16|title=Next-Generation Digital Information Storage in DNA|journal=Science|volume=337|issue=6102|pages=1628|doi=10.1126/science.1226355|pmid=22903519|bibcode=2012Sci...337.1628C|s2cid=934617|issn=0036-8075|doi-access=free}}</ref><ref>{{Cite journal|last1=Erlich|first1=Yaniv|last2=Zielinski|first2=Dina|date=2017-03-02|title=DNA Fountain enables a robust and efficient storage architecture|journal=Science|volume=355|issue=6328|pages=950–954|doi=10.1126/science.aaj2038|pmid=28254941|bibcode=2017Sci...355..950E|s2cid=13470340|issn=0036-8075|url=https://zenodo.org/record/889697}}</ref><ref>{{Cite journal|last1=Organick|first1=Lee|last2=Ang|first2=Siena Dumas|last3=Chen|first3=Yuan-Jyue|last4=Lopez|first4=Randolph|last5=Yekhanin|first5=Sergey|last6=Makarychev|first6=Konstantin|last7=Racz|first7=Miklos Z.|last8=Kamath|first8=Govinda|last9=Gopalan|first9=Parikshit|last10=Nguyen|first10=Bichlien|last11=Takahashi|first11=Christopher N.|date=March 2018|title=Random access in large-scale DNA data storage|url=https://www.nature.com/articles/nbt.4079|journal=Nature Biotechnology|language=en|volume=36|issue=3|pages=242–248|doi=10.1038/nbt.4079|pmid=29457795|s2cid=205285821|issn=1546-1696}}</ref> nanoscale imaging modalities,<ref>{{Cite journal|last1=Shah|first1=Shalin|last2=Dubey|first2=Abhishek K.|last3=Reif|first3=John|date=2019-04-10|title=Programming Temporal DNA Barcodes for Single-Molecule Fingerprinting|journal=Nano Letters|volume=19|issue=4|pages=2668–2673|doi=10.1021/acs.nanolett.9b00590|pmid=30896178|bibcode=2019NanoL..19.2668S|s2cid=84841635|issn=1530-6984}}</ref><ref>{{Cite journal|last1=Sharonov|first1=Alexey|last2=Hochstrasser|first2=Robin M.|date=2006-12-12|title=Wide-field subdiffraction imaging by accumulated binding of diffusing probes|journal=Proceedings of the National Academy of Sciences|language=en|volume=103|issue=50|pages=18911–18916|doi=10.1073/pnas.0609643104|issn=0027-8424|pmid=17142314|pmc=1748151|bibcode=2006PNAS..10318911S|doi-access=free}}</ref><ref name=":8">{{Cite journal|last1=Jungmann|first1=Ralf|last2=Avendaño|first2=Maier S.|last3=Dai|first3=Mingjie|last4=Woehrstein|first4=Johannes B.|last5=Agasti|first5=Sarit S.|last6=Feiger|first6=Zachary|last7=Rodal|first7=Avital|last8=Yin|first8=Peng|date=May 2016|title=Quantitative super-resolution imaging with qPAINT|journal=Nature Methods|language=en|volume=13|issue=5|pages=439–442|doi=10.1038/nmeth.3804|pmid=27018580|pmc=4941813|issn=1548-7105}}</ref> synthetic controllers and reaction networks,<ref name=":0">{{Cite journal|last1=Shah|first1=Shalin|last2=Wee|first2=Jasmine|last3=Song|first3=Tianqi|last4=Ceze|first4=Luis|last5=Strauss|first5=Karin|last6=Chen|first6=Yuan-Jyue|last7=Reif|first7=John|date=2020-05-04|title=Using Strand Displacing Polymerase To Program Chemical Reaction Networks|journal=Journal of the American Chemical Society|volume=142|issue=21|pages=9587–9593|doi=10.1021/jacs.0c02240|pmid=32364723|s2cid=218504535|issn=0002-7863}}</ref><ref name=":1">{{Cite journal|last1=Chen|first1=Yuan-Jyue|last2=Dalchau|first2=Neil|last3=Srinivas|first3=Niranjan|last4=Phillips|first4=Andrew|last5=Cardelli|first5=Luca|last6=Soloveichik|first6=David|last7=Seelig|first7=Georg|date=October 2013|title=Programmable chemical controllers made from DNA|journal=Nature Nanotechnology|language=en|volume=8|issue=10|pages=755–762|doi=10.1038/nnano.2013.189|pmid=24077029|pmc=4150546|bibcode=2013NatNa...8..755C|issn=1748-3395}}</ref><ref name=":2">{{Cite journal|last1=Srinivas|first1=Niranjan|last2=Parkin|first2=James|last3=Seelig|first3=Georg|last4=Winfree|first4=Erik|last5=Soloveichik|first5=David|date=2017-12-15|title=Enzyme-free nucleic acid dynamical systems|journal=Science|language=en|volume=358|issue=6369|pages=eaal2052|doi=10.1126/science.aal2052|issn=0036-8075|pmid=29242317|doi-access=free}}</ref><ref name=":3">{{Cite journal|last1=Soloveichik|first1=David|last2=Seelig|first2=Georg|last3=Winfree|first3=Erik|date=2010-03-23|title=DNA as a universal substrate for chemical kinetics|journal=Proceedings of the National Academy of Sciences|language=en|volume=107|issue=12|pages=5393–5398|doi=10.1073/pnas.0909380107|issn=0027-8424|pmid=20203007|pmc=2851759|bibcode=2010PNAS..107.5393S|doi-access=free}}</ref> etc.

== History ==

== A brief history of DNA computing and molecular programming ==

[[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}} &#x2014; 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>

Line 9:

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 almost after a decade.

The field of DNA computing can be categorized as a sub-field of the broader [[DNA nanotechnology|DNA nanoscience]] field started by [http://seemanlab4.chem.nyu.edu/ 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 scientist 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|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>