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) 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 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. (STOC 2000) 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, 416 KB) 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 , 6 pages. ( 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 "one-pot" PCR-like 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. (stickers.ps.gz, 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