Robert F. Johnson, Qing Dong, and Erik Winfree
The question of whether a molecular implementation is "for all intents and purposes" equivalent to the intended abstract specification is a fundamental question for molecular programming. Building on earlier work by Seung Woo Shin and Qing Dong, we show that bisimulation provides a surprisingly natural framework assessing the correctness of proposed implementations of formal chemical reaction networks (CRNs). While CRN bisimulation can be easily applied in many circumstances of interest, and an algorithm for doing so is frequently effective, we show that in general variants of the problem of finding and checking bisimulation are NP-complete or PSPACE-complete in this context. Differences with the alternative theory of pathway decomposition are also discussed. (Full proof and additional results will appear in an expanded journal version of the paper, "soon".)
[ DNA Computing and Molecular Programming (DNA22) proceedings, Lecture Notes in Computer Science (LNCS), Volume 9818, September 2016, pp 114-134 (21 pages) pdf, 393 KB ]
Nicholas Schiefer and Erik Winfree
In earlier work, we proposed a theoretical model that combines tile self-assembly and chemical reaction networks, showing that fabrication tasks and computation tasks can be performed more efficiently than in either previous model, when measuring in terms of space used and program size. Here, we show that the CRN-TAM is also as fast or faster. In particular, we show that a class of search problems can be solved in polynomial time, using exponential space -- i.e. the CRN-TAM can efficiently use the inherent parallelism of chemistry for this class of problems. (Full proofs will appear in an expanded journal version of the paper, "soon".)
[ DNA Computing and Molecular Programming (DNA22) proceedings, Lecture Notes in Computer Science (LNCS), Volume 9818, September 2016, pp 165-182 (18 pages) pdf, 238 KB ]
Rizal F. Hariadi, Erik Winfree, and Bernard Yurke.
And so he looked at a tiny bubble
bursting on the surface of an infinite ocean.
Within it, molecules, their world torn asunder.
And in that vigor,
and in that endless churning,
the origin of life.
We followed him deep into this vision.
[PNAS, Published online before print October 26, 2015 doi: 10.1073/pnas.1424673112: article PDF (1.0 MB, 10 pages), article PDF+SI (1.8 MB, 35 pages). ]
Chris Thachuk, Erik Winfree, and David Soloveichik
DNA strand displacement systems are powerful in theory, capable of simulating arbitrary formal chemical reaction network dynamics. In practice, they are plagued by problems, such as leak reactions where the outputs of an intended reaction are released -- to some degree -- even in the absence of the intended inputs. Here we present a systematic approach, involving what we call "double long domains", that aims to eliminate leak reactions.
[ DNA Computing and Molecular Programming (DNA21) proceedings, Lecture Notes in Computer Science (LNCS), Volume 9211, July 2015, pp 133-153 (21 pages) pdf, 790 KB ]
Erratum: Figure 2a of the LNCS paper has a labeling error in the lower lefthand waste molecule. The top domains should be X2 Y1, not X1 X2.
Nicholas Schiefer and Erik Winfree
The abstract chemical reaction network (CRN) model allows for the specification of complex dynamical behaviors in a well-mixed solution. CRN programs have a systematic implementation as DNA strand displacement cascades. The abstract tile assembly model (aTAM) allows for the specification of complex self-assembly processes within a single growing crystal. aTAM programs have a systematic implementation as DNA tile sets. The CRN-TAM provides a "minimal" integration of these two models, allowing CRN reactions to produce tiles, and allowing tile assembly steps to send signals back to the CRN. Although a compelling implementation is not yet available, we show that the CRN-TAM can do things neither previous model can do alone -- in particular, we show that concise CRN-TAM programs can ("optimally") construct arbitrary algorithmically-defined objects, without the sometimes-dramatic scale-up required in the aTAM.
[ DNA Computing and Molecular Programming (DNA21) proceedings, Lecture Notes in Computer Science (LNCS), Volume 9211, July 2015, pp 34-54 (21 pages) pdf, 432 KB ]
Joseph M. Schaeffer, Chris Thachuk, and Erik Winfree
Multistrand is a simulation package that performs random walks on the secondary structure energy landscape for test tubes of multiple (but not too many!) DNA strands. It has a powerful Python interface that allows setting up complex sets of simulations, as well as powerful analysis methods for making sense of them. (Multistrand was developed as the major component of Joseph's PhD thesis.)
[ DNA Computing and Molecular Programming (DNA21) proceedings, Lecture Notes in Computer Science (LNCS), Volume 9211, July 2015, pp 194-211 (18 pages) pdf, 454 KB ]
[ Erratum: On page 198, there is a sign error; the equation should be ΔG = ΔH - T * ΔS. ]
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 email@example.com