钱璐璐 (Lulu Qian) and Erik Winfree
Abstract chemical reaction networks (CRNs) provide an all-encompassing formal language for modelling well-mixed chemical systems involving a finite number of species. Showing that arbitrary CRNs can in principle be implemented with DNA strand displacement cascades [*] was a major step toward proving the generality and universality of pure-DNA systems. However, well-mixed systems are far less powerful than molecular systems that exploit spatial geometry to encode information combinatorially. While I know of no all-encompassing formal language for molecular machines with geometry, a very broad class of systems can be described as discrete chemical reaction networks wherein each molecule is localized on a surface at grid points, and asynchronous reactions mediate movement and state change. Here we suggest a pure-DNA implementation using a combination of 3-way and 4-way branch migration.
[ DNA Computing and Molecular Programming (DNA20) (18 pages, June 2014) conference preprint, 228 KB ]
[ Lecture Notes in Computer Science (LNCS), Volume 8727, 2014, pp 114-131 (18 pages) pdf, 856 KB ]
Casey Grun, Karthik Sarma, Brian Wolfe, Seung Woo Shin, and Erik Winfree.
So-called domain-level models were introduced to describe how engineered DNA strand displacement systems shoudl work, prior to assigning actual sequences to the domains. Here we describe our efforts to provide a model rich enough to describe arbitrary secondary structures (so long as no pseudoknots are involved) and to support reaction mechanisms such as association, dissociation, 3-way branch migration, and 4-way branch migration. We use a nifty time-scale separation to make the process tractable and to find a "condensed" reaction network representation.
[ Verification of Engineered Molecular Devices and Programs (VEMDP) (29 pages, June 2014): workshop article, 1.1 MB ]
Seung Woo Shin, Chris Thachuk, Erik Winfree.
What does it mean for two chemical reaction networks to be logically equivalent? The answer is not as obvious as it may seem -- in fact, we still can't give a fully satisfactory answer. There seem to be many possible notions one could entertain, each with its own strengths and weaknesses. Here we present a refinement of the ideas from Seung Woo's Masters Thesis that focus on the smallest coherent sequences of reactions out of which all other sequences can be built. A strength of the theory is that it can handle the "delayed choice" phenomenon, wherein a single species in a molecular implementation has already committed to participation in a reaction, but not yet fully committed to exactly which one. Combined with bisimulation ideas from Qing Dong's Masters Thesis, we hope that this theory can address most, if not all, methods to implement chemical reaction networks using DNA strand displacement systems -- and perhaps more.
[ arXiv preprint (21 pages, November 2014): PDF, 365 KB. ]
[ Verification of Engineered Molecular Devices and Programs (VEMDP) (23 pages, June 2014): workshop article, 298 KB ]
[ Note: The VEMDP version introduces a notion of "futile loops", not present in the MS thesis theory. The arXiv verion reverts to the theory without futile loop elimination, due to a difficulty proving that our basis-finding algorithm terminates. The proof of Theorem B.1 in the VEMDP version is false as stated. ]
Robert Johnson and Erik Winfree.
Formally, discrete chemical reaction networks (CRNs) have a finite number of species, but an infinite number of states -- the numbers of molecules in a test tube is unbounded. The point is, this can make it hard to verify that a proposed molecular implementation (a big complicated CRN) is really doing the job it was designed to do (a smaller simpler CRN). Nonetheless, a method based on Milner's notion of bisimulation in concurrency theory was developed in Qing Dong's Masters Thesis. When considering chemical systems involving polymers of potentially unbounded length, such as the DNA, RNA, and protein polymers in the central dogma of molecular biology, then the number of possible species becomes infinite as well. The point is, the extra infinities can make implementations of polymer reaction networks (PRNs) even harder to verify. And yet, by extending the bisimulation ideas, it can (at least sometimes) be done!
[ Verification of Engineered Molecular Devices and Programs (VEMDP) (15 pages, June 2014): workshop article, 798 KB ]
DNA Based Computers: DIMACS Workshop, held April 4, 1995 (eds Richard J. Lipton and Eric B. Baum) American Mathematical Society, 1996.
DNA Based Computers II: DIMACS Workshop, held June 10-12, 1996 (eds Laura F. Landweber and Eric B. Baum) American Mathematical Society, 1998.
DNA Based Computers III: DIMACS Woskhop, held June 23-25, 1997 (eds Harvey Rubin and David H. Wood) American Mathematical Society, 1999.
Proceedings of the Fourth DIMACS Meeting on DNA Based Computers, held at the University of Pennsylvania, June 16-19, 1998. (never published as a book.)
DNA Based Computers V: DIMACS Workshop, held June 14-15, 1999. (eds. Erik Winfree and David K. Gifford) American Mathematical Society, 2000.
DNA Based Computers VI: held June 13-17, 2000. (eds. Anne Condon and Grzegorz Rozenberg) Lecture Notes in Computer Science 2054, Springer, 2001.
Send comments firstname.lastname@example.org