Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published April 18, 2019 | Published + Submitted
Journal Article Open

Verifying chemical reaction network implementations: A pathway decomposition approach

Abstract

The emerging fields of genetic engineering, synthetic biology, DNA computing, DNA nanotechnology, and molecular programming herald the birth of a new information technology that acquires information by directly sensing molecules within a chemical environment, stores information in molecules such as DNA, RNA, and proteins, processes that information by means of chemical and biochemical transformations, and uses that information to direct the manipulation of matter at the nanometer scale. To scale up beyond current proof-of-principle demonstrations, new methods for managing the complexity of designed molecular systems will need to be developed. Here we focus on the challenge of verifying the correctness of molecular implementations of abstract chemical reaction networks, where operation in a well-mixed "soup" of molecules is stochastic, asynchronous, concurrent, and often involves multiple intermediate steps in the implementation, parallel pathways, and side reactions. This problem relates to the verification of Petri nets, but existing approaches are not sufficient for providing a single guarantee covering an infinite set of possible initial states (molecule counts) and an infinite state space potentially explored by the system given any initial state. We address these issues by formulating a new theory of pathway decomposition that provides an elegant formal basis for comparing chemical reaction network implementations, and we present an algorithm that computes this basis. Our theory naturally handles certain situations that commonly arise in molecular implementations, such as what we call "delayed choice," that are not easily accommodated by other approaches. We further show how pathway decomposition can be combined with weak bisimulation to handle a wider class that includes most currently known enzyme-free DNA implementation techniques. We anticipate that our notion of logical equivalence between chemical reaction network implementations will be valuable for other molecular implementations such as biochemical enzyme systems, and perhaps even more broadly in concurrency theory.

Additional Information

©2017 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). Received 1 November 2014, Revised 2 October 2017, Accepted 13 October 2017, Available online 31 October 2017. We appreciate helpful discussions with John Baez, Luca Cardelli, Vincent Danos, Qing Dong, Robert Johnson, Stefan Badelt, and Matthew Lakin. S.W.S. was supported by California Institute of Technology's Summer Undergraduate Research Fellowship 2009, NSF grant CCF-0832824, ARO Grant W911NF-09-1-0440 and NSF Grant CCF-0905626. C.T. was supported by NSF grants CCF-1213127, SHF-1718938, and a Banting Fellowship. E.W. was supported by NSF grants CCF-0832824, CCF-1213127, and CCF-1317694.

Attached Files

Published - 1-s2.0-S0304397517307399-main.pdf

Submitted - 1411.0782.pdf

Files

1411.0782.pdf
Files (1.9 MB)
Name Size Download all
md5:65bf8451b30eb423962c49ad8c53b198
729.6 kB Preview Download
md5:3d4c80e47fcd7e36d05bdf8d255900b3
1.2 MB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 20, 2023