A Caltech Library Service

A General-Purpose CRN-to-DSD Compiler with Formal Verification, Optimization, and Simulation Capabilities

Badelt, Stefan and Shin, Seung Woo and Johnson, Robert F. and Dong, Qing and Thachuk, Chris and Winfree, Erik (2017) A General-Purpose CRN-to-DSD Compiler with Formal Verification, Optimization, and Simulation Capabilities. In: DNA Computing and Molecular Programming. Lecture Notes in Computer Science. No.10467. Springer , Cham, Switzerland, pp. 232-248. ISBN 978-3-319-66798-0.

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

Use this Persistent URL to link to this item:


The mathematical formalism of mass-action chemical reaction networks (CRNs) has been proposed as a mid-level programming language for dynamic molecular systems. Several systematic methods for translating CRNs into domain-level strand displacement (DSD) systems have been developed theoretically, and in some cases demonstrated experimentally. Software that facilitates the simulation of CRNs and DSDs, and that helps automate the construction of DSDs from CRNs, has been instrumental in advancing the field, but as yet has not incorporated the fundamental enabling concept for programming languages and compilers: a rigorous abstraction hierarchy with well-defined semantics at each level, and rigorous correctness proofs establishing the correctness of compilation from a higher level to a lower level. Here, we present a CRN-to-DSD compiler, Nuskell, that makes a first step in this direction. To support the wide range of translation schemes that have already been proposed in the literature, as well as potential new ones that are yet to be proposed, Nuskell provides a domain-specific programming language for translation schemes. A notion of correctness is established on a case-by-case basis using the rate-independent stochastic-level theories of pathway decomposition equivalence and/or CRN bisimulation. The “best” DSD implementation for a given CRN can be found by comparing the molecule size, network size, or simulation behavior for a variety of translation schemes. These features are illustrated with a 3-reaction oscillator CRN and a 32-reaction feedforward boolean circuit CRN.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Winfree, Erik0000-0002-5899-7523
Additional Information:© Springer International Publishing AG 2017. First Online: 24 August 2017. We thank the U.S. National Science Foundation for support: NSF Grant CCF-1213127 and NSF Grant CCF-1317694 (“The Molecular Programming Project”). The Gordon and Betty Moore Foundation’s Programmable Molecular Technology Initiative (PMTI). SB is funded by the Caltech Biology and Biological Engineering Division Fellowship.
Funding AgencyGrant Number
Gordon and Betty Moore FoundationUNSPECIFIED
Caltech Division of Biology and Biological EngineeringUNSPECIFIED
Series Name:Lecture Notes in Computer Science
Issue or Number:10467
Record Number:CaltechAUTHORS:20181126-085056720
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:91151
Deposited By: Tony Diaz
Deposited On:26 Nov 2018 17:41
Last Modified:16 Nov 2021 03:38

Repository Staff Only: item control page