Skip to main content

2016 | OriginalPaper | Buchkapitel

22. Molecular Computing

verfasst von : Bernhard Reus

Erschienen in: Limits of Computation

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This chapter is dedicated to molecular computing. Molecular computing uses DNA and molecular biology and chemistry as hardware. Historically, its beginnings are rooted in the attempt to solve NP-complete problems efficiently. Those attempts and the overall potential and the major challenges of DNA computing are reviewed. One particular abstract model of molecular computing, Chemical Reaction Networks, are introduced in more detail and compared to other notions of computations. The programming techniques for Chemical Reaction Networks are very different from traditional approaches presented earlier, as the programmer has no control over the order of reactions executed. A concrete “synthetic chemistry” implementation of this abstract model that uses DNA strand displacement is briefly explained.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
A human cell contains almost two meters of DNA [19] strand rolled up into a small ball, i.e. nucleus, of 5 \(\upmu \)m [13] structured into 23 pairs of chromosomes.
 
2
The complete human genome needs about 3.08 GB of storage space on a conventional hard drive [22].
 
3
Latest research seems to suggest that there is rather a “mosaic” of DNA in the cells [21].
 
4
Mutation rates vary substantially ...even among different parts of the genome in a single organism. Scientists have reported mutation rates as low as 1 mistake per 100 million ...to 1 billion ...nucleotides, mostly in bacteria, and as high as 1 mistake per 100 ...to 1,000 ...nucleotides, the latter in a group of error-prone polymerase genes in humans” [23].
 
5
Yes, the one from the RSA algorithm!.
 
6
More precisely the Directed Hamiltonian Path Problem version: “does a tour exist that visits each city exactly once?”.
 
7
Using and combining several techniques: polymerase chain reaction, gel electrophoresis, and affinity purification.
 
8
This included all 154 of Shakespeares sonnets (ASCII text) and a 26-s excerpt from Martin Luther King’s 1963 I have a dream speech (MP3 format), and with some other data used a total of 757,051 bytes.
 
9
According to the National Human Genome Research Institute.
 
10
In chemistry the term “kinetics” refers to the study of reaction rates.
 
11
However, there will be reaction rates associated to reactions that depend on the concentrations of the molecules in use and thus vary during computation. They can be used to implicitly prioritise reactions by increasing or decreasing the probability to fire.
 
12
The minus symbol here denotes (pointwise) vector subtraction. Similarly, we use \(+\) for vector addition.
 
13
This is a very particular CRN, and we will have to discuss below how to read off results or outputs from a CRN in a more general setting.
 
14
This is a special case for CRNs.
 
15
We allow more than one input here as the encoding of tuples in CRNs is not as easily programmable as for our other notions of computations.
 
16
We allow more than one input and output here for the same reasons as for chemical reaction deciders.
 
17
Here all reactions are assumed to have the same rate constant.
 
18
This is an enzyme that produces transcript RNA.
 
19
Here “alien” alludes to any technology one does not understand.
 
20
Carl Adam Petri (12 July 1926—2 July 2010) was an award-winning German mathematician and computer scientist who invented Petri nets exactly for the purpose of describing chemical reactions.
 
21
DNA occurs most of the time as double stranded (double helix) “ladder”.
 
22
James Dewey Watson (born April 6, 1928) is an American molecular biologist who co-discovered the structure of DNA and was awarded the 1962 Nobel Prize for Physiology or Medicine with Crick and Wilkins (see footnotes 23–25) among numerous other prizes. He is the first Nobel laureate to have sold his Nobel Prize medal at auction to raise funds in 2014.
 
23
Maurice Hugh Frederick Wilkins (15 December 1916—5 October 2004) was a New Zealand-born English molecular biologist, who was co-awarded the 1962 Nobel Prize for Physiology or Medicine among numerous other prizes (See footnote 25).
 
24
Francis Harry Compton Crick (8 June 1916—28 July 2004) was a British molecular biologists who co-discovered the structure of DNA and was co-awarded the 1962 Nobel Prize for Physiology or Medicine (see footnote 25).
 
25
The discovery of the double helix involved many more researchers who were not mentioned by the Nobel Committee. The most famous ones, Rosalind Franklin and Oswald Avery, were already deceased in 1962 and apparently, according to the Nobel Prize rules, could not be mentioned.
 
