The DNA and Natural Algorithms Group:

Publications

Time-Complexity of Multilayered DNA Strand Displacement Circuits. *
Georg Seelig and David Soloveichik
Of central importance in the theory of computation -- and in life in general -- is how long it takes to get things done. For standard models such as digital circuits and Turing machines, time complexity is very well understood. Does our understanding of classical computation directly yield results for computation in biochemical circuits? Of course, it depends on how you do things. For example, as shown here, circuits built from stochiometric gates (one output molecule per input molecule) are asymptotically slower than those using catalytic gates (each input molecule can produce many output molecules). This suggests that the time complexity of formal chemical reaction networks is likely to develop into an interesting, rich -- and probably suprising -- theory.
[A preliminary extended abstract appears in DNA 15, LNCS 5877 pages 144-153 (2009): .pdf, 451 KB. ]
Programmable Control of Nucleation for Algorithmic Self-Assembly. (Journal version, December 4, 2009) see below
Self-assembly of carbon nanotubes into two-dimensional geometries using DNA origami templates. *
Hareem T. Maune, Si-Ping Han, Robert D. Barish, Marc Bockrath, William A. Goddard III, Paul W. K. Rothemund, Erik Winfree.
Carbon nanotubes are amazing molecules -- rolled up sheets of hexagonal carbon mesh with astounding thermal and electrical properties, they're the nanocircuit engineer's dream. But they're oh so hard to handle! Too small and too slippery to pick up and put them where you want, most researchers either study individual nanotubes, make do with regular arrays of nanotubes, look for chance circuits in randomly scattered piles of nanotubes, or rely on bulk properties of tangled tubes. Here we suggest a way to self-assemble complex nanotube circuits in parallel -- by sticking them in precise locations on DNA origami nanobreadboards. In the future, we envision this technique being expanded from the two-nanotube devices demonstrated in this paper, to multiple nanotube circuits on individual origami, to large-scale nanotube circuits on origami placed on lithographically-patterned surfaces. Dream on!
[Nature Nanotechnology, 8 November, 2009 (5 pages): paper, 1.3 MB, supplementary information, 2.1 MB.]
(Caltech press release, Eric Drexler's blog )
Control of DNA Strand Displacement Kinetics Using Toehold Exchange. *
David Yu Zhang and Erik Winfree.
Computer programs work by transferring control from one line of the program to another. Many DNA programs work by transferring control from one part of a molecule to another. That's what toehold exchange does. It is an essential mechanism in many of our DNA strand displacement circuits. Here we study the device physics of toehold exchange and show that kinetics can be predicted remarkably accurately from the thermodynamics of toehold binding. With this understanding, we can make our DNA programs transition smoothly from step to step.
[JACS, 131: 17303-17314, 2009 (12 pages): paper, 2.2 MB, supplementary information, 200 KB. ]
Placement and orientation of individual DNA shapes on lithographically patterned surfaces. *
RJ Kershner, LD Bozano, CM Micheel, AH Hung, AR Fornof, JN Cha, CT Rettner, M Bersani, J Frommer, PWK Rothemund, GM Wallraff.
Electrical engineers excel at making things using top-down patterning, such as using lithograph to etch circuits on large wafers of silicon, but it is quite difficult to achieve feature sizes below 20nm. Molecular engineers excel at making things using bottom-up self-assembly, such as using DNA hybridization to fold a virus genome into DNA origami, but it is quite difficult to put all the precisely-constructed molecules in the right places on a large scale. Patterning from 10cm down to 20nm. Patterning from 100nm down to 3Å. A match made in heaven. (Joint Caltech/IBM work.)
[Nature Nanotechnology, 3: 557-561, 16 August, 2009 (5 pages): paper, 784 KB, supplementary information, 9.9 MB, and supplementary movie, 3.3 MB.]
(Comments in the press... but please take them with a grain of salt. Working nanoscale circuits are much much further from reality than some of these would suggest. Let's be clear: the work here doesn't attempt to make functional circuits, it just provides a step toward the solution for how to position DNA origami on a lithographically-patterned substrate. We have no idea when or if this approach will pay off for a commercial application. Anyway: Caltech Press Release, IBM Press Release, guardian.co.uk, BBC, CNET, Wired, EE Times, Discover Magazine )
An Information-Bearing Seed for Nucleating Algorithmic Self-Assembly. *
Robert D. Barish, Rebecca Schulman, Paul W. K. Rothemund, and Erik Winfree.
What is a seed? The tiny seed of a giant sequoia tree, sprouting after the fire. The invisible seed of an idea, from which a thousand possibilities grow. A crystal seed, determining the order of all that grows from it. The seed of man and woman, carrying with it the future of humanity. Clearly, it's important stuff. Why? The seed carries the information, the creative part, the inspiration -- and what follows is mere mechanism, the consequences, the algorithm. In this work, we use DNA origami as a highly effective seed for growing DNA tile crystals. Arbitrary information can be put on the seed; it directs the growth of DNA crystals and determines their morphology... much as a genome determines phenotype of an organism... or even, as an idea creates the future.
[PNAS, 106: 6054-6059, 2009 (6 pages): .pdf, 1.7 MB, supplementary information, 2.6 MB, and appendix, 124 KB. ]
(Comments in the press: Caltech Press Release, New Scientist, Foresight )
Statistical Learning of Arbitrary Computable Classifiers. *
David Soloveichik.
It's possible to learn. But there's a conundrum. If the thing you're trying to learn is really complex, you'll need a really complex model. That means you'll need a lot of data to distinguish between the good models and the bad ones. Can you know when you've got enough data? Remarkably, yes... most of the time. But not until you've seen the data -- a distinction that explains why other researchers (with different learning assumptions) have claimed that this is impossible.
[arXiv preprint: cs.LG/0806.3537v2 (5 pages): .pdf, 84 KB. ]
Dynamic Allosteric Control of Noncovalent DNA Catalysis Reactions. *
David Yu Zhang and Erik Winfree.
"When you're hot, you're hot; when you're not, you're not." Some find in that phrase solace for fickle fortune. Others see an engineering principle. It's the ideal for a switchable catalyst: when it's ON, it works full speed ahead, but when it's OFF, nothing doing. In this paper, we design and demonstrate a modification of the catalyst for a previously studied DNA hybrization reaction (Zhang et al 2007) that can be turned ON and OFF by an exogenous DNA strand. This is accomplished by designing the catalyst so that it has two conformations -- switchable by the exogenous strand -- one of which hides the toehold critical for initiating the catalytic reaction. I can almost hear those poor DNA molecules' lament.
[JACS, 130:13921–13926, 2008 (6 pages): .pdf, 850 KB. ]
Programmability of Chemical Reaction Networks. *
Matthew Cook, David Soloveichik, Erik Winfree, and Jehoshua Bruck.
So you'd like to program chemistry, would you? Well, it's tough. Suppose you already had a handle on the molecular design problem: "No problem," you say, "given a specification for a set of chemical reaction equations, I can construct molecules that react according to plan." Even that's not good enough, because there are limits to what a system can do when the parts are bouncing around like a bag of marbles. So, it's tough. But we can give you some hints. In this paper, we compare stochastic chemical reaction networks to a variety of known models of computation (including one of our eccentric favorites, John Conway's FRACTRAN) and examine the limits of computability. You'll meet molecular counts, probabilities, vector addition systems, primitive recursive functions... and discover just when you can and can't perform uniform computation with chemistry. And all this is for well-mixed solutions with a fixed number of chemical species -- if you want to include polymers and geometrical structures, that's a whole other game. Maybe easier, actually.
[In Algorithmic Bioprocesses, Springer Berlin Heidelberg, Eds. A. Condon, D. Harel, J. N. Kok, A. Salomaa, E. Winfree, pp. 543-584 (937 KB) (2009).
Draft preprint (45 pages): .pdf, 824 KB. ]
Programming DNA Tube Circumferences. *
Peng Yin, Rizal F. Hariadi, Sudheer Sahu, Harry M. T. Choi, Sung Ha Park, Thomas H. LaBean, John H. Reif.
To form a good crystal, must the monomer unit be a compact, well-folded structure? Or can it be a floppy mess? Peng shows that what's really important is the structure in the context of the resulting crystal -- so yes, a monomer can be a floppy mess, and it's still alright! This philosophy leads to the "single-stranded tile" (SST) motif. Because each tile consists of just one strand with four domains, each specifying connectivity in one of the four lattice directions. This allows a straightforward programming of crystals ribbons and tubes with specified width. Lovely.
[Science, vol 321: 824-826, 2008 (3 pages): online .pdf, 240 KB. (26 pages): online supplementary, 3.6 MB. See the blurb at nanotechweb.org and Caltech's Press Release. ]

David's PhD Thesis: Molecules computing : self-assembled nanostructures, molecular automata, and chemical reaction networks. *
133 pages. California Institute of Technology, Defended May 2008.
David Soloveichik. Thesis advisor: Erik Winfree.
We call it the song of the little nightingale. According to the text of the Clauser Prize announcement, this thesis provides seminal contributions to the theory of molecular computing, addressing fundamental questions like: Can we program the self-assembly of complex molecular structures? How can the behavior of molecular systems be made more robust to imperfections and noise? How complex can chemical circuitry become? And, what are the fundamental limits? That's a lovely song to sing.
[.pdf, 2.5 MB; Caltech ETD.]
Error suppression mechanisms for DNA tile self-assembly and their simulation. *
Kenichi Fujibayashi, David Yu Zhang, Erik Winfree, Satoshi Murata.
With the pieces floating all over the place, how can self-assembly be restricted just to the active attachment sites where you want it? How can you prevent the pieces from sticking to each other to soon? Well, one possibility is to put a lock on their binding sites, and design the active attachment sites (and no others!) to serve as a key. Here, we present two possible implementations of this concept for the algorithmic self-assembly of DNA tiles. They are analyzed by theory and simulation; surprisingly, for our designs, locking both the input and output sides of tiles provides substantially greater error suppression than just locking one side.
[Natural Computing, (on line, July 2008) (24 pages): online .pdf, 3.4 MB. ]
DNA as a Universal Substrate for Chemical Kinetics. *
David Soloveichik, Georg Seelig, and Erik Winfree
If chemistry is programmable, what's the programming language? Well, there are many possibilities... but let's not go with a fad. For well over one hundred years, chemists have been using the elegant and refined mathematical language of mass action chemical kinetics. Traditionally, it has been used descriptively, as a means of describing chemical systems encountered in the real world. As chemical engineers interested in programming chemistry, we wish to use the language of chemical kinetics prescriptively, as a means of describing the behaviors we aim to achieve. It's a rich language, capable of expressing behaviors as varied and sophisticated as stable attractors, oscillators, chaotic dynamics, signal processing and computation -- but much of the evidence for this has come from theoretical studies of chemical reaction networks that are possible in principle, rather than from the study of real systems. That is, for the past hundred years, many intriguing chemical reaction networks existed only in a kind of theoretical dream world, with no physical implementation known. Finally, here we show how any chemical reaction network you dream up can be implemented using systems of DNA logic gates, transforming chemical kinetics from a modeling language into a programming language. Go ahead, make your dreams come true!
[DNA 14 conference preprint, revised: (10 pages): .pdf, 508 KB.
In LNCS 5347 pages 57-69 (2009): .pdf, 582 KB. ]
A simple DNA gate motif for synthesizing large-scale circuits. *
Lulu Qian and Erik Winfree
What is the core of life? Is it, as the poets sometimes say, the ebb and flow of the tides, the in and out of breathing, the ups and downs of fortune? Or is it, as the electrical engineers might say, all in the circuitry, the processing of information, the dynamics of behavior? In this work, we present a simple DNA device, called the "seesaw gate", that should make both poets and engineers happy. It operates by a simple back-and-forth process -- a strand comes in on one side, pushing that side "down" and kicking off the one on the other side as it goes "up". And then visa versa, like a seesaw. Released strands are then free to interact with other seesaw gates, allowing networks to be designed systematically. Remarkably, the ebb and flow of activity in these networks can perform computations of arbitrary complexity in principle -- in fact, we describe a compiler that translates digital logic circuits into functionally equivalent seesaw gate networks, and we argue that the simplicity of the motif should make networks containing thousands of gates possible. If this theoretical proposal pans out experimentally, could it become a core technology for embedding circuitry in synthetic biochemical systems?
[DNA 14 conference preprint: (13 pages): .pdf, 417 KB.
In LNCS 5347 pages 70-89 (2009): .pdf, 414 KB. ]
Robust Stochastic Chemical Reaction Networks and Bounded Tau-Leaping. *
David Soloveichik
Biology is robust. Step on it, squash it, zap it, shake it -- odds are, it will just keep going. What makes biological systems so robust, and what are the implications of this robustness? To study this question, forget the arms and legs and blood and guts -- biological organisms are just chemistry, intricate networks of chemical reactions. What's special about robust chemical reaction networks? That should be a simpler question. In this paper, David makes a surprising connection: robustness allows stochastic chemical reaction networks to be simulated efficiently. In fact, this insight leads to an elegant and fast algorithm for simulating stochastic chemical reaction networks and even results in formal statements limiting how fast a simulator could possibly be. The result provides a new and fundamental framework for analyzing the efficiency of stochastic simulation algorithms. The bottom line is, robustness doesn't only make life easier for the organism, it makes life easier for those of us studying the organism.
[ Journal of Computational Biology 16(3): 501-522 (2009), (22 pages): .pdf, 364 KB.
arXiv version, with corrections & additions: cs.CC/0803.1030 (29 pages): .pdf, 427 KB. ]
Toward Reliable Algorithmic Self-Assembly of DNA Tiles: A Fixed-Width Cellular Automaton Pattern. *
Kenichi Fujibayashi, Rizal Hariadi, Sung Ha Park, Erik Winfree, Satoshi Murata.
In biological morphogenesis, genetic information is expressed as biochemical processes that create an organism. In algorithmic self-assembly, information in DNA is expressed as complex folding and crystallization processes that construct intricately patterned supramolecular objects. Here, we combine several techniques developed in this lab -- Erik's DNA tiles, Paul's DNA origami, Rebecca's ribbon crystals, and Rob's (as yet unpublished) origami seeds -- to self-assemble a fixed-width cellular automaton pattern related to Sierpinski triangles. (One commentator calls them "snakeskin nanobelts", an odd but evocative phrase.) Along the way, we gained some insights about assembly errors and how to prevent them -- about how algorithmic crystals aggregate and grow together and about lattice defect and computation error rates.
[Nano Letters, 8(17) 1791-1797, 2008 (5 pages): .pdf, 884 KB and supplementary information, 1.9 MB. Highlighted in Nature. Made the cover of Nano Letters!]
Engineering Entropy-Driven Reactions and Networks Catalyzed by DNA. *
David Yu Zhang, Andrew J. Turberfield, Bernard Yurke, and Erik Winfree.
The entropy of the universe is always increasing. That sounds like a force -- something that keeps increasing can push something else, can't it? The problem, of course, is that using entropy to do work sounds like trying to plow a field by herding stray cats -- it just ends in chaos. But does it have to? Nope: chemists, in fact, are quite familiar with entropy-driven reactions. In this paper, we show how to design systems of DNA molecules with catalytic reactions that are driven by entropy. And it doesn't end in chaos, far from it: we argue that our reactions can be wired together into arbitrary analog or digital circuits, which means they can process information and thus create order. So entropy can drive the production of order? Yup. No wonder the universe is such a beautiful place!
[Science, 318:1121-1125, 2007 (5 pages) .pdf, 604k and supplementary info, 640k. Chosen as an editor's choice; also see Roy Bar-Ziv's excellent Perspectives essay, an interesting commentary in The Scientist and a nice article in The New Scientist.
Computation with Finite Stochastic Chemical Reaction Networks. *
David Soloveichik, Matthew Cook, Erik Winfree, and Jehoshua Bruck.
Some people think of chemistry as a bag of colored marbles. Shake really hard. When the marbles hit each other, they change colors, according to rules. So there's a bit of structure, but it's a chaotic mess -- at any given moment, it's anyone's guess what will happen next. Can chemistry do computation, then? At least since Jacob & Monod, and perhaps before, it has been generally recognized that biochemical systems, such as genetic regulatory networks, can operate much like electrical circuits -- the concentration of some chemical species can carry an ON/OFF signal. Arbitrary digital circuit logic can be performed. If enough marbles turn green, we'll say the output was "1". Bennett even realized that if we string the marbles together like a necklace of beads, then Turing-universal computation can be performed. That's strictly more powerful, theoretically, than digital circuits. What we show here is that finite stochastic chemical reaction networks -- bags of marbles without strings -- can also perform Turing-universal computation. Reasonably quickly, too! This result holds if we accept some probability, no matter how small, that the chemistry will produce the wrong output... but remarkably, the result fails if we insist that the chemistry always and without exception produces the correct output. It pays to be tolerant, if even ever so slightly.
[Natural Computing, (Volume 7, pages 615-633, 2008), (19 pages): online .pdf, 690 KB or Technical Report CaltechPARADISE:2007.ETR085 (19 pages): .pdf, 530 KB. ]

Rebecca's PhD Thesis: The Self-Replication and Evolution of DNA Crystals. *
133 pages. California Institute of Technology, Defended May 2007.
Rebecca Schulman. Thesis advisor: Erik Winfree.
Few questions are so profound as that of life's origins. It may be that the answer is not ours to know. But we can know how it could have happened -- that is, we can ask "What chemical systems have the capacity to self-replicate and evolve?" This too is a profound question, and a rich one; it asks about the design space for evolvable chemical systems, and there must be many many ways. A good place to start, then, would be the simplest. In that spirit, Rebecca's thesis examines how DNA tiles could be programmed to faithfully copy information, spawn daughter crystals, mutate, grow under selective pressures, and thus evolve in potentially complex evolutionary landscapes. What is truly remarkable is how such a simple chemical mechanism -- the selective sticking that underlies tile-based self-assembly -- can exhibit so many profoundly life-like characteristics. Perhaps the essence of life is not so hard to come by, after all?
[.pdf, 3.1 MB; Caltech ETD.]
Synthesis of crystals with a programmable kinetic barrier to nucleation. *
Rebecca Schulman and Erik Winfree.
Rock candy is my favorite form of sugar. It sparkles with beautiful flat facets. It's tasty. And it practically makes itself, growing right on the stick -- almost as you watch! All you have to do is slowly cool a pot-full of supersaturated hot sugar water. Ahh, the beauty of crystal growth. But if the solid form is thermodynamically favorable (it is growing, after all) why does it grow just on the stick, and not precipitate out of solution everywhere? The answer, of course, is that there is a kinetic barrier to nucleation: small crystals are more likely to melt than to grow. But your stick had on it some pre-formed large crystals (sugar grains) that were more likely to grow than to melt. Seed crystals, we call them. They suck up all the sugar, and voila, big beautiful rock candy! All goes to show: control over nucleation is wonderful to have. But rock candy is just a metaphor. Control over nucleation is critical for a whole slew of biological processes -- such as the growth of the cytoskeleton -- where a structure needs to be built in the right place and at the right time, but nowhere else. It's natural to think that control over nucleation will be key to self-assembling molecular technologies as well. That's what our paper is about. We design DNA tiles that crystallize into ribbons -- but there's a big kinetic barrier to nucleation unless we add a seed. Hopefully, this mechanism for controlling nucleation can be used as a general subroutine for programming complex crystal growth processes.
[PNAS, (vol. 104, pp. 15236-15241, 2007) (6 pages): .pdf, 429 KB and supplementary information, 1.4 MB. ]
Reducing Facet Nucleation during Algorithmic Self-Assembly. *
Ho-Lin Chen, Rebecca Schulman, Ashish Goel, Erik Winfree.
A single bit flip in the source code and the program won't compile. A single mistake in calculating the digits of pi, and every subsequent digit is garbage. This is what happens in brittle algorithms: corrupted information gets used to compute more information, which is thus corrupted, and the infection grows. Our initial efforts to embed algorithmic logic into DNA self-assembly were brittle. A single DNA tile that attached at the wrong site would utterly disrupt the algorithmic pattern being formed. So we invented a way to design "proofreading" tile sets that allowed a few errors to occur without disrupting algorithmic growth. Unfortunately, our construction turned out to still have problems when crystals grew with large facets -- it did not suppress errors occurring from spontaneous nucleation of new layers of tiles on the facets. A few years ago, Ho-Lin and Ashish proposed an improved construction for DNA tile sets, which they call "snaked proofreading" tile sets, that has excellent theoretical properties in this regard. Here, Ho-Lin and Rebecca demonstrate experimentally that the fundamental principle of the new construction is sound: we can design tile sets that logically suppress nucleation on facets. In effect, those nasty bit flips will now most of the time just flip right back.
[Nano Letters, (on-line August 24, 2007) (7 pages): .pdf, 653 KB and supplementary information, 93 KB. ]
An autonomous polymerization motor powered by DNA hybridization. *
Suvir Venkataraman, Robert M. Dirks, Paul W. K. Rothemund, Erik Winfree, Niles A. Pierce.
Can a DNA molecule walk? Can we design a molecular motor from scratch? If so, how could it work? Consider macroscopic motors for a minute: they come in all varieties, using all sorts of principles -- internal combustion engines, steam engines, Wankel rotary engines, electric motors, pneumatic motors, solenoids, rockets, jets... each best suited to different tasks. The molecular world has similar diversity. In biology, we see rotary motors like ATPase and the flagellar motor, walking motors like kinesin, linear motors like RNA polymerase and the ribosome, and waving motors like cilia. Not to mention muscle. Among the most mind-bending are the polymerization motors of pathogenic bacteria, such as Rickettsia and Listeria, that live inside eukaryotic host cells. By displaying proteins that catalyze the polymerization of the host cell's actin, these bacteria create a "comet tail" behind them that pushes them forcefully through the cell and even into neighboring cells. This was the motor principle targeted in our work, which was lead by Niles' group. Perhaps most fascinating is that the DNA polymers grow by insertion between the polymer tail and the DNA catalyst strands anchored on the "surrogate bacterial cell". This insertion takes place by a series of conformational rearrangements without ever the two sides losing their strong attachment to each other. Quite a dance!
[Nature Nanotechnology, (vol. 2, pp. 490-494, 2007) (5 pages): .pdf, 738 KB and supplementary information, 581 KB. ]
How Crystals that Sense and Respond to Their Environment Could Evolve. *
Rebecca Schulman and Erik Winfree.
In 1965, Graham Cairns-Smith proposed that the first (and simplest) Darwinian entities were clay crystals, and that as they evolved to reproduce faster and more robustly, they catalyzed organic synthesis... and eventually their invented technology took over the reins... and this "genetic takeover" resulted in us, their organic brainchildren. Sounds crazy, doesn't it? Especially since crystal evolution hasn't been demonstrated experimentally. Well, read his books. In any case, a few years ago we realized that we might be able to evolve our DNA crystals in the lab -- it's not clay, but the principles might be similar. So we asked ourselves, what might be an interesting selective pressure that our crystals could be subjected to, so that evolution leads to increasing functional complexity? The answer was quite surprising: without any novel chemistry or physics, purely informational aspects of crystal growth are in principle sufficient for a crystal to "intelligently" respond to the presence or absence in the environment of material required for growth -- and crystals containing information that enables them to respond more adeptly will grow and reproduce faster. This is intriguing.
[Natural Computing, (Volume 7, pages 219-237, 2008) (19 pages): online .pdf, 485 KB or (17 pages): preprint .pdf, 256 KB. ]
Combining Self-Healing and Proofreading in Self-Assembly. *
David Soloveichik, Matthew Cook, Erik Winfree.
If you cut a crystal, does it bleed? Normally, you'd think not... but algorithmic crystal growth has some surprisingly life-like properties... so it makes you wonder. For example, there are crystal monomer solutions that, depending on the information contained in a seed crystal, can grow into any algorithmically describable shape -- much like a biological developmental program. But what if the growth process is error-prone? What if the crystal suffers damage from a hostile environment (i.e. you cut it)? Previous work showed that even under such conditions (considered separately), algorithmic crystals can grow and maintain their integrity. But different constructions and different arguments were used in the two cases. Here, we introduce a new construction and a new proof technique that shows that both challenges can be met simultaneously! No blood.
[Natural Computing, (Volume 7, pages 203-218, 2008) (16 pages): online .pdf, 472 KB or (12 pages): preprint .pdf, 310 KB. ]
Thermodynamic Analysis of Interacting Nucleic Acid Strands. *
Robert M. Dirks, Justin S. Bois, Joseph M. Schaeffer, Erik Winfree, Niles A. Pierce.
If you're thinking about the molecular machines that may have inhabited the RNA World in times gone by, if you're planning on engineering a modern-day DNA World, or even if you're just curious, you may want to know what happens when you toss a collection of strands together in a test tube. Will they fold up? Into what shapes? Will they interact? Form multi-stranded assemblies? With what concentrations? For single strands, existing dynamic programming algorithms can find the minimum-free-energy fold and even calculate the partition function exactly, so that the probabilities of alternative folds can be compared. (At least, with respect to the standard nearest-neighbor model of secondary structure.) The bimolecular case has also been tackled. Here, Niles & his boys lead the charge to solve the full problem for any number of strands. An exact solution, with fast algorithms, is provided. The math is elegant, involving symmetry groups, convex optimization, and what seem like remarkable "coincidences". Nice.
[SIAM Review, vol. 49, pp 65-88, 2007 (24 pages): preprint .pdf, 653 KB. ]
Complexity of Self-Assembled Shapes. (Journal version, February 9, 2007) see below

Jongmin's PhD Thesis: In vitro Synthetic Transcriptional Networks. *
118 pages. California Institute of Technology, Defended December 2006.
Jongmin Kim. Thesis advisor: Erik Winfree.
This thesis describes presents a simplified architecture for designing and synthesizing arbitrary dynamics in in vitro biochemical networks. Inspired by neural networks and genetic regulatory networks, the in vitro systems make use of just RNA polymerase and RNases in addition to DNA constructs that define the network structure. Theory demonstrates that arbitrary dynamics can be synthesized in general, and experiments demonstrate individual switches as well as circuits that implement bistability and oscillation.
[.pdf, 18 MB; Caltech ETD.]
Construction of an in vitro bistable circuit from synthetic transcriptional switches. *
Jongmin Kim, Kristin S. White, Erik Winfree.
How simple can life be? To some, the answer to this question is a small bungalow on Fiji, a hammock, and the sound of waves sloshing and slurping against the sand. Others are more inclined to think about the origin of life, about minimal organisms, about what it would take to create life from scratch. Being broad-minded, we appreciate both perspectives. While our research on the first aspect of the problem is still in progress, this paper reports our efforts in the second direction -- efforts to recreate, in simplified form, the information-processing heart of cellular processes: genetic regulatory networks. We do it in vitro using just DNA, RNA, and a small handful of enzymes... though not without encountering a few challenges and surprises!
[Molecular Systems Biology, 2:68, 2006 (12 pages): paper and supplementary info; also see Michael Simpson's excellent News & Views essay. Raw data is available from our Extra Supplementary Material page. ]
Enzyme-Free Nucleic Acid Logic Circuits. *
Georg Seelig, David Soloveichik, David Yu Zhang, Erik Winfree.
It's a game of molecular dominoes. One falls, bumps into the next, triggering its fall. Sometimes two separate cascades converge on a single domino, and only when both hit at once does the domino fall. Or maybe either input is enough. In fact, you can build any kind of logic circuit out of dominoes. You can make a domino cascade that multiplies binary numbers, if you want. It's fun. But maybe not so deep scientifically, not so useful. But suppose you now do the same thing with molecules, say DNA strands. Now you have a way to embed logical control in chemistry, to sense and react to molecular events. Now you're at the same frontier of molecular information processing that biology has been exploiting and refining for almost 4 billion years. We're a bit behind in the game.
[Science, 314:1585-1588, 2006 (4 pages) paper and supplementary information; also see Walter Fontana's excellent Perspectives essay, Udi Shapiro's News and Views essay in Nature Nanotechnology, a note in Scientific American, Caltech's Press Release, or a general-interest article we wrote for a Caltech newsletter (we all helped write it, even though they mistakenly only put my name on it). ]
Catalyzed Relaxation of a Metastable DNA Fuel. *
Georg Seelig, Bernard Yurke, Erik Winfree.
DNA machines need fuel. Whether the machine is a motor, a manipulator, or a computer, if it is to be capable of driving a system to perform a periodic behavior -- and what respectable machine can't do that? -- then it needs fuel. ATP is an excellent fuel: small, high energy content, simple... but, how can we put it?... holding it requires small hands. Not even the rain has such small hands. So certainly not human-designed DNA machines, yet. So for DNA machines, we will make do with a bigger fuel -- but one that can be specifically targeted. That, more or less, was the motivation for this work. (The original work pursuing this line of reasoning was Turberfield et al 2003 [ref 1] and further progress was made in "DNA Hybridization Catalysts and Catalyst Circuits" [ref 37, see below]. Here, we finally have a system that works quite nicely.) {apologies to ee cummings}
[JACS, 128(37): 12211-12220, 2006 (5 pages): .pdf, 1.4 MB. ]
Sturdier DNA Nanotubes via Ligation. *
Patrick O'Neill, Paul W. K. Rothemund, Ashish Kumar and Deborah K. Fygenson
Deborah's group decides to ligate DNA nanotubes. They are stable under a fluorescence microscope up to 70C and, unlike noncovalent tubes, resist opening under AFM. That's very, very useful!
[Nano Letters 6(7): 1379-1383, 2006 (5 pages): .pdf, 286 KB. See also supplementary pdf, 27KB. ]
A DNA Superstructure-based Replicator without Product Inhibition. *
David Yu Zhang and Bernard Yurke.
DNA replication, when one becomes two, marks the fundamental moment in life. How simple can the machinery for replication be? Can it be designed from scratch? Dave and Bernie present here a proposal for a clock-work machine -- an information-bearing superstructure made entirely of multi-base DNA building-block motifs -- that replicates its overall structure when exposed to the proper sequence of raw building blocks and fuel. So it's theoretically possible. This throws down the gauntlet: Can an autonomous scheme be devised? Can a simpler implementation be found, one practical enough for experimental demonstration? Can a chemical self-replicator be rationally designed?
[Natural Computing 5(2): 183-202, 2006 (20 pages): .pdf, 1.3 MB. ]
Folding DNA to create nanoscale shapes and patterns. *
Paul W. K. Rothemund
Paul sends a swarm of staple strands to tie viral DNA in knots...thereby self-assembling 100 x 100 nm objects with roughly 6 nm resolution from the 7 kilobase single-stranded genomic DNA of M13mp18. Rectangles. Squares. Triangles. Stars. Even a smiley-face. About 50 billion copies of each, in a typical reaction, and with very high yields. It works like magic. We did some calculations... Paul's smiley faces constitute the most concentrated happiness ever experienced on earth. Each spot in such a structure contains a unique address and can be addressed as such by DNA hybridization, allowing one to "write" on the DNA origami objects. Words. Pictures. Snowflakes. A map of North and South America. We did some more calculations... Paul probably made more maps than have ever been produced in the history of mankind -- we're definitely talking quantity over quality here. The applications of this technology are likely to be less whimsical. For example, it can be used as a "nanobreadboard" for attaching almost arbitrary nanometer-scale components, and there are few other ways to obtain such precise control over the arrangement of components at this scale. You'll never look at M13 phage DNA the same way again...
[Nature 440, 297-302 (16 March 2006). article, .pdf, 575 KB. News and View, .pdf, 300 KB. Supplementary material: .pdf, part 1, 6.3 MB; .pdf, part 2, 193 KB. Caltech's Press Release. ]
Design of DNA origami. *
Paul W. K. Rothemund
Paul talks a little about the design software and future possibilities.
[Proceedings of the International Conference on Computer-Aided Design (ICCAD) 2005: .pdf, 646 KB.]
Scaffolded DNA Origami: from Generalized Multicrossovers to Polygonal Networks. *
Paul W. K. Rothemund
Paul makes a DNA origami especially for Ned Seeman, and sketches how polygonal networks and polygonal three-dimensional structures can be created.
[in Nanotechnology: Science and Computation, pages 3-21, 2006. Preprint (22 pages): .pdf, 1.4 MB.]
Self-Healing Tile Sets. *
Erik Winfree.
Wandering in the dreamy fields of abstraction and metaphor, I like to think of algorithmic self-assembly as a toy model of organismal development. A tile set can direct the growth of an algorithmic pattern from a seed assembly "in the same way" as genetic DNA directs the growth of a salamander from an egg. Similar principles seem to be at work in both systems: information flow is essential, sophisticated programming is possible, the physics and chemistry is messy but fault-tolerance can be achieved. The adult salamander, however, can do something that has not previously been shown in algorithmic self-assembly -- after losing its tail, the salamander can regrow a new one! Perhaps more remarkable, actually, is the ability of almost all multicellular organisms to heal severe wounds within their bodies. In this paper I investigate a (somewhat) analogous issue for algorithmic self-assembly, and show that self-healing tile sets are possible.
[in Nanotechnology: Science and Computation, pages 55-78, 2006. Preprint (24 pages): .pdf, 431 KB.]
[Note, a one-page abstract of this work appeared in the FNANO 2005 conference proceedings. Unfortunately, the 3x3 self-healing transformation in the figure shown there had an error in the boundary and seed tile blocks. EW 8/05]
Two Computational Primitives for Algorithmic Self-Assembly: Copying and Counting. *
Robert D. Barish, Paul W. K. Rothemund, and Erik Winfree
Here we demonstrate crystals that count and tubes that copy. This is interesting as the second example of algorithmic self-assembly. Counting is a useful primitive for bottom-up fabrication tasks such as constructing a memory chip with address demultiplexers. Copying is a useful primitive for Darwinian evolution. The error rates in this work, however, strongly motivate research into "proofreading" and other methods for fault-tolerant self-assembly.
[Nano Letters 5(12): 2586-2592, 2005 (7 pages): .pdf, 515 KB. See also the Supplementary Materials (.pdf), 622 KB and our Extra Supplementary Materials page.]
Complexity of Compact Proofreading for Self-Assembled Patterns. *
David Soloveichik and Erik Winfree.
Presumably, there is some cost for obtaining low error rates during self-assembly. Maybe assembly must be slower. Or the same pattern can be assembled more reliably, but using more tile types. Or the pattern must be assembled at a larger scale. Or all of the above. In fact, Chen and Goel (2005) proved that if you can accept "just a little slower", "just a few more tiles", and "just a slightly larger scale", then any self-assembled pattern can be made as reliable as you want. But suppose you insist that the pattern remain at exactly the original scale, as do Reif, Sahu, and Yin (2005) ? We give evidence that for some patterns -- which we term "robust" -- it is still possible to do arbitrarily strong proofreading with modest costs in speed and tile set size, but for other patterns -- which we term "fragile" -- it is not... at least, not with any proofreading scheme that uses a certain kind of redundancy.
[Published in DNA Computing 11, LNCS 3892: 305-324 (2006): .pdf, 595 KB.] [Preprint, typos corrected 3/29/2006 (20 pages): .pdf, 237 KB.]
Self-Replication and Evolution of DNA Crystals. *
Rebecca Schulman and Erik Winfree.
What is the simplest physical system capable of extensive Darwinian evolution? Such a system might be a candidate for the origin of life. One would expect that it must have certain features: it must be capable of of reproducing as an organism to populate an environmental niche; of storing an unbounded amount of information in its "genome"; of copying that information with low error rates; and of expressing that information as a phenotype with selective advantages or disadvantages. Graham Cairns-Smith has argued, since the 1960's, that mineral crystals (such as clays) provide the most compelling example of a simple and abundant physical system capable of extensive Darwinian evolution: Clay crystals can store information as a pattern of inhomogeneities that are propagated from layer to layer, with few errors; they can reproduce by random fragmentation; and they can express a variety of morphological phenotypes. To be blunt, he proposes that your great-great-great-great-great-....-grandparent was a lump of clay. I think he may be right. But the evidence is thin: to date, no one has managed to catch clay in the act of replicating information or evolving. In this paper, we propose using experimentally-tractable DNA tile self-assembly to investigate how evolution could conceivably work on information-bearing crystals.
Won the conference best paper award! (of 94 papers)
[ECAL 2005, in LNCS 3630:734-743, 2005. Preprint (10 pages): .pdf, 2.3 MB, .ps, 9.3 MB] .]
The Computational Power of Benenson Automata. *
David Soloveichik and Erik Winfree.
In a series of experimental papers, Benenson et al demonstrated how information encoded in DNA can be processed autonomously by a molecular automaton consisting of a type IIS restriction enzyme (FokI) and a collection of DNA "rule molecules". They constructed several two-symbol, two-state finite state machines as well as several 4-input AND/NOT gates. Ultimately, applications envisioned include diagnosis of mRNA and delivery of a theraputic molecule. Here, we formalize the class of logical computations that can be performed by such systems and show that, in our abstraction, the finite-input computations that can be performed by Benenson automata can be exactly characterized by a connection to branching programs -- which indicates that (if restriction enzymes slightly more powerful than FokI can be found) Benenson automata are considerably more powerful than we had originally imagined!
[Preprint: cs.CC/0412097 on arXiv.org (18 pages): .pdf, 223 KB.]
[Journal version: Theoretical Computer Science 244(2-3):279-297, 2005, (19 pages): .pdf, 192 KB.]
[Note: Thanks to remarkably thorough comments from the reviewers, the clarity and precision of the definitions and proofs in the journal version have been improved substantially. Read this version, not the arxiv version!]
Algorithmic Self-Assembly of DNA Sierpinski Triangles. *
Paul W. K. Rothemund, Nick Papadakis, Erik Winfree.
Our first demonstration of algorithmic crystals, wherein molecularly-encoded information directs the growth process to create a complex pattern. The DNA crystals are, at the molecular level, a two-dimensional woven fabric of short DNA strands. Both because this programmable growth could be considered a super-simplified toy model of organismal development, and because DNA is the central information molecule in biology, I like to call it "weaving the tapestry of life". This is a substantial personal victory for me: I proposed that this should be possible in 1995 as a graduate student -- nearly 10 years later, Paul's efforts made it actually happen.
[PLoS Biology 2 (12) e424, 2004, (13 pages): .pdf, 4.6 MB.] See also our Extra Supplementary Materials page. (PLoS Biology has a synopsis and a primer by Chengde Mao for this paper. Also it was highlighted in Nature by Philip Ball. And there's a Caltech Press Release. )
Design and Characterization of Programmable DNA Nanotubes. *
Paul W. K. Rothemund, Axel Ekani-Nkodo, Nick Papadakis, Ashish Kumar, Deborah Kuchnir Fygenson, Erik Winfree.
DNA tiles designed to make sheets sometimes roll up into tubes that are abstractly analogous to protein microtubules that self-assemble from tubulin. Way cool! Fortuitously discovered during Paul's work on the DNA Sierpinski triangles, DNA nanotubes have opened up a whole host of interesting possibilities that we never dreamed of before...
[JACS 126(50):16344-16353, 2004, (9 pages): .pdf, 891 KB.] See also our Extra Supplementary Materials page.
Neural Network Computation by in vitro Transcriptional Circuits. *
Jongmin Kim, John J. Hopfield, Erik Winfree.
Is it possible to design biochemical circuits in the same way we design electrical circuits -- where the information processing and dynamics is what we're interested in, rather than the chemistry per se? What kinds of dynamical and decision-making behavior can be achieved this way? In this paper, we give a concrete proposal for how to use synthetic DNA molecules and a few enzymes (RNA polymerase and some ribonucleases) to make general-purpose threshold gates that can be wired together to make arbitrary circuits. The mathematical description turns out to be closely related to continuous-time analog neural networks. We analyze a few example circuits.
[Advances in Neural Information Processing Systems (NIPS) 17, 2004, pg 681-688. preprint, (8 pages): .pdf, 426 KB.]
DNA Hybridization Catalysts and Catalyst Circuits. *
Georg Seelig and Bernard Yurke and Erik Winfree.
Energy stored in metastable configurations of DNA molecules can in principle be used to power DNA nanomachines and other molecular processes. Essential to using this energy productively is the ability to regulate how and when the energy is released. Starting with a previously-demonstrated DNA hybridization catalyst for doing exactly that, we introduce schemes for an improved catalyst and for networks of catalysts that operate as computing circuits. We show preliminary experimental results investigating these proposals -- which uncover a few interesting surprises!
[in DNA Computers 10, LNCS volume 3384:329-343, 2005, (15 pages): .pdf, 361 KB]
Programmable Control of Nucleation for Algorithmic Self-Assembly. *
Rebecca Schulman and Erik Winfree.
When writing a computer program, it is easy -- so trivial you don't even think about it -- to make sure that your algorithm starts with the correct input and proceeds from there. Models of algorithmic self-assembly usually assume that assembly begins with a "seed tile" which provides the input information. But molecular self-assembly is an inherently parallel process; assembly begins anywhere it is energetically favored. In this paper we show that tile sets can be constructed that introduce arbitrarily large barriers to spurious nucleation (starting self-assembly from something other that the seed tile). By combining this construction with previous methods for proofreading tile sets, we can now construct tile sets that are robust to all major types of errors, without introducing significant slow-down. Control of nucleation also has some very interesting applications, such as enzyme-free detection and amplification, and enzyme-free in-vitro evolution.
[SIAM Journal on Computing 39 (4) pp. 1581-1616, December 4, 2009, (36 pages) .pdf, 1.5 MB.]
[preprint cond-mat/0607317 on arXiv.org (22 pages): .pdf, 728 KB]
[extended abstract in DNA Computers 10, LNCS volume 3384: 319-328, 2005, (10 pages): .pdf, 176 KB]
Complexity of Self-Assembled Shapes. *
David Soloveichik and Erik Winfree.
If you can effectively describe a shape -- e.g. write a computer program that draws it -- then can the shape be self-assembled by spontaneous local processes from just a few kinds of pieces? The answer may be "no" if you are concerned about the exact size of the shape, but if it is only the form of the shape that matters, then the answer is always "yes". In fact, the Kolmogorov complexity of a shape provides upper and lower bounds for the number of tile types necessary to self-assemble it (at some scale). Proof of this result makes use of a construction for programmable "blocks" that execute a Turing machine simulation to guide the growth process, and introduces a new proof technique for establishing when growth is independent of the order in which tiles are added. This work suggests that scale plays the same role in self-assembly as does time in computability: when you ignore it and just ask, "can it be done at all?", then the theory becomes clean and elegant.
[SIAM Journal on Computing 36 (6) 1544-1569, 2007, (26 pages) paper, 810 KB.]
[preprint cs.CC/0412096 on arXiv.org (25 pages): .pdf, 488 KB.]
[extended abstract in DNA Computers 10, LNCS volume 3384:344-354, 2005, (10 pages): .pdf, 272 KB, color, .pdf, 271 KB, B/W]
Paradigms for Computational Nucleic Acid Design. *
Robert M. Dirks, Milo Lin, Erik Winfree and Niles A. Pierce.
What constitutes a good design criterion for choosing DNA sequences that (should) fold up into target nanostructures? We argue that both positive (the target structure should have low energy) and negative (all other structures should have high energy) design criteria should be considered. Secondary structure formalisms for describing and analyzing DNA molecules allow these criteria to be rigorously treated computationally.
[preprint with clear figures: .pdf, 6.4 MB]
[published in Nucleic Acids Research: 32(4):1392-1403, 2004, (17 pages, in color): .pdf, 503KB; supplemental.pdf, 2.7MB; sequences.gz, 2.8MB]
Proofreading Tile Sets: Error Correction for Algorithmic Self-Assembly. *
Erik Winfree and Renat Bekbolatov.
Experimental studies of algorithmic self-assembly have observed error rates between 1 and 10 %, measured as the fraction of DNA tiles that fail to perfectly match their neighbors. It is difficult to perform extended computations when every elemental logical operation is so likely to be wrong. Here, we provide a general-purpose technique for designing tile sets that are robust to assembly errors. Kinetic and thermodynamic models of self-assembly are key to our investigations. It is suggested that proofreading tile sets can square the error rate for comparable physical conditions -- i.e. bring 10% to 1% and bring 1% to .01%.
[in DNA Computers 9, LNCS volume 2943:126-144, 2004, (19 pages, in color): .pdf, 2.0 MB, .ps, 18 MB]
See also our Extra Supplementary Material page. [Note: Typo in Fig 7b: "FC" on the left should be "FM".]
Self-Assembled Circuit Patterns. *
Matthew Cook, Paul W. K. Rothemund, and Erik Winfree.
Can DNA self-assembly be used for patterning, as a scaffold for functional devices such as molecular electronic circuits? We show that several circuit patterns, including demultiplexers, random-access memory, and Hadamard matrix transforms, can be self-assembled (in principle) from a small number of tile types.
[in DNA Computers 9, LNCS volume 2943:91-107, 2004. (17 pages, in color): .pdf, 608 KB, .ps, 3.2 MB]
One Dimensional Boundaries for DNA Tile Self-Assembly. *
Rebecca Schulman, Shaun Lee, Nick Papadakis, and Erik Winfree.
Discusses our progress toward using DNA tiles to self-assembly the boundary for a self-assembled Sierpinski triangle. Experimental results show that individual tiles behave well, with the expected tile-tile interactions, but size and shape distributions of self-assembled structures were sometimes surprising and unsatisfactory. We understand this by analyzing models of 1D polymerization, for example distinguishing accretion from a seed vs. parallel aggregation. This work identifies control over nucleation as an important target for future study in algorithmic self-assembly.
[in DNA Computers 9, LNCS volume 2943:108-125, 2004, (19 pages, in color): .pdf, 2.1 MB, .ps.gz, 8.7 MB, .ps, 49 MB]
See also our Extra Supplementary Material page.
DNA Computing by Self-Assembly. *
Erik Winfree.
A brief review of algorithmic self-assembly of DNA.
[in NAE's The Bridge, 33(4):31-38, 2003 (8 pages): preprint in color .pdf, 350KB, or as published in B/W .pdf, 275KB]
Protein Design is NP-Hard. *
Niles Pierce and Erik Winfree.
Shows that a commonly-used formulation for protein design -- amino acid sequence selection to stabilize a given backbone fold using a pairwise energy model -- is NP-Hard if the energy function is considered part of the specification of the problem (as it is in common practice, since this is the implicit formulation of the target backbone fold). Therefore, it may be advantageous to exploit specific properties of protein folding energetics, rather than relying on general-purpose (worst-case) exponential-time algorithms.
[in Protein Engineering, v15, pp. 779-782, 2002 (4 pages): PRODES.pdf, 1.1 MB]
Combinatorial Optimization Problems in Self Assembly. *
Leonard Adleman, Qi Cheng, Ashish Goel, Ming-deh-Huang, David Kempe, Pablo Moisset, Paul Rothemund
Can one find the minimal number of tiles required to uniquely produce a given shape? Here we prove that the problem is NP-complete. Also, for a large class of tile sets we give a method to find concentrations of tiles that yield the fastest time of self-assembly.
[in STOC 2002, (10 pages): .pdf, 731 KB, .ps, 537 KB]
Paul's PhD Thesis: Theory and Experiments in Algorithmic Self-Assembly. *
283 pages, in black and white. University of Southern California, December 2001.
Paul W. K. Rothemund. Thesis advisor: Leonard Adleman.
This thesis describes theory on the uniqueness of self-assembled structures with an expanded account of material in the paper "The Program-Size Complexity of Self-Assembled Squares" (see below), experiments in algorithmic capillary force-based self-assembly as well as capillary force-based assembly of Penrose tilings, and DNA computation for breaking the Data Encryption Standard (DES). It has appendices detailing the frequency of certain tile configurations (vertex stars) in the Penrose tiling and an initial experiment in making capillary force-based gears.
[pwkr_thesis_nov15.ps, 49.8 MB, or pwkr_thesis_nov15.ps.gz, 8.8 MB, or pwkr_thesis_nov15.pdf, 9.1 MB]
Algorithmic Self-Assembly of DNA: Theoretical Motivations and 2D Assembly Experiments. *
Erik Winfree.
Overview discussion of Wang tiles, computation by self-assembly, and previous experimental results, as well as some additional experiments using the system described in Nature 394, 539-544, Aug. 6, 1998 -- see below.
[in Journal of Biomolecular Structure and Dynamics, 11 (S2): 263-270, 2000, (8 pages, in color): algSA_JBSD.pdf, 746 KB, or algSA_JBSD.ps.gz, 3.3 MB]
[Erratum: In figure 6 on page 266, the lower right sticky end sequence of the B tile should be AGTGA instead of ATGTA, to be complementary with the upper left one of the A tile.]
Two Dimensional and Two States in DNA Nanotechnology. *
Nadrian C. Seeman, Furong Liu, Chengde Mao, Xiaoping Yang, Lisa A. Wenzler, Ruojie Sha, Weiqiong Sun, Zhiyong Shen, Xiaojun Li, Jing Qi, Yuwen Zhang, Tsu-Ju Fu, Junghuei Chen and Erik Winfree.
This brief review, written by Ned Seeman, describes the state of DNA nanotechnology in the year 2000, including the recent results described in Nature 394, 539-544, Aug. 6, 1998 -- see below.
[in Journal of Biomolecular Structure and Dynamics, 11 (S2): 253-262, 2000, (10 pages, B/W): TwoDimTwoStates.pdf, 554 KB]
String Tile Models for DNA Computing by Self-Assembly. *
Erik Winfree, Tony Eng, Grzegorz Rozenberg.
How much computation can be done with linear self-assembly? With some tricky strand routing through complex DNA tiles, you can do a lot!
[in DNA Based Computers 6, LNCS 2054, pp. 63-88, 2001, (26 pages, in color): stringtiles.pdf, 679 KB, or stringtiles.ps, 1.6 MB]
[early draft, 6/2000: stringtiles_DN6.ps.gz, 225 KB]
The Program-Size Complexity of Self-Assembled Squares. *
Paul W. K. Rothemund and Erik Winfree.
Are there small self-assembly programs for building squares of a particular size? Yes! Also contains a nice presentation of our model of self-assembly.
[in STOC 2000, (10 pages): squares_STOC.ps.gz, 114 KB, squares_STOC.ps, 761 KB, or squares_STOC.pdf, 243 KB]
Construction, analysis, ligation, and self-assembly of DNA triple crossover complexes. *
Thomas H. LaBean, Hao Yan, Jens Kopatsch, Furong Liu, Erik Winfree, John H. Reif, Nadrian C. Seeman.
2D crystals can be made from fancier DNA complexes that allow for baroque strand routing.
[in Journal of the American Chemical Society, 122(9): 1848-1860, 2000, (13 pages): triplex.ps.gz, 906 KB, or triplex.pdf, 712 KB]
Using lateral capillary forces to compute by self-assembly. *
Paul W. K. Rothemund.
Here Paul used macroscopic plastic tiles to test ideas about algorithmic self-assembly. The plastic tiles self-assemble at the interface of oil and water, and hydrophilic and hydrophobic patches on the edges of the tiles mediate the specific binding interactions between them. Tiles in this paper encode binding interactions for creating Sierpinski triangles as well as Penrose tilings. Paul had mild success creating unnucleated patterns with Sierpinski tiles and perhaps created the most complex set of specific capillary bonds ever made.
[in Proceedings of the National Academy of Sciences, 97(3): 984-989, 2000, (6 pages): Rothemund-PNAS-capillary.pdf, 911KB]
Experimental Progress in Computation by Self-Assembly of DNA Tilings. *
Thomas H. LaBean, Erik Winfree, John H. Reif.
Describes experimental characterization of three-helix DNA complexes, shows that multiple TX can assemble around a template strand, and illustrates how they could be used to self-assemble an addition table.
[in DNA Based Computers 5, pp. 123-140, 1999, (18 pages): LaBeanTX.pdf, 497 KB, or LaBeanTX.ps.gz, 600 KB, or LaBeanTX.ps, 2.3 MB]
Error Correction in DNA Computing: Misclassification and Strand Loss. *
Kevin Chen and Erik Winfree.
Update on Rowies et al: shows that misclassification can be ameliorated by repeated separation, and strand loss can be recovered by PCR, resulting in reliable computation at the cost of moderately more time and space. *IF* there is no sequence-specific bias to the errors.
[in DNA Based Computers 5, pp. 49-63, 1999, (16 pages): kevin.pdf, 304 KB, or kevin.ps.gz, 100 KB, or kevin.ps, 416 KB]
Design and self-assembly of two-dimensional DNA crystals. *
Erik Winfree, Furong Liu, Lisa Wenzler, Nadrian C. Seeman.
Periodic lattices of DNA double-crossover molecules, of the type proposed in "On the Computational Power of DNA Annealing and Ligation", are demonstrated experimentally.
[in Nature 394, 539-544, Aug. 6, 1998, (6 pages): lattice.pdf, 3.8 MB, or lattice.ps.gz, 710 KB, or lattice.ps, 1.1 MB]
[supplementary material: Supp. Material 1, 5KB, or Supp. Material 2, 9KB]
Erik's PhD Thesis: Algorithmic Self-Assembly of DNA. *
110 pages, Caltech, June 1998.
Erik Winfree . Thesis advisor: John Hopfield.
The contents of several of the above papers are included here; in addition there are many more experimental results. Note that pages 61, 72, and 87 are in color.
[thesis.ps.gz, 5 MB, or thesis.pdf, 2.6 MB, or thesis.ps, 21 MB, or the Caltech official library copy]
Simulations of Computing by Self-Assembly. *
Erik Winfree.
A kinetic and thermodynamic analysis of error rates in a simple model of the two-dimensional self-assembly process proposed in my first paper on this topic, "Annealing and Ligation".
[presented at DNA Based Computers IV; published as Caltech CS Tech Report 1998.22, (25 pages): simulation.ps.gz, 392 KB, or simulation.pdf, 1.0 MB, or simulation.ps, 3.1 MB]
Whiplash PCR for O(1) Computing. *
Erik Winfree.
Some comments and extensions to the "one-pot" PCR-like technique of [Hagiya,Arita,Kiga,Sakamoto,Yokoyama in DNA Based Computers III], including a a way for a single DNA strand to simulate the execution of circuit.
[presented at DNA Based Computers IV; published as Caltech CS Tech Report 1998.23, (14 pages): whiplash.pdf, 331 KB, or whiplash.ps.gz, 136 KB, or whiplash.ps, 666 KB]
Universal Computation via Self-assembly of DNA: Some Theory and Experiments. *
Erik Winfree, Xiaoping Yang, Nadrian C. Seeman.
This follow-up to "Annealing and Ligation" (below) examines the relationship of DNA self-assembly to formal language theory -- finding ties to regular, context-free, and recursively enumerable languages. Additionally, preliminary laboratory investigations into the self-assembly required for universal computation is reported.
[in DNA Based Computers II, pgs 191-213, 1998 (22 pages): self-assem.ps.gz, 546 KB, or self-assem.pdf, 627 KB, or self-assem.ps, 2.6 MB]
[Note, there are a few typographical errors in important definitions. EW, 6/98]
A Sticker Based Architecture for DNA Computation. *
Sam Roweis, Erik Winfree, Richard Burgoyne, Nickolas V. Chelyapov, Myron F. Goodman, Paul W. K. Rothemund, Leonard M. Adleman.
A new representation for encoding bits in DNA is presented and examined, and generally applicable methods for decreasing separation error rates are discussed.
[in DNA Based Computers II, pgs 1-29, 1998 (26 pages): stickers.pdf, 611 KB, or stickers.ps.gz, 231 KB, or stickers.ps, 1.2 MB]
This appeared in journal form as two papers:
A Sticker-Based Model for DNA Computatation.
Sam Roweis, Erik Winfree, Richard Burgoyne, Nickolas V. Chelyapov, Myron F. Goodman, Paul W. K. Rothemund, Leonard M. Adleman.
[ Journal of Computational Biology, 5(4): 615-29, 1998 .pdf, 1.3 MB]
and
On the Reduction of Errors in DNA Computation.
Sam Roweis and Erik Winfree.
[ Journal of Computational Biology, 6(1): 65--5, 1999 .pdf, 884 KB]
On Applying Molecular Computation to the Data Encryption Standard. *
Leonard M. Adleman, Paul W. K. Rothemund, Sam Roweis, Erik Winfree.
An algorithm for breaking DES is designed for the Stickers model. Size, space, and error rates of the resulting machine are considered.
[in DNA Based Computers II, pgs 31-44, 1998 (21 pages): des.pdf, 185 KB, or des.ps.gz, 77 KB, or des.ps, 211 KB]
The journal version: [ Journal of Computational Biology, 6(1): 53-63, 1999 .pdf, 771 KB]
On the Computational Power of DNA Annealing and Ligation. *
Erik Winfree.
Here I show how one might create a "one-pot" mixture of DNA which can perform universal computation by self-assembly of DNA double crossover units. A.k.a. "weaving the tapestry of life".
[in DNA Based Computers, pgs 199-221, 1996, (13 pages): ligation.ps.gz, 157 KB, or ligation.ps, 951KB, or ligation.pdf, 314KB]
[Note, there are strand polarity errors in several figures. EW, 5/96]
Complexity of Restricted and Unrestricted Models of Molecular Computation. *
Erik Winfree.
Here I show some limits on what can be computed using some proposed operations on DNA. In particular, how affinity separation w/ or w/o amplification relates to branching programs and non-deterministic branching programs. These limits have since been overcome by the inclusion of additional operations, such as ligation.
[in DNA Based Computers, pgs 187-198, 1996, (8 pages): models.ps.gz, 72KB, or models.ps, 195KB, or models.pdf, 209KB]
A DNA and restriction enzyme implementation of Turing Machines. *
Paul W. K. Rothemund.
Here Paul gives a construction for simulating Minsky's 4 symbol, 7 state universal Turing machine using DNA, the type IIS restriction enzyme Fok I, and ligase. The encoding of machine state and current symbol used in this paper was later used by Kobi Benenson of Udi Shapiro's group to create DNA finite state machines and hence such machines have been called Rothemund-Shapiro machines.
[in DNA Based Computers, pgs 75-120, 1996, (29 pages below): dimacs.ps, 578KB, or dimacs.pdf, 330KB]
Organizing Centers in a Cellular Excitable Medium. *
Arthur T. Winfree, Erik M. Winfree, and Herbert Seifert.
Excitable media support directed wave propagation that, unlike linear waves, are directed and self-sustaining but annihilate each other when they collide. Examples include, in one dimension, action potential propagation along a neuron; in two dimensions, a slow-moving fire burning across a quick-growing plain of grass leaving a thin zone of burnt grass in its wake; in three dimensions, the electrical-contractile waves that make heart muscle beat. The Belousov-Zhabotinski reaction provides a simple chemical analog in any dimension, and the Greenberg-Hastings cellular automaton provides a simple discrete model that exhibits many of the same qualitative behaviors. The most striking behavior of excitable media in two dimensions is that after part of a wavefront is rubbed out, a spiral pattern develops as the wavefront swirls around its end. In three dimensions, one observes a wavesheet rather than a wavefront -- and if one rubs out a hole in that wavesheet, what develops is a remarkable three dimensional spiral. In fact there are an infinite variety of topologically distinct three dimensional spirals, each corresponding to the Seifert surface of a distinct knot. We simulated two such spirals in a three dimensional Greenberg-Hastings cellular automaton.
[in Physica 17D (1985), 109-115 (7 pages): .pdf, 487KB.]
P.S. This is my first published work! My contribution, as a high school student, was to write the program for simulating the cellular automaton and visualizing initial conditions and the resulting three dimensional pattern formation.

Reference details for DNA Computing conference proceedings:

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 to

winfree@caltech.edu