Content deleted Content added
m Use div col |
m Open access bot: pmc updated in citation with #oabot. |
||
| (42 intermediate revisions by 23 users not shown) | |||
Line 1:
{{Short description|Computing using molecular biology hardware}}
[[File:DNA orbit animated.gif|thumb|The biocompatible computing device: Deoxyribonucleic acid (DNA)]]
'''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|pmc=3581509}}</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|url-access=subscription}}</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|author5-link=Karin Strauss|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 ==
[[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 }} — 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 }} — Describes a solution for the [[
</ref><ref>{{cite journal |author1=
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
The field of DNA computing can be categorized as a sub-field of the broader [[DNA nanotechnology|DNA nanoscience]] field started by
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
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, [https://users.cs.duke.edu/~reif/ 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.▼
▲In 2003,
== Applications, examples, and recent developments ==
In 1994 [[Leonard Adleman]] presented the first prototype of a DNA computer. The [[:de:TT-100|TT-100]] was a test tube filled with 100 microliters of a DNA solution. He managed to solve an instance of the directed [[Hamiltonian path]] problem.<ref>Braich, Ravinderjit S., et al. "Solution of a satisfiability problem on a gel-based DNA computer." ''DNA Computing''. Springer Berlin Heidelberg, 2001. 27-42.</ref> In Adleman's experiment, the Hamiltonian Path Problem was implemented notationally as
=== Combinatorial problems ===
First results to these problems were obtained by [[Leonard Adleman]].
* In 1994: Solving a [[Hamiltonian path problem|Hamiltonian path]] in a graph with
* In 2002: Solving a [[NP-complete]] problem as well as a [[3-satisfiability|3-SAT]] problem with 20 variables.
=== Tic-tac-toe game ===
In 2002, J. Macdonald, D.
By default, the computer is considered to have played first in the central square. The human player starts with eight different types of DNA strands corresponding to the eight remaining boxes that may be played. To play box number i, the human player pours into all bins the strands corresponding to input #i. These strands bind to certain DNA enzymes present in the bins, resulting, in one of these bins, in the deformation of the DNA enzymes which binds to the substrate and cuts it. The corresponding bin becomes fluorescent, indicating which box is being played by the DNA computer. The DNA enzymes are divided among the bins in such a way as to ensure that the best the human player can achieve is a draw, as in real tic-tac-toe.
=== Neural network based computing ===
Kevin Cherry and [[Lulu Qian]] at Caltech developed a DNA-based artificial neural network that can recognize 100-bit hand-written digits. They
=== Improved speed with Localized (cache-like) Computing ===
One of the challenges of DNA computing is its slow speed. While DNA
=== Renewable (or reversible) DNA computing ===
Subsequent research on DNA computing has produced
{{Cite journal
|last1= Eshra|first1= A.|last2= Shah|first2= S.
Line 42 ⟶ 44:
|date= 2019
|title= Renewable DNA hairpin-based logic circuits
|journal= [[IEEE Transactions on Nanotechnology]]
|volume= 18|pages= 252–259
|doi= 10.1109/TNANO.2019.2896189|issn= 1536-125X
Line 48 ⟶ 50:
|bibcode= 2019ITNan..18..252E|s2cid= 5616325}}
</ref>
While both
Using strand displacement reactions (SRDs), reversible proposals are presented in
==Methods==
Line 58 ⟶ 60:
The most fundamental operation in DNA computing and molecular programming is the strand displacement mechanism. Currently, there are two ways to perform strand displacement:
* [[Toehold mediated strand displacement]] (TMSD)<ref name=":5" />
* Polymerase-based strand displacement (PSD)<ref name=":0" />
=== Toehold exchange ===
=== Chemical reaction networks (CRNs) ===
The full stack for DNA computing looks very similar to a traditional computer architecture. At the highest level, a C-like general purpose programming language is expressed using a set of [[Chemical reaction networks|chemical reaction networks (CRNs)]]. This intermediate representation gets translated to ___domain-level DNA design and then implemented using a set of DNA strands. In 2010,
===DNAzymes===
Catalytic DNA ([[deoxyribozyme]] or DNAzyme) catalyze a reaction when interacting with the appropriate input, such as a matching [[oligonucleotide]]. These DNAzymes are used to build logic gates analogous to digital logic in silicon; however, DNAzymes are limited to
The DNAzyme logic gate changes its structure when it binds to a matching oligonucleotide and the fluorogenic substrate it is bonded to is cleaved free. While other materials can be used, most models use a fluorescence-based substrate because it is very easy to detect, even at the single molecule limit.<ref name="weiss">
{{Cite journal | last1 = Weiss | first1 = S. | s2cid = 9697423 | title = Fluorescence Spectroscopy of Single Biomolecules | doi = 10.1126/science.283.5408.1676 | journal = Science | volume = 283 | issue = 5408 | pages = 1676–1683 | year = 1999 | pmid = 10073925|bibcode = 1999Sci...283.1676W }}. Also available here: http://www.lps.ens.fr/~vincent/smb/PDF/weiss-1.pdf
</ref> The amount of fluorescence can then be measured to tell whether or not a reaction took place. The DNAzyme that changes is then
Two commonly used DNAzymes are named E6 and 8-17. These are popular because they allow cleaving of a substrate in any arbitrary ___location.<ref>
{{Cite journal |
</ref> Stojanovic and MacDonald have used the E6 DNAzymes to build the [[MAYA I]]<ref>
{{Cite journal |
</ref> and [[MAYA II]]<ref>
{{Cite journal |
</ref> machines, respectively; Stojanovic has also demonstrated logic gates using the 8-17 DNAzyme.<ref>
{{Cite journal |
</ref> While these DNAzymes have been demonstrated to be useful for constructing logic gates, they are limited by the need
{{Cite journal | last1 = Cruz | first1 = R. P. G. | last2 = Withers | first2 = J. B. | last3 = Li | first3 = Y. | title = Dinucleotide Junction Cleavage Versatility of 8-17 Deoxyribozyme | doi = 10.1016/j.chembiol.2003.12.012 | journal = Chemistry & Biology | volume = 11 | issue = 1 | pages = 57–67 | year = 2004 | pmid = 15112995| doi-access = free | hdl = 11375/23673 | hdl-access = free }}
</ref>
Line 94 ⟶ 96:
| volume = 2 | issue = 4 | pages = 497–503 | url = http://www.wisdom.weizmann.ac.il/~udi/DNA5/scripps_short/index.htm | doi = 10.1098/rsfs.2011.0118| pmid = 22649583 | pmc = 3363030 | archive-url=https://web.archive.org/web/20090103224150/http://www.wisdom.weizmann.ac.il/~udi/DNA5/scripps_short/index.htm |archive-date=2009-01-03 | access-date = 2009-08-13 }}</ref>
Benenson, Shapiro and colleagues have demonstrated a DNA computer using the [[FokI]] enzyme<ref name="shapiro">{{Cite journal |
{{Cite journal | last1 = Bond | first1 = G. L. | last2 = Hu | first2 = W. | last3 = Levine | first3 = A. J. | doi = 10.2174/1568009053332627 | title = MDM2 is a Central Node in the p53 Pathway: 12 Years and Counting | journal = [[Current Cancer Drug Targets]] | volume = 5 | issue = 1 | pages = 3–8 | year = 2005 | pmid = 15720184}}
</ref> On negative diagnosis it was decided to release a suppressor of the positive diagnosis drug instead of doing nothing. A limitation of this implementation is that two separate automata are required, one to administer each drug. The entire process of evaluation until drug release took around an hour to complete. This method also requires transition molecules as well as the FokI enzyme to be present. The requirement for the FokI enzyme limits application ''in vivo'', at least for use in "cells of higher organisms".<ref name="kahan08">
{{Cite journal |
</ref> It should also be pointed out that the 'software' molecules can be reused in this case.
=== Algorithmic self-assembly ===
[[Image:Rothemund-DNA-SierpinskiGasket.jpg|thumb
{{Main|DNA nanotechnology#Algorithmic self-assembly|l1 = DNA nanotechnology: Algorithmic self-assembly}}
DNA nanotechnology has been applied to the related field of DNA computing. DNA tiles can be designed to contain multiple sticky ends with sequences chosen so that they act as [[Wang tile]]s. A DX array has been demonstrated whose assembly encodes an [[Exclusive or|XOR]] operation; this allows the DNA array to implement a [[cellular automaton]] which generates a [[fractal]] called the [[Sierpinski gasket]]. This shows that computation can be incorporated into the assembly of DNA arrays, increasing its scope beyond simple periodic arrays.<!--
--><ref name="rothemund04winfree">{{Cite journal | last1 = Rothemund | first1 = P. W. K. | last2 = Papadakis | first2 = N. | last3 = Winfree | first3 = E. | doi = 10.1371/journal.pbio.0020424 | title = Algorithmic Self-Assembly of DNA Sierpinski Triangles | journal = PLOS Biology | volume = 2 | issue = 12 | pages = e424 | year = 2004 | pmid = 15583715| pmc =534809 | doi-access = free }}</ref>
== Capabilities ==
Line 119 ⟶ 121:
== Alternative technologies ==
A partnership between [[IBM]] and [[Caltech]] was established in 2009 aiming at "[[DNA chip]]s" production.<ref>[http://media.caltech.edu/press_releases/13284](Caltech's own article) {{webarchive
== Pros and cons ==
Line 139 ⟶ 141:
* [[Transcriptor]]
* [[Wetware computer]]
* [[Molecular logic gate]]
{{Div col end}}
Line 179 ⟶ 182:
* [http://computer.howstuffworks.com/dna-computer.htm How Stuff Works explanation]
* Dirk de Pol: [https://unglaublich.de/dns-ein-neuer-supercomputer/ ''DNS – Ein neuer Supercomputer?'']. In: Die Neue Gesellschaft / Frankfurter Hefte {{ISSN|0177-6738}}, Heft 2/96, Februar 1996, S. 170–172
* [https://web.archive.org/web/20040825021955/http://physicsweb.org/article/news/6/3/11/
* [http://archive.arstechnica.com/reviews/2q00/dna/dna-1.html Ars Technica]
* [https://www.nytimes.com/2004/04/29/science/29DNA.html - The New York Times DNA Computer for detecting Cancer]
| |||