A Caltech Library Service

Chemical Reaction Networks and Stochastic Local Search

Winfree, Erik (2019) Chemical Reaction Networks and Stochastic Local Search. In: DNA Computing and Molecular Programming. Lecture Notes in Computer Science. No.11648. Springer , Cham, pp. 1-20. ISBN 978-3-030-26806-0.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ReadCube access
Winfree, Erik0000-0002-5899-7523
Additional Information:© 2019 Springer Nature Switzerland AG. First Online: 24 July 2019. This work was supported in part by National Science Foundation (NSF) grant 1317694 – The Molecular Programming Project. Thanks to Matt Cook, David Soloveichik, Chris Thachuk, William Poole, Lulu Qian, Grzegorz Rozenberg, Moshe Vardi, Tony Rojko, and Henry Lester for stimulating questions, comments, and encouragement.
Funding AgencyGrant Number
Series Name:Lecture Notes in Computer Science
Issue or Number:11648
Record Number:CaltechAUTHORS:20200810-152243847
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104900
Deposited By: Tony Diaz
Deposited On:10 Aug 2020 22:38
Last Modified:16 Nov 2021 18:37

Repository Staff Only: item control page