26
Watson–Crick base pairing refers to the complementary C–G (Cytosine-Guanine) and A–T (Adenine–Thymine) base pairs, see also Fig. 22.1.
 
27
Pronounced “five-prime to three-prime”.
 
28
Gel electrophoresis is a laboratory technique for visualising DNA or proteins. DNA fragments are separated according to their molecular size as they migrate through a gel.
 
29
In two domain strand displacement the nicks are always on the top strand.
 
Literatur
2.
Zurück zum Zitat Angluin, D., Aspnes, J., Eisenstat, D.: Stably computable predicates are semilinear. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, pp. 292–299. ACM, New York (2006) Angluin, D., Aspnes, J., Eisenstat, D.: Stably computable predicates are semilinear. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, pp. 292–299. ACM, New York (2006)
3.
Zurück zum Zitat Bennett, C.H.: On constructing a molecular computer. IBM J. Res. Dev. 17, 525–532 (1973)CrossRef Bennett, C.H.: On constructing a molecular computer. IBM J. Res. Dev. 17, 525–532 (1973)CrossRef
4.
Zurück zum Zitat Bennett, C.H., Landauer, R.: The fundamental physical limits of computation. Sci. Am. 253(1), 48–56 (1985)CrossRef Bennett, C.H., Landauer, R.: The fundamental physical limits of computation. Sci. Am. 253(1), 48–56 (1985)CrossRef
5.
Zurück zum Zitat Bonnet, J., Yin, P., Ortiz, M.E., Subsoontorn, P., Endy, D.: Amplifying genetic logic gates. Science 340(6132), 599–603 (2013)CrossRef Bonnet, J., Yin, P., Ortiz, M.E., Subsoontorn, P., Endy, D.: Amplifying genetic logic gates. Science 340(6132), 599–603 (2013)CrossRef
6.
Zurück zum Zitat Cardelli, L.: Two-domain DNA strand displacement. In: Cooper, S.B., Kashefi, E., Panangaden, P. (eds.) Developments in Computational Models (DCM 2010). EPTCS 26, pp. 47–61 (2010) Cardelli, L.: Two-domain DNA strand displacement. In: Cooper, S.B., Kashefi, E., Panangaden, P. (eds.) Developments in Computational Models (DCM 2010). EPTCS 26, pp. 47–61 (2010)
8.
Zurück zum Zitat Chen, H.-L., Doty, D., Soloveichik, D.: Deterministic function computation with chemical reaction networks. Nat. Comput. 13(4), 517–534 (2013)MathSciNetCrossRefMATH Chen, H.-L., Doty, D., Soloveichik, D.: Deterministic function computation with chemical reaction networks. Nat. Comput. 13(4), 517–534 (2013)MathSciNetCrossRefMATH
9.
Zurück zum Zitat Chen, Y.-J., Dalchau, N., Srinivas, N., Phillips, A., Cardelli, L., Soloveichik, D., Seelig, G.: Programmable chemical controllers made from DNA. Nat. Nanotechnol. 8(10), 755762 (2013) Chen, Y.-J., Dalchau, N., Srinivas, N., Phillips, A., Cardelli, L., Soloveichik, D., Seelig, G.: Programmable chemical controllers made from DNA. Nat. Nanotechnol. 8(10), 755762 (2013)
10.
Zurück zum Zitat Church, G.M., Gao, Y., Kosuri, S.: Next-generation digital information storage in DNA. Science 337(6102), 1628 (2012)CrossRef Church, G.M., Gao, Y., Kosuri, S.: Next-generation digital information storage in DNA. Science 337(6102), 1628 (2012)CrossRef
11.
Zurück zum Zitat Cook, M., Soloveichik, D., Winfree, E., Bruck, S.: Programmability of chemical reaction networks. In: Condon, A., Harel, D., Kok, J.N., Salomaa, A., Winfree, E. (eds.) Algorithmic Bioprocesses, pp. 543–584. Springer, Heidelberg (2009)CrossRef Cook, M., Soloveichik, D., Winfree, E., Bruck, S.: Programmability of chemical reaction networks. In: Condon, A., Harel, D., Kok, J.N., Salomaa, A., Winfree, E. (eds.) Algorithmic Bioprocesses, pp. 543–584. Springer, Heidelberg (2009)CrossRef
12.
Zurück zum Zitat Cox, J.C., Cohen, D.S., Ellington, A.D.: The complexities of DNA computation. Trends Biotechnol. 171, 151–154 (1999)CrossRef Cox, J.C., Cohen, D.S., Ellington, A.D.: The complexities of DNA computation. Trends Biotechnol. 171, 151–154 (1999)CrossRef
14.
Zurück zum Zitat Doty, D.: Timing in chemical reaction networks. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, pp. 772–784 (2014) Doty, D.: Timing in chemical reaction networks. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, pp. 772–784 (2014)
15.
Zurück zum Zitat Goldman, N., Bertone, P., Chen, S., Dessimoz, C., LeProust, E.M., Sipos, B., Birney, E.: Towards practical, high-capacity, low-maintenance information storage in synthesized DNA. Nature 494, 77–80 (2013)CrossRef Goldman, N., Bertone, P., Chen, S., Dessimoz, C., LeProust, E.M., Sipos, B., Birney, E.: Towards practical, high-capacity, low-maintenance information storage in synthesized DNA. Nature 494, 77–80 (2013)CrossRef
16.
Zurück zum Zitat Hartmann, L., Jones, N.D., Simonsen, J.G., Vrist, S.B.: Programming in biomolecular computation: programs, self-interpretation and visualisation. Sci. Ann. Comput. Sci. 21(1), 73–106 (2011)MathSciNet Hartmann, L., Jones, N.D., Simonsen, J.G., Vrist, S.B.: Programming in biomolecular computation: programs, self-interpretation and visualisation. Sci. Ann. Comput. Sci. 21(1), 73–106 (2011)MathSciNet
18.
Zurück zum Zitat Lakin, M.R., Parker, D., Cardelli, L., Kwiatkowska, M., Phillips, A.: Design and analysis of DNA strand displacement devices using probabilistic model checking. J. R. Soc. Interface 9(72), 1470–1485 (2012)CrossRef Lakin, M.R., Parker, D., Cardelli, L., Kwiatkowska, M., Phillips, A.: Design and analysis of DNA strand displacement devices using probabilistic model checking. J. R. Soc. Interface 9(72), 1470–1485 (2012)CrossRef
20.
Zurück zum Zitat Linial, M., Linial, N.: On the potential of molecular computing. Science-AAAS-Wkly. Pap. Ed. 268(5210), 481 (1995) Linial, M., Linial, N.: On the potential of molecular computing. Science-AAAS-Wkly. Pap. Ed. 268(5210), 481 (1995)
21.
Zurück zum Zitat Lupski, J.R.: Genome mosaicism—one human, multiple genomes. Science 341(6144), 358–359 (2013)CrossRef Lupski, J.R.: Genome mosaicism—one human, multiple genomes. Science 341(6144), 358–359 (2013)CrossRef
23.
Zurück zum Zitat Pray, L.A.: DNA replication and causes of mutation. Nat. Educ. 1(1), 214 (2008) Pray, L.A.: DNA replication and causes of mutation. Nat. Educ. 1(1), 214 (2008)
24.
Zurück zum Zitat Peterson, J.L.: Petri Net Theory and the Modeling of Systems. Prentice-Hall Inc., Englewood Cliffs (1981)MATH Peterson, J.L.: Petri Net Theory and the Modeling of Systems. Prentice-Hall Inc., Englewood Cliffs (1981)MATH
25.
Zurück zum Zitat Seelig, G., Soloveichik, D., Zhang, D.Y., Winfree, E.: Enzyme-free nucleic acid logic circuits. Science 314(5805), 1585–1588 (2006)CrossRef Seelig, G., Soloveichik, D., Zhang, D.Y., Winfree, E.: Enzyme-free nucleic acid logic circuits. Science 314(5805), 1585–1588 (2006)CrossRef
27.
Zurück zum Zitat Soloveichik, D., Cook, M., Winfree, E., Bruck, S.: Computation with finite stochastic chemical reaction networks. Nat. Comput. 7(4), 615–633 (2008) Soloveichik, D., Cook, M., Winfree, E., Bruck, S.: Computation with finite stochastic chemical reaction networks. Nat. Comput. 7(4), 615–633 (2008)
Metadaten
Titel
Molecular Computing
verfasst von
Bernhard Reus
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-27889-6_22