Erik's Molecular Computation
page: Erik's research articles
Good stuff, eh? (reverse chronological order)
THIS IS OLD AND OUTDATED. PLEASE SEE OUR NEW PAGE!!!
- Protein Design is NP-Hard, 4 pages. (Protein Engineering, v15,
pp. 779-782, 2002). 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.
(PRODES.pdf, 1.1 MB).
- Algorithmic Self-Assembly of DNA: Theoretical Motivations and
2D Assembly Experiments, 8 pages.
(Journal of Biomolecular Structure and Dynamics)
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 color.
(algSA_JBSD.pdf, 746 KB),
(algSA_JBSD.ps.gz, 3.3 MB).
- String Tile Models for DNA Computing by Self-Assembly, 26 pages.
(DNA Based Computers 6)
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 color.
(stringtiles.pdf, 679 KB),
(stringtiles.ps, 1.6 MB),
(early draft, 225 KB).
- The Program-Size Complexity of Self-Assembled Squares, 10 pages.
Paul W. K. Rothemund, 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.
(squares_STOC.ps.gz, 114 KB),
(squares_STOC.ps, 761 KB).
- Construction, analysis, ligation, and self-assembly of
DNA triple crossover complexes , 13 pages.
Journal of the American Chemical Society, 122(9): 1848-1860 (March 2000))
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.
(triplex.ps.gz, 906 KB),
(triplex.pdf, 712 KB).
- Experimental Progress in Computation by Self-Assembly
of DNA Tilings, 18 pages.
(LaBeanTX.pdf, 490 KB),
(LaBeanTX.ps.gz, 600 KB),
(LaBeanTX.ps, 2.3 MB)
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 DIMACS #5)
- Error Correction in DNA Computing:
Misclassification and Strand Loss,
16 pages. (kevin.ps.gz,
100 KB), (kevin.ps,
Kevin Chen, 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 DIMACS #5)
- Design and self-assembly of two-dimensional DNA crystals ,
Nature 394, 539-544 (Aug. 6, 1998) Article)
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. NOTE: There is a typographical error in the
Methods sections specifying TAE/Mg++. We use the standard (e.g. Sambrook/Maniatis) TAE
buffer supplemented to 12.5 mM Mg++ with magnesium acetate. NOTE: There is a more unfortunate error in Figure 1. Each DAO repeat is 37 (not 36) nucleotides; that is, 16nt core, two 8nt arms, and one 5nt sticky end.
(lattice.ps.gz, 710 KB),
(lattice.ps, 1.1 MB).
- On the Reduction of Errors in DNA Computation ,
Sam Roweis and Erik Winfree,
Journal of Computational Biology, 6(1): 65--75, 1999.
(Journal version of errors analysis in "Stickers", DNA II, below.)
- On Applying Molecular Computation to the Data Encryption Standard ,
Leonard M. Adleman, Paul W. K. Rothemund, Sam Roweis, Erik Winfree,
Journal of Computational Biology, 6(1): 53--63, 1999.
(Journal version of DNA II paper, below.)
- 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--629, 1998.
(Journal version of DNA II stickers paper, below, sans errors analysis.)
Erik's PhD Thesis: Algorithmic Self-Assembly of DNA, 110 pages, 6/98.
(thesis.pdf, 5 MB),
(thesis.ps.gz, 5 MB),
(thesis.ps, 21 MB).
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.
- Simulations of Computing by Self-Assembly,
25 pages. (simulation.ps.gz,
392 KB), (simulation.ps,
3.1 MB), Erik Winfree, 5/98. 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".
(in DIMACS #4)
- Whiplash PCR for O(1) Computing,
14 pages. (whiplash.ps.gz,
136 KB), (whiplash.ps,
666 KB), Erik Winfree, 5/98. Some comments and extensions to the
technique of [Hagiya,Arita,Kiga,Sakamoto,Yokoyama in DIMACS #3], including a
a way for a single DNA strand to simulate the execution of circuit.
(in DIMACS #4)
- Universal Computation via Self-assembly of DNA: Some Theory and
Experiments, 22 pages. (self-assem.ps.gz, 546 KB), (self-assem.ps, 2.6 MB), Erik Winfree,
Xiaoping Yang, Nadrian C. Seeman, 8/7/96. 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. [Note, there are a few typographical errors in important definitions. EW,
6/98] (in DIMACS #2, pgs 191--213)
- A Sticker Based Architecture for DNA Computation, 26 pages.
231 KB), (stickers.ps,
1.2 MB), Sam Roweis, Erik Winfree, Richard Burgoyne, Nickolas V. Chelyapov,
Myron F. Goodman, Paul W.K. Rothemund, Leonard M. Adleman, 7/96. A new
representation for encoding bits in DNA is presented and examined, and
generally applicable methods for decreasing separation error rates are
discussed. (in DIMACS #2, pgs 1--29)
- On Applying Molecular Computation To The Data Encryption Standard,
21 pages. (des.ps.gz,
77 KB), (des.ps,
211 KB), Leonard M. Adleman, Paul W.K. Rothemund, Sam Roweis, Erik
Winfree, 8/96. An algorithm for breaking DES is designed for the Stickers
model. Size, space, and error rates of the resulting machine are considered.
(in DIMACS #2, pgs 31--44)
- On the Computational Power of DNA Annealing and Ligation, 13
pages. (ligation.ps.gz, 157 KB), (ligation.ps,
951KB), Erik Winfree, 5/25/95. 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".
[Note, there are strand polarity errors
in several figures. EW, 5/96] (in DIMACS #1, pgs 199--221)
- Complexity of Restricted and Unrestricted Models of Molecular Computation,
8 pages. (models.ps.gz, 72KB), (models.ps,
195KB), Erik Winfree, 5/1/95. 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 DIMACS #1, pgs 187--198)
DIMACS #1 is: DNA Based Computers: DIMACS Workshop,
April 4, 1995 (eds Richard J. Lipton and Eric
B. Baum) American Mathematical Society, 1996.
DIMACS #2 is: DNA Based Computers II: DIMACS Workshop,
June 10-12, 1996 (eds Laura F. Landweber and Eric B. Baum)
American Mathematical Society, 1998.
DIMACS #3 is: DNA Based Computers III: DIMACS Woskhop,
June 23-25, 1997 (eds Harvey Rubin and David H. Wood)
American Mathematical Society, 1999.
DIMACS #4 is: Proceedings of the Fourth DIMACS Meeting on DNA Based
Computers, held at the University of Pennsylvania, June 16-19, 1998.
DIMACS #5 is: DNA Based Computers V: DIMACS Workshop, June
14-15, 1999. (eds. Erik Winfree and David K. Gifford)
American Mathematical Society, to appear.
Send comments to