Content deleted Content added
made plural Tags: Visual edit Mobile edit Mobile web edit |
m Open access bot: pmc updated in citation with #oabot. |
||
| (26 intermediate revisions by 13 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=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–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
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 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|url-access=subscription}}</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|url-access=subscription}}</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|url-access=subscription}}</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|bibcode=2004ACIE...43.4906Y |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,
== 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 the "[[travelling salesman problem]]". For this purpose, different DNA fragments were created, each one of them representing a city that had to be visited. Every one of these fragments is capable of a linkage with the other fragments created. These DNA fragments were produced and mixed in a [[test tube]]. Within seconds, the small fragments form bigger ones, representing the different travel routes. Through a chemical reaction, the DNA fragments representing the longer routes were eliminated. The remains are the solution to the problem, but overall, the experiment lasted a week.<ref>{{cite journal | last1 = Adleman | first1 = Leonard M | year = 1998 | title = Computing with DNA | journal = Scientific American | volume = 279 | issue = 2| pages = 54–61 | doi = 10.1038/scientificamerican0898-54 | bibcode = 1998SciAm.279b..54A }}</ref> However, current technical limitations prevent the evaluation of the results. Therefore, the experiment isn't suitable for the application, but it is nevertheless a [[proof of concept]].
=== 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. Stefanović and M. Stojanović created a DNA computer able to play [[tic-tac-toe]] against a human player.<ref>[FR] - J. Macdonald, D. Stefanovic et M. Stojanovic, ''Des assemblages d'ADN rompus au jeu et au travail'', [[:fr:Pour la Science|Pour la Science]],
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 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 50:
|bibcode= 2019ITNan..18..252E|s2cid= 5616325}}
</ref>
While both
Using strand displacement reactions (SRDs), reversible proposals are presented in
==Methods==
Line 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">
Line 83:
{{Cite journal |last1=MacDonald |first1=J. |last2=Li |first2=Y. |last3=Sutovic |first3=M. |last4=Lederman |first4=H. |last5=Pendri |first5=K. |last6=Lu |first6=W. |last7=Andrews |first7=B. L. |last8=Stefanovic |first8=D. |last9=Stojanovic |first9=M. N. |year=2006 |title=Medium Scale Integration of Molecular Logic Gates in an Automaton |journal=Nano Letters |volume=6 |issue=11 |pages=2598–2603 |bibcode=2006NanoL...6.2598M |doi=10.1021/nl0620684 |pmid=17090098}}. Also available here: [http://www.ece.gatech.edu/research/labs/bwn/nanos/papers/Medium_Scale_Integration_of_Molecular.pdf]
</ref> machines, respectively; Stojanovic has also demonstrated logic gates using the 8-17 DNAzyme.<ref>
{{Cite journal |last1=Stojanovic |first1=M. N. |last2=Mitchell |first2=T. E. |last3=Stefanovic |first3=D. |year=2002 |title=Deoxyribozyme-Based Logic Gates |url=https://figshare.com/articles/Deoxyribozyme-Based_Logic_Gates/3638808 |journal=Journal of the American Chemical Society |volume=124 |issue=14 |pages=3555–3561 |doi=10.1021/ja016756v |pmid=11929243|bibcode=2002JAChS.124.3555S }}. Also available at [http://www.dna.caltech.edu/courses/cs191/paperscs191/stojanovic_mitchell_stefanovic2002.pdf]
</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 103:
=== Algorithmic self-assembly ===
[[Image:Rothemund-DNA-SierpinskiGasket.jpg|thumb
{{Main|DNA nanotechnology#Algorithmic self-assembly|l1 = DNA nanotechnology: Algorithmic self-assembly}}
Line 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|url=https://web.archive.org/web/20111014075545/http://media.caltech.edu/press_releases/13284|date=October 14, 2011}}</ref> A Caltech group is working on the manufacturing of these nucleic-acid-based integrated circuits. One of these chips can compute whole square roots.<ref>[https://www.science.org/doi/full/10.1126/science.1200520 Scaling Up Digital Circuit Computation with DNA Strand Displacement Cascades]</ref> A compiler has been written in [[Perl]].<ref>[https://www.science.org/doi/abs/10.1126/science.1200520] Online</ref>
== Pros and cons ==
| |||