Anupama J. Thubagere, Wei Li, Robert F. Johnson, Zibo Chen, Shayan Doroudi, Yae Lim Lee, Gregory Izatt, Sarah Wittman, Niranjan Srinivas, Damien Woods, Erik Winfree, Lulu Qian.
Science is often blown forward by the wind of dreams. Can you imagine a mail room smaller than a single virus? Can you imagine a box of mail packages, each being just a single molecule? Can you imagine a single molecule robot wandering around this room, picking up molecular packages and placing each one in the right molecular bin, according to the zip code on its address? Can you imagine a cargo-sorting DNA robot? We dreamed this dream seven years ago. It wasn't particularly realistic, then. But now it is real.
[ Science: 357: eaan6558, 15 September 2017 (1+9 pages) . ]
[ Media: Caltech press release, Science podcast, Los Angeles Times, ABC News Australia, The Scientist, and more. ]
[ The early days of the project in the hands of a talented BIOMOD team. ]
Sedigheh (Nasim) Zolaktaf, Frits Dannenberg, Xander Rudelis, Anne Condon, Joseph M. Schaeffer, Mark Schmidt, Chris Thachuk, Erik Winfree
Models that capture a substantial fraction of the known thermodynamics of multistranded DNA molecules at the analytically-tractable secondary structure level, such as NUPACK, have proven invaluable for the analysis of both biological and artificial nucleic acid systems. Extending such models to predict the kinetics of secondary structure rearrangements and interactions between molecules, as done for example in the Multistrand simulation, has the potential to address a wider range of phenomena. However, thermodynamics does not dictate kinetics -- there is an infinite family of kinetic models that are perfectly consistent with any given thermodynamic model -- and therefore the accuracy of naive kinetics models is limited. Here, we propose a parameterization of multistranded secondary structure kinetics that is based on the Arrhenius model for elementary base-pairing changes, and we prototype a Bayesian Markov Chain Monte Carlo (MCMC) inference method to obtain an ensemble of improved parameter sets -- resulting in markedly increased accuracy when evaluated on a database of experimentally-measured kinetics rates culled from the literature.
[ DNA Computing and Molecular Programming (DNA23) proceedings, Lecture Notes in Computer Science (LNCS), Volume 10467, August 2017, pp 172-187 (16 pages) pdf, 695 KB. ]
William Poole, Andrés Ortiz-Muñoz, Abhishek Behera, Nick S. Jones, Thomas E. Ouldridge, Erik Winfree, Manoj Gopalkrishnan.
What is the difference between noise and information? What distinguishes stochasticity and thinking? These concepts may seem like opposites, but from a certain perspective, they are closely related. Here we present several theoretical constructions for chemical reaction networks whose stochasticity embodies meaningful information, and whose response to input constitutes perfect Bayesian inference.
[ DNA Computing and Molecular Programming (DNA23) proceedings, Lecture Notes in Computer Science (LNCS), Volume 10467, August 2017, pp 210-231 (22 pages) pdf, 1.1 MB. ]
[ arXiv preprint (21 pages, July 2017): PDF, 2.6 MB. ]
Stefan Badelt, Seung Woo Shin, Robert F. Johnson, Qing Dong, Chris Thachuk, Erik Winfree.
What does it mean to compile to molecules? To some, this just means that a computer was used design the molecules, somehow. To others, a more rigorous process is implied: that the intended design is specified by a "high level" formal language, and that a systematic process is used to translate the design into the "low level" molecular construction. Here, we go further: the high-level specification language and the low-level implementation language must each have a semantics -- that is to say, the intended/expected behavior of a given system must be well-defined based on its description -- and more importantly, the behavior of the implementation produced by the compiler must come with a guarantee that it is effectively the same as the specification. These features are prototyped by the Nuskell compiler, which translates formal chemical reaction networks into domain-level DNA strand displacement systems.
[ DNA Computing and Molecular Programming (DNA23) proceedings, Lecture Notes in Computer Science (LNCS), Volume 10467, August 2017, pp 232-248 (17 pages) pdf, 1.0 MB. ]
Niranjan Srinivas, James Parkin, Georg Seelig, Erik Winfree, and David Soloveichik
In days gone by, did you ever build electrical circuits on an old-fashioned breadboard? Maybe you plugged in a few capacitors, a few resistors, an inductor, and transistor -- and voila! an AM radio! The wonderful thing was that if you could draw the circuit and analyze the equations, you could build it. And with a little tuning, it would work. Will biochemistry ever be that straightforward? We take a small step, by showing that the standard chemical reaction network formalism can serve as a programming language for DNA strand displacement systems. We provide a CRN-to-DNA compiler and build a three-reaction oscillator experimentally. What will you build?
[ bioRxiv preprint (21 pages, May 2017): article, 2.5 MB and supplementary, 10 MB. ]
Constantine G. Evans and Erik Winfree
We do our best to provide a gentle but solid introduction to some key physical principles for DNA tile self-assembly, including algorithmic growth, error rates, proofreading, and nucleation. We discuss how an understanding of these issues allows one to navigate from abstract models of tile assembly, such as the aTAM, to more realistic models of tile assembly, such as the single-crystal kTAM and the mass-action kTAM. Finally, we outline a "unified" model of tile self-asssembly that helps clarify the relationships between different levels of abstraction.
[ Chemical Society Reviews, DOI:10.1039/C6CS00745G (22 pages, May 2017): article, 4.9 MB. ]
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 firstname.lastname@example.org