Programmability of Chemical Reaction Networks (2009)
Matthew Cook, David Soloveichik, Erik Winfree, Jehoshua Bruck
Summary. Motivated by the intriguing complexity of biochemical circuitry within individual cells we study Stochastic Chemical Reaction Networks (SCRNs), a formal model that considers a set of...
Sequences and Synthesis (2009)
Rebecca Schulman, Erik Winfree
While several of the double-stranded (core) sequences for tiles were identical to those used in earlier experiments [1], we designed all the sticky end sequences and the sequences for tiles Z9-Z12...
How Crystals that Sense and Respond to Their Environments Could Evolve (2009)
Rebecca Schulman, Erik Winfree
Abstract. An enduring mystery in biology is how a physical entity simple enough to have arisen spontaneously could have evolved into the complex life seen on Earth today. Cairns-Smith has proposed...
A simple DNA gate motif for synthesizing large-scale circuits (2009)
Abstract. The prospects of programming molecular systems to perform complex autonomous tasks has motivated research into the design of synthetic biochemical circuits. Of particular interest to us are...
COMBINING SELF-HEALING AND PROOFREADING IN SELF-ASSEMBLY (2009)
David Soloveichik, Matthew Cook, Erik Winfree
Abstract. Molecular self-assembly is a promising approach to bottom-up fabrication of complex structures. A major impediment to the practical use of self-assembly to create complex structures is the...
Algorithmic self-assembly of DNA Sierpinski triangles (2009)
Algorithms and information, fundamental to technological and biological organization, are also an essential aspect of many elementary physical phenomena, such as molecular self-assembly. Here we...
David Yu Zhang, Andrew J. Turberfield, Bernard Yurke, Erik Winfree, David Y Zhang, Andrew J Turberfield, ...
S1. DNA sequence design The DNA sequence design process was done on a domain level. Domains denoted by unmodified numbers are termed primary domains, while domains denoted by barred numbers are...
Paradigms for computational nucleic acid design (2009)
Robert M. Dirks, Milo Lin, Erik Winfree, Niles A. Pierce
The design of DNA and RNA sequences is critical for many endeavors, from DNA nanotechnology, to PCR-based applications, to DNA hybridization arrays. Results in the literature rely on a wide variety...
DNA as a Universal Substrate for Chemical Kinetics (Extended Abstract) (2009)
David Soloveichik, Georg Seelig, Erik Winfree
Abstract. We show that a DNA-based chemical system can be constructed such that it closely approximates the dynamic behavior of an arbitrary system of coupled chemical reactions. Using strand...
Algorithmic Bioprocesses (2009)
Condon, Anne, Harel, David, Kok, Joost, Salomaa, Arto, Winfree, Erik
An information-bearing seed for nucleating algorithmic self-assembly (2009)
Barish, Robert D., Schulman, Rebecca, Rothemund, Paul W. K., Winfree, Erik
Self-assembly creates natural mineral, chemical, and biological structures of great complexity. Often, the same starting materials have the potential to form an infinite variety of distinct...
Protein Engineering vol.15 no.10 pp.779–782, 2002 Protein Design is NP-hard (2008)
2To whom correspondence should be addressed.
Thomas H. Labean, Erik Winfree, John H. Reif
Abstract. Approaches to DNA-based computing by self-assembly require the use of DNA nanostructures, called tiles, that have e cient chemistries, expressive computational power, and convenient input...
Dynamic allosteric control of noncovalent DNA catalysis reactions (2008)
Zhang, David Yu, Winfree, Erik
Allosteric modulation of catalysis kinetics is prevalent in proteins and has been rationally designed for ribozymes. Here, we present an allosteric DNA molecule that, in its active configuration,...
Programmability of Chemical Reaction Networks (2008)
Cook, Matthew, Soloveichik, David, Winfree, Erik, Bruck, Jehoshua
Motivated by the intriguing complexity of biochemical circuitry within individual cells we study Stochastic Chemical Reaction Networks (SCRNs), a formal model that considers a set of chemical...
Complexity of Self-Assembled Shapes (Extended Abstract ⋆) (2008)
David Soloveichik, Erik Winfree
Abstract. The connection between self-assembly and computation suggests that a shape can be considered the output of a self-assembly “program,” a set of tiles that fit together to create a shape....
Fujibayashi, Kenichi, Hariadi, Rizal, Park, Sung Ha, Winfree, Erik, Murata, Satoshi
Bottom-up fabrication of nanoscale structures relies on chemical processes to direct, self-assembly. The complexity, precision, and yield achievable by a one-pot reaction are limited by our ability...
COMPUTATION WITH FINITE STOCHASTIC CHEMICAL REACTION NETWORKS (2008)
David Soloveichik, Matthew Cook, Erik Winfree, Jehoshua Bruck
Abstract. A highly desired part of the synthetic biology toolbox is an embedded chemical microcontroller, capable of autonomously following a logic program specified by a set of instructions, and...
Neural network computation by in vitro transcriptional circuits (2004 (2008)
Jongmin Kim, John J. Hopfield, Erik Winfree
The structural similarity of neural networks and genetic regulatory networks to digital circuits, and hence to each other, was noted from the very beginning of their study [1, 2]. In this work, we...
DNA Hybridization Catalysts and Catalyst Circuits (2008)
Georg Seelig, Bernard Yurke, Erik Winfree
Abstract. Practically all of life’s molecular processes, from chemical synthesis to replication, involve enzymes that carry out their functions through the catalysis of metastable fuels into waste...
INFORMATION AND ALGORITHMS IN BIOCHEMISTRY (2008)
Information and algorithms appear to be central to biological organization and processes, from the storage and reproduction of genetic information to the control of developmental processes to the...
• Charles H. Wilts Prize for the best dissertation in Electrical Engineering (2008)
E. California Blvd, Marc D. Riedel, Erik Winfree, Andrew Viterbi
to be submitted to IEEE Transactions on Computers.
Complexity of Self-Assembled Shapes (Extended Abstract ⋆) (2008)
David Soloveichik, Erik Winfree
Abstract. The connection between self-assembly and computation suggests that a shape can be considered the output of a self-assembly “program,” a set of tiles that fit together to create a shape....
Strand Loss, Kevin Chen, Erik Winfree
Abstract. We present a method of transforming an extract-based DNA computation that is error-prone into one that is relatively error-free. These improvements in error rates are achieved without the...
Error Correction for DNA Self-Assembly: Preventing Facet Nucleation (2008)
Ho-lin Chen, Ashish Goel, Rebecca Schulman, Erik Winfree
Abstract. Algorithmic self-assembly has been proposed as a mechanism for bottom-up construction of nanostructures and autonomous DNA computation. For these applications, we are often interested in...
Error Correction for DNA Self-Assembly: Preventing Facet Nucleation (2008)
Ho-lin Chen, Ashish Goel, Rebecca Schulman, Erik Winfree
Abstract. Algorithmic self-assembly has been proposed as a mechanism for bottom-up construction of nanostructures and autonomous DNA computation. For these applications, we are often interested in...
Computation with Finite Stochastic Chemical Reaction Networks (2008)
Soloveichik, David, Cook, Matthew, Winfree, Erik, Bruck, Jehoshua
A highly desired part of the synthetic biology toolbox is an embedded chemical microcontroller, capable of autonomously following a logic program specified by a set of instructions, and interacting...
Computation with finite stochastic chemical reaction networks (2008)
David Soloveichik, Matthew Cook, Erik Winfree, Jehoshua Bruck
Abstract. A highly desired part of the synthetic biology toolbox is an embedded chemical microcontroller, capable of autonomously following a logic program specified by a set of instructions, and...
Sam Roweis, Erik Winfree, Richard Burgoyne, Nickolas V. Chelyapov, Myron F. Goodman, ...
We introduce a new model of molecular computation that we call the sticker model. Like many previous proposals it makes use of DNA strands as the physical substrate in which information is...
Synthesis of crystals with a programmable kinetic barrier to nucleation (2007)
Schulman, Rebecca, Winfree, Erik
A central goal of chemistry is to fabricate supramolecular structures of defined function and composition. In biology, control of supramolecular synthesis is often achieved through precise control...
Reducing facet nucleation during algorithmic self-assembly (2007)
Chen, Ho-Lin, Schulman, Rebecca, Goel, Ashish, Winfree, Erik
Algorithmic self-assembly, a generalization of crystal growth, has been proposed as a mechanism for bottom-up fabrication of complex nanostructures and autonomous DNA computation. In principle,...
Complexity of Self-Assembled Shapes (2007)
Soloveichik, David, Winfree, Erik
The connection between self-assembly and computation suggests that a shape can be considered the output of a self-assembly “program,” a set of tiles that fit together to create a shape. It seems...
Thermodynamic Analysis of Interacting Nucleic Acid Strands (2007)
Dirks, Robert M., Bois, Justin S., Schaeffer, Joseph M., Winfree, Erik, Pierce, Niles A.
Motivated by the analysis of natural and engineered DNA and RNA systems, we present the first algorithm for calculating the partition function of an unpseudoknotted complex of multiple interacting...
Holin Chen, Ashish Goel, Erik Winfree, Chris Luhrs
Tile systems have proved to be a useful model for understanding self-assembly at the nano scale. Self-healing tile systems, introduced by Winfree, have the property that the self-assembled shape can...
Kenichi Fujibayashi, Rizal Hariadi, Sung Ha Park, Erik Winfree, Satoshi Murata
Bottom-up fabrication of nanoscale structures relies on chemical processes to direct self-assembly. The complexity, precision, and yield achievable by a one-pot reaction are limited by our ability to...
Thermodynamic analysis of interacting nucleic acid strands (2007)
Robert M. Dirks, Justin S. Bois, Joseph M. Schaeffer, Erik Winfree, Niles A. Pierce
Abstract. Motivated by the analysis of natural and engineered DNA and RNA systems, we present the first algorithm for calculating the partition function of an unpseudoknotted complex of multiple...
Ho-lin Chen, Rebecca Schulman, Ashish Goel, Erik Winfree
All reactions were performed in Tris Acetate EDTA buffer (TAE) supplemented with 12.5 µM MgCl2. Gel electrophoresis of individual tiles was performed in 10 % polyacrylamide with 0.6 % by volume 10 %...
Programmable Control of Nucleation for Algorithmic Self-Assembly (2006)
Schulman, Rebecca, Winfree, Erik
Algorithmic self-assembly, a generalization of crystal growth processes, has been proposed as a mechanism for autonomous DNA computation and for bottom-up fabrication of complex nanostructures. A...
Complexity of self-assembled shapes (2005)
David Soloveichik, Erik Winfree
Abstract. The connection between self-assembly and computation suggests that a shape can be considered the output of a self-assembly “program, ” a set of tiles that fit together to create a...
Complexity of compact proofreading for self-assembled patterns (2005)
David Soloveichik, Erik Winfree
Abstract. Fault-tolerance is a critical issue for biochemical computation. Recent theoretical work on algorithmic self-assembly has shown that error correcting tile sets are possible, and that they...
Complexity of compact proofreading for self-assembled patterns (2005)
David Soloveichik, Erik Winfree
Abstract. Fault-tolerance is a critical issue for biochemical computation. Recent theoretical work on algorithmic self-assembly has shown that error correcting tile sets are possible, and that they...
Summary. Molecular self-assembly appears to be a promising route to bottom-up fabrication of complex objects. Two major obstacles are how to create structures with more interesting organization than...
Self-replication and evolution of DNA crystals (2005)
Rebecca Schulman, Erik Winfree
Abstract. Is it possible to create a simple physical system that is capable of replicating itself? Can such a system evolve interesting behaviors, thus allowing it to adapt to a wide range of...
The computational power of benenson automata (2005)
David Soloveichik, Erik Winfree
The development of autonomous molecular computers capable of making independent decisions in vivo regarding local drug administration may revolutionize medical science. Recently Benenson at el [3]...
Programmable control of nucleation for algorithmic self-assembly (2005)
Rebecca Schulman, Erik Winfree
Abstract. Algorithmic self-assembly has been proposed as a mechanism for autonomous DNA computation and for bottom-up fabrication of complex nanodevices. Whereas much previous work has investigated...
Two computational primitives for algorithmic self-assembly: Copying and counting (2005)
Robert D. Barish, Erik Winfree
Copying and counting are useful primitive operations for computation and construction. We have made DNA crystals that copy and crystals that count as they grow. For counting, 16 oligonucleotides...
Complexity of Self-Assembled Shapes (2004)
Soloveichik, David, Winfree, Erik
The connection between self-assembly and computation suggests that a shape can be considered the output of a self-assembly ``program,'' a set of tiles that fit together to create a shape. It seems...
The Computational Power of Benenson Automata (2004)
Soloveichik, David, Winfree, Erik
The development of autonomous molecular computers capable of making independent decisions in vivo regarding local drug administration may revolutionize medical science. Recently Benenson at el (2004)...
Algorithmic Self-Assembly of DNA Sierpinski Triangles (2004)
Rothemund, Paul W. K., Papadakis, Nick, Winfree, Erik
Algorithms and information, fundamental to technological and biological organization, are also an essential aspect of many elementary physical phenomena, such as molecular self-assembly. Here we...
Algorithmic Self-Assembly of DNA Sierpinski Triangles (2004)
Engineered DNA self-assembly to produce a fractal pattern demonstrates all the necessary mechanisms for the molecular implementation of arbitrary cellular automata.
Algorithmic Self-Assembly of DNA Sierpinski Triangles (2004)
Algorithms and information, fundamental to technological and biological organization, are also an essential aspect of many elementary physical phenomena, such as molecular self-assembly. Here we...
Paradigms for computational nucleic acid design (2004)
Dirks, Robert M., Lin, Milo, Winfree, Erik, Pierce, Niles A.
The design of DNA and RNA sequences is critical for many endeavors, from DNA nanotechnology, to PCR-based applications, to DNA hybridization arrays. Results in the literature rely on a wide variety...
TileSoft: Sequence Optimization Software for Designing DNA Secondary Structures (2004)
Peng Yin, Bo Guo, Christina Belmore, Will Palmeri, Erik Winfree, Thomas H. LaBean, ...
DNA is a crucial construction material for molecular scale objects with nano-scale features. Diverse synthetic DNA objects hold great potential for applications such as nanofabrication,...
Paradigms for computational nucleic acid design (2004)
Robert M. Dirks, Milo Lin, Erik Winfree, Niles A. Pierce
The design of DNA and RNA sequences is critical for many endeavors, from DNA nanotechnology, to PCR-based applications, to DNA hybridization arrays. Results in the literature rely on a wide variety...
One dimensional boundaries for DNA tile self-assembly (2004)
Rebecca Schulman, Shaun Lee, Nick Papadakis, Erik Winfree
Abstract. In this paper we report the design and synthesis of DNA molecules (referred to as DNA tiles) with specific binding interactions that guide self-assembly to make one-dimensional assemblies...
Proofreading tile sets: Error correction for algorithmic self-assembly (2004)
Erik Winfree, Renat Bekbolatov
Abstract. For robust molecular implementation of tile-based algorithmic self-assembly, methods for reducing errors must be developed. Previous studies suggested that by control of physical...
Self-assembled circuit patterns (2004)
Abstract. Self-assembly is a process in which basic units aggregate under attractive forces to form larger compound structures. Recent theoretical work has shown that pseudo-crystalline self-assembly...
Algorithmic self-assembly of DNA (2003)
How can molecules compute? In his early studies of reversible computation, Bennett imagined an enzymatic Turing Machine which modified a hetero-polymer (such as DNA) to perform computation with...
Protein Design is NP-hard (2002)
Pierce, Niles A., Winfree, Erik
Biologists working in the area of computational protein design have never doubted the seriousness of the algorithmic challenges that face them in attempting in silico sequence selection. It turns out...
Protein design is NP-hard (2002)
Pierce, Niles A., Winfree, Erik
Biologists working in the area of computational protein design have never doubted the seriousness of the algorithmic challenges that face them in attempting in silico sequence selection. It turns out...
Protein Design is NP-hard (2002)
Pierce, Niles A., Winfree, Erik
Biologists working in the area of computational protein design have never doubted the seriousness of the algorithmic challenges that face them in attempting in silico sequence selection. It turns out...
Experimental Progress in Computation by Self-Assembly of DNA Tilings (1999)
Thomas H. Labean, Erik Winfree, John H. Reif
Approaches to DNA-based computing by self-assembly require the use of DNA nanostructures, called tiles, that have efficient chemistries, expressive computational power, and convenient input and...
Experimental Progress in Computation by Self-Assembly of DNA Tilings (1999)
Thomas H. Labean, Erik Winfree, John H. Reif
. Approaches to DNA-based computing by self-assembly require the use of DNA nanostructures, called tiles, that have efficient chemistries, expressive computational power, and convenient input and...
Biomolecular Computing by In Vitro Transcriptional Networks (1998)
Winfree, Erik, Kim, Jongmin, Lee, Shaun, Mohanty, Sarina, Shantz, Kristin
This grant supported the initial development of a novel biochemical system, in vitro transcriptional networks, that can be programmed to construct arbitrary circuits. These systems are a...
Algorithmic self-assembly of DNA (1998)
How can molecules compute? In his early studies of reversible computation, Bennett imagined an enzymatic Turing Machine which modified a hetero-polymer (such as DNA) to perform computation with...
Whiplash PCR for O(1) Computing (1998)
This paper reviews the experimental technique of whiplash PCR, as introduced in Hagiya et al. (in press), and proposes a model of computation based on this technique in combination with assembly PCR...
Simulations of Computing by Self-Assembly. (1998)
Winfree (1996) proposed a Turing-universal model of DNA self-assembly. In this abstract model, DNA double-crossover molecules self-assemble to form an algorithmically-patterned two-dimensional...
iii This thesis reports an unusual and unexpected journey through intellectual territory entirely new to me. Who is prepared for such journeys? I was not. Thus my debt is great to those who have...
Simulations of computing by self-assembly (1998)
Abstract Winfree (1996) proposed a Turing-universal model of DNA self-assembly. In this abstract model, DNA double-crossover molecules self-assemble to form an algorithmically-patterned...
Whiplash PCR for O(1) Computing (1998)
This paper reviews the experimental technique of whiplash PCR, as introduced in Hagiya et al. (in press), and proposes a model of computation based on this technique in combination with assembly PCR...
Whiplash PCR for O(1) computing (1998)
Abstract This paper reviews the experimental technique of whiplash PCR, asintroduced in Hagiya et al. (in press), and proposes a model of computation based on this technique in combination with...
iii This thesis reports an unusual and unexpected journey through intellectual territory entirely new to me. Who is prepared for such journeys? I was not. Thus my debt is great to those who have...
Simulations of computing by self-assembly (1998)
Abstract Winfree (1996) proposed a Turing-universal model of DNA self-assembly. In this abstract model, DNA double-crossover molecules self-assemble to form an algorithmically-patterned...
iii This thesis reports an unusual and unexpected journey through intellectual territory entirely new to me. Who is prepared for such journeys? I was not. Thus my debt is great to those who have...
On Applying Molecular Computation To The Data Encryption Standard (1996)
Leonard M. Adleman, Sam Roweis, Erik Winfree
this paper we consider the so called plaintext-ciphertext attack. Here the cryptanalyst obtains a plaintext and its corresponding ciphertext and wishes todeterminethekey used to perform the...
Universal Computation via Self-assembly of DNA: Some Theory and Experiments (1996)
Erik Winfree, Xiaoping Yang, Nadrian C. Seeman
In this paper we examine the computational capabilities inherent in the hybridization of DNA molecules. First we consider theoretical models, and show that the self-assembly of oligonucleotides into...
A sticker based model for DNA computation (1996)
Sam Roweis, Erik Winfree, Richard Burgoyne, Nickolas V. Chelyapov, Myron F. Goodman, ...
Weintroduce a new model of molecular computation thatwe call the sticker model. Likemany previous proposals it makes use of DNA strands as the physical substrate in which information is represented...
A sticker based model for DNA computation (1996)
Sam Roweis, Erik Winfree, Richard Burgoyne, Nickolas V. Chelyapov, Myron F. Goodman, ...
Weintroduce a new model of molecular computation thatwe call the sticker model. Likemany previous proposals it makes use of DNA strands as the physical substrateinwhichinformation is represented and...
On the Computational Power of DNA Annealing and Ligation (1995)
In [Winfree] it was shown that the DNA primitives of Separate, Merge, and Amplify were not sufficiently powerful to invert functions defined by circuits in linear time. Dan Boneh et al [Boneh] show...
Complexity of Restricted and Unrestricted Models of Molecular Computation (1995)
In [Li1] and [Ad2] a formal model for molecular computing was proposed, which makes focused use of affinity purification. The use of PCR was suggested to expand the range of feasible computations,...
c ○ 2007 Society for Industrial and Applied Mathematics COMPLEXITY OF SELF-ASSEMBLED SHAPES ∗ (1544)
David Soloveichik, Erik Winfree
Abstract. The connection between self-assembly and computation suggests that a shape can be considered the output of a self-assembly “program, ” a set of tiles that fit together to create a...
Paradigms for computational nucleic acid design
Dirks, Robert M., Lin, Milo, Winfree, Erik, Pierce, Niles A.
The design of DNA and RNA sequences is critical for many endeavors, from DNA nanotechnology, to PCR-based applications, to DNA hybridization arrays. Results in the literature rely on a wide variety...
Algorithmic Self-Assembly of DNA Sierpinski Triangles
Rothemund, Paul W. K, Papadakis, Nick, Winfree, Erik
Algorithms and information, fundamental to technological and biological organization, are also an essential aspect of many elementary physical phenomena, such as molecular self-assembly. Here we...
Paradigms for computational nucleic acid design
Dirks, Robert M., Lin, Milo, Winfree, Erik, Pierce, Niles A.
The design of DNA and RNA sequences is critical for many endeavors, from DNA nanotechnology, to PCR-based applications, to DNA hybridization arrays. Results in the literature rely on a wide variety...
Algorithmic Self-Assembly of DNA Sierpinski Triangles
Rothemund, Paul W. K, Papadakis, Nick, Winfree, Erik
Algorithms and information, fundamental to technological and biological organization, are also an essential aspect of many elementary physical phenomena, such as molecular self-assembly. Here we...
Construction of an in vitro bistable circuit from synthetic transcriptional switches
Kim, Jongmin, White, Kristin S, Winfree, Erik
Information processing using biochemical circuits is essential for survival and reproduction of natural organisms. As stripped-down analogs of genetic regulatory networks in cells, we engineered...
Synthesis of crystals with a programmable kinetic barrier to nucleation
Schulman, Rebecca, Winfree, Erik
A central goal of chemistry is to fabricate supramolecular structures of defined function and composition. In biology, control of supramolecular synthesis is often achieved through precise control...
An information-bearing seed for nucleating algorithmic self-assembly
Barish, Robert D., Schulman, Rebecca, Rothemund, Paul W. K., Winfree, Erik
Self-assembly creates natural mineral, chemical, and biological structures of great complexity. Often, the same starting materials have the potential to form an infinite variety of distinct...