nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Chemical Reaction Networks and Stochastic Local Search

verfasst von : Erik Winfree

Erschienen in: DNA Computing and Molecular Programming

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Stochastic local search can be an effective method for solving a wide variety of optimization and constraint satisfaction problems. Here I show that some stochastic local search algorithms map naturally to stochastic chemical reaction networks. This connection highlights new ways in which stochasticity in chemical reaction networks can be used for search and thus for finding solutions to problems. The central example is a chemical reaction network construction for solving Boolean formula satisfiability problems. Using an efficient general-purpose stochastic chemical reaction network simulator, I show that direct simulation of the networks proposed here can be more efficient, in wall-clock time, than a somewhat outdated but industrial-strength commercial satisfiability solver. While not of use for practical computing, the constructions emphasize that exploiting the stochasticity inherent in chemical reaction network dynamics is not inherently inefficient – and indeed I propose that stochastic local search could be an important aspect of biological computation and should be exploited when engineering future artificial cells.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Nächstes Kapitel Implementing Arbitrary CRNs Using Strand Displacing Polymerase

The sequence of reactions identified in the proof will have a positive probability of occurring next, specifically, at least \((12M+L)^{-(N+M)}\). This provides an exponential bound on the expected time to halt, to wit, less than \((12M+L)^{N+M}/k+(N+M)/k\). But is that useful?

A straightforward adaptation of the previous argument works for a closely related CRN that is identical to WalkSATCRN[f] except that species tryX0 and tryX1 are conflated as tryX for each variable X. This CRN should work similarly, as the main difference is merely that a variable being flipped now might spontaneously revert. But it is not the CRN that I simulated.

Simonis, H.: Sudoku as a constraint problem. In: Proceedings of the 4th International Workshop on Modelling and Reformulating Constraint Satisfaction Problems, vol. 12, pp. 13–27 (2005)

Lynce, I., Ouaknine, J.: Sudoku as a SAT problem. In: Proceedings of the 9th International Symposium on Artificial Intelligence and Mathematics (AIMATH) (2006)

Hopfield, J.J.: Searching for memories, Sudoku, implicit check bits, and the iterative use of not-always-correct rapid neural computation. Neural Comput. 20, 1119–1164 (2008)MathSciNetCrossRef

Jonke, Z., Habenschuss, S., Maass, W.: Solving constraint satisfaction problems with networks of spiking neurons. Front. Neurosci. 10, 118 (2016)CrossRef

Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Company, New York (1979)MATH

Jaffar, J., Maher, M.J.: Constraint logic programming: a survey. J. Logic Program. 19, 503–581 (1994)MathSciNetCrossRef

Vardi, M.Y.: Boolean satisfiability theory and engineering. Commun. ACM 57, 5 (2014)

Järvisalo, M., Le Berre, D., Roussel, O., Simon, L.: The international SAT solver competitions. AI Mag. 33, 89–92 (2012)CrossRef

Balyo, T., Heule, M.J.H., Jarvisalo, M.: SAT competition 2016: recent developments. In: Thirty-First AAAI Conference on Artificial Intelligence (2017)

10.

de Moura, L., Bjørner, N.: Z3: an efficient SMT solver. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 337–340. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78800-3_24CrossRef

11.

Selman, B., Kautz, H.A., Cohen, B.: Local search strategies for satisfiability testing. Cliques, Color. Satisf. 26, 521–532 (1993)CrossRef

12.

Selman, B., Kautz, H.A., Cohen, B.: Noise strategies for improving local search. In: Proceedings of the 12th National Conference on Artificial Intelligence, vol. 94, pp. 337–343. MIT Press (1994)

13.

Hoos, H.H., Stützle, T.: Stochastic Local Search: Foundations and Applications. Elsevier, Amsterdam (2004)MATH

14.

Gomes, C.P., Kautz, H., Sabharwal, A., Selman, B.: Satisfiability solvers. Foundations of Artificial Intelligence 3, 89–134 (2008)

15.

Kirschner, M., Mitchison, T.: Beyond self-assembly: from microtubules to morphogenesis. Cell 45, 329–342 (1986)CrossRef

16.

Holy, T.E., Leibler, S.: Dynamic instability of microtubules as an efficient way to search in space. Proc. Nat. Acad. Sci. 91, 5682–5685 (1994)CrossRef

17.

Gerhart, J., Kirschner, M.: Cells, Embryos, and Evolution: Toward a Cellular and Developmental Understanding of Phenotypic Variation and Evolutionary Adaptability. Blackwell Science, Malden (1997)

18.

Kirschner, M., Gerhart, J.: Evolvability. Proc. Nat. Acad. Sci. 95, 8420–8427 (1998)CrossRef

19.

Cauwenberghs, G.: A fast stochastic error-descent algorithm for supervised learning and optimization. In: Advances in Neural Information Processing Systems, pp. 244–251 (1993)

20.

Sebastian Seung, H.: Learning in spiking neural networks by reinforcement of stochastic synaptic transmission. Neuron 40, 1063–1073 (2003)CrossRef

21.

Hinton, G.E., Nowlan, S.J.: How learning can guide evolution. Complex Syst. 1, 495–502 (1987)MATH

22.

Cook, M., Soloveichik, D., Winfree, E., Bruck, J.: Programmability of chemical reaction networks. In: Condon, A., Harel, D., Kok, J., Salomaa, A., Winfree, E. (eds.) Algorithmic Bioprocesses. Natural Computing Series, pp. 543–584. Springer, Heidelberg (2009)CrossRef

23.

Soloveichik, D., Seelig, G., Winfree, E.: DNA as a universal substrate for chemical kinetics. Proc. Nat. Acad. Sci. 107, 5393–5398 (2010)CrossRef

24.

Chen, Y.-J.: Programmable chemical controllers made from DNA. Nat. Nanotechnol. 8, 755 (2013)CrossRef

25.

Srinivas, N., Parkin, J., Seelig, G., Winfree, E., Soloveichik, D.: Enzyme-free nucleic acid dynamical systems. Science 358, eaal2052 (2017)CrossRef

26.

Gillespie, D.T.: Stochastic simulation of chemical kinetics. Ann. Rev. Phys. Chem. 58, 35–55 (2007)CrossRef

27.

Anderson, D.F., Cappelletti, D., Koyama, M., Kurtz, T.G.: Non-explosivity of stochastically modeled reaction networks that are complex balanced. Bull. Math. Biol. 80, 2561–2579 (2018)MathSciNetCrossRef

28.

Kurtz, T.G.: The relationship between stochastic and deterministic models for chemical reactions. J. Chem. Phys. 57, 2976–2978 (1972)CrossRef

29.

Karp, R.M., Miller, R.E.: Parallel program schemata. J. Comput. Syst. Sci. 3, 147–195 (1969)MathSciNetCrossRef

30.

Johnson, R.F., Dong, Q., Winfree, E.: Verifying chemical reaction network implementations: a bisimulation approach. Theor. Comput. Sci. 765, 3–46 (2019)MathSciNetCrossRef

31.

Doty, D., Zhu, S.: Computational complexity of atomic chemical reaction networks. Natural Comput. 17, 677–691 (2018)MathSciNetCrossRef

32.

Magnasco, M.O.: Chemical kinetics is turing universal. Phys. Rev. Lett. 78, 1190–1193 (1997)CrossRef

33.

Liekens, A.M.L., Fernando, C.T.: Turing complete catalytic particle computers. In: Almeida e Costa, F., Rocha, L.M., Costa, E., Harvey, I., Coutinho, A. (eds.) ECAL 2007. LNCS (LNAI), vol. 4648, pp. 1202–1211. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74913-4_120CrossRef

34.

Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Nat. Comput. 7, 615–633 (2008)MathSciNetCrossRef

35.

Chen, H.-L., Doty, D., Soloveichik, D.: Deterministic function computation with chemical reaction networks. Natural Comput. 13, 517–534 (2014)MathSciNetCrossRef

36.

Cummings, R., Doty, D., Soloveichik, D.: Probability 1 computation with chemical reaction networks. Natural Comput. 15, 245–261 (2016)MathSciNetCrossRef

37.

Napp, N.E., Adams, R.P.: Message passing inference with chemical reaction networks. In: Advances in Neural Information Processing Systems, pp. 2247–2255 (2013)

38.

Gopalkrishnan, M.: A scheme for molecular computation of maximum likelihood estimators for log-linear models. In: Rondelez, Y., Woods, D. (eds.) DNA 2016. LNCS, vol. 9818, pp. 3–18. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-43994-5_1CrossRefMATH

39.

Fett, B., Bruck, J., Riedel, M.D.: Synthesizing stochasticity in biochemical systems. In: Proceedings of the 44th Annual Design Automation Conference, pp. 640–645. ACM (2007)

40.

Poole, W., et al.: Chemical boltzmann machines. In: Brijder, R., Qian, L. (eds.) DNA 2017. LNCS, vol. 10467, pp. 210–231. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66799-7_14CrossRef

41.

Cardelli, L., Kwiatkowska, M., Laurenti, L.: Programming discrete distributions with chemical reaction networks. Nat. Comput. 17, 131–145 (2018)MathSciNetCrossRef

42.

Anderson, D.F., Craciun, G., Kurtz, T.G.: Product-form stationary distributions for deficiency zero chemical reaction networks. Bull. Math. Biol. 72, 1947–1970 (2010)MathSciNetCrossRef

43.

Cappelletti, D., Ortiz-Munoz, A., Anderson, D., Winfree, E.: Stochastic chemical reaction networks for robustly approximating arbitrary probability distributions. arXiv preprint arXiv:1810.02854 (2018)

44.

Braich, R.S., Chelyapov, N., Johnson, C., Rothemund, P.W.K., Adleman, L.: Solution of a 20-variable 3-SAT problem on a DNA computer. Science 296, 499–502 (2002)CrossRef

45.

Kirkpatrick, S., Selman, B.: Critical behavior in the satisfiability of random Boolean expressions. Science 264, 1297–1301 (1994)MathSciNetCrossRef

46.

Selman, B., Kirkpatrick, S.: Critical behavior in the computational cost of satisfiability testing. Artif. Intell. 81, 273–295 (1996)MathSciNetCrossRef

47.

Strzebonski, A.: Mathematica SatisfiabilityQ uses MiniSAT 1.14. StackExchange and personal communication (2016, 2019). https://mathematica.stackexchange.com/questions/103726/why-is-satisfiabilitycount-faster-than-satisfiableq

48.

Soloveichik, D.: CRNSimulatorSSA Mathematica Package. Personal Web Site (2016). http://users.ece.utexas.edu/~soloveichik/crnsimulator.html

49.

Gibson, M.A., Bruck, J.: Efficient exact stochastic simulation of chemical systems with many species and many channels. J. Phys. Chem. A 104, 1876–1889 (2000)CrossRef

50.

Mauch, S., Stalzer, M.: Efficient formulations for exact stochastic simulation of chemical systems. IEEE/ACM Trans. Comput. Biol. Bioinf. 8, 27–35 (2011)CrossRef

51.

Thanh, V.H., Zunino, R.: Adaptive tree-based search for stochastic simulation algorithm. Int. J. Comput. Biol. Drug Des. 7, 341–357 (2014)CrossRef

52.

Condon, A., Hu, A.J., Maňuch, J., Thachuk, C.: Less haste, less waste: on recycling and its limits in strand displacement systems. Interface Focus 2, 512–521 (2012)CrossRef

53.

Thachuk, C., Condon, A.: Space and energy efficient computation with DNA strand displacement systems. In: Stefanovic, D., Turberfield, A. (eds.) DNA 2012. LNCS, vol. 7433, pp. 135–149. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32208-2_11CrossRefMATH

54.

Condon, A., Thachuk, C.: Towards space-and energy-efficient computations. In: Kempes, C., Grochow, J., Stadler, P., Wolpert, D. (eds.) The Energetics of Computing in Life and Machines, chapter 9, pp. 209–232. The Sante Fe Institute Press, Sante Fe (2019)

55.

Matthew M Cook. Networks of Relations. PhD thesis, California Institute of Technology, 2005

56.

Hopfield, J.J.: Neural networks and physical systems with emergent collective computational abilities. Proc. Nat. Acad. Sci. 79, 2554–2558 (1982)MathSciNetCrossRef

57.

Kitano, H.: Towards a theory of biological robustness. Mol. Syst. Biol. 3, 137 (2007)CrossRef

58.

Reich, E.S.: Mathematician claims breakthrough in Sudoku puzzle. Nature (2012). https://doi.org/10.1038/nature.2012.9751CrossRef

59.

Karr, J.R., Sanghvi, J.C., Macklin, D.N., Arora, A., Covert, M.W.: WholeCellKB model organism databases for comprehensive whole-cell models. Nucleic Acids Res. 41, D787–D792 (2012)CrossRef

60.

Winfree, E.: Mathematica Notebooks for CRN SAT Solvers. Personal Web Site (2019). http://www.dna.caltech.edu/SupplementaryMaterial/CRNSAT/

Titel: Chemical Reaction Networks and Stochastic Local Search
verfasst von: Erik Winfree
Verlag: Springer International Publishing
Buch: DNA Computing and Molecular Programming
Print ISBN: 978-3-030-26806-0

Electronic ISBN: 978-3-030-26807-7

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-26807-7_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner