CSCI 2570 - Introduction to Nanocomputing

Readings for Lecture 05 and 06

These readings are restricted to Brown University.

Molecular computation of solutions to combinatorial problems by L.M. Adleman, Science, vol. 266, p. 5187 (1994).
This is the first paper showing that a combinatorial optimization problem can be solved using DNA hybridization. This was done for the Hamiltonia Path Problem.
DNA solution of hard combinatorial problems by R.J. Lipton, Science, vol. 268, p. 542 (1995).
Adleman's approach has been extended to the solution of Satisfiability.
Universal computation via self-assembly of DNA: some theory and experiments by R. Winfree, S. Yang and N.C. Seeman, DNA Computers II, p. 191 (1998).
The authors show that the linear structures created by the hybridization of linea DNA chains can be described by regular expressions. Assembley of complexes produces structures describable by context-free and recursively enumerable languages. They say that 2D structures are universal computing structures and they discuss the increased computational power provided by 3D structures.
Design and self-assembly of two-dimensional DNA crystals by E. Winfree, F. Liu, L.A. Wenzler and N.C. Seeman, Nature, vol. 394, p. 539 (1998).
From the paper: "Self-assembly is increasingly becoming recognized as a route to nanotechnology."
The program size complexity of self-assembled squares by P.W.K. Rothemund and E. Winfree, Procs. 2000 STOC, p. 459 (2000).
The authors ask how many tiles suffice to generate a 2D pattern of tiles in a tiling system.
Successes and Challenges by J.H. Reif, Science, vol. 296, p. 478 (2002).
Overview of the next paper.
Solution of a 20-variable 3-SAT problem on a DNA computer by R.S. Braich, N. Chelyapov, C. Johnson, P.W.K. Rothemund and L. Adleman, Science, vol. 296, p. 499 (2002).
Report of an experiment in which a 20-variable instance of SAT is solved.
Combinatorial Optimization Problems in Self-Assembly by L. Adleman, Q. Cheng, A. Goel, M.-D. Huang, D. Kempe, P.M. de Espanes and P.W.K. Rothemund, p. 23 (2002).
Two questions are addressed: a) "What is the smallest tile system that produces a given shape." and b) "Which concentration of tiles leads to fastest self assembly?"
Proofreading tile sets: error correction for algorithmic self-assembly by E. Winfree and R. Bekbolatov, DNA9, p. 126 (2003).
The authors introduce a method of adding redundancy to tiles for the purpose of reducing the likelihood of self-assembly errors.
DNA computing by self-assembly by E. Winfree, National Academy of Engineering Bridge, vol. 34, n. 3, p. 31 (2003).
This is a good, short overview paper of DNA computing that gives an honest assessment of the prospects for success in this area.
DNA-templated self-assembly of protein arrays and highly conductive nanowires by H. Yan, S.H. Park, G. Finkelstain, J.H, Reif and T.H. LaBean, Science, vol. 301, p. 1882 (2003).
This paper gives an example of the use of self-assembled protein arrays to produce conductive nanowires.
Self-assembled circuit patterns by M. Cook, P.W.K. Rothemund and E. Winfree, DNA9, v. 2943, p. 91 (2004).
This paper demonstrates that some of the patterns that can be produced by tiling systems can be interpreted as layouts for logic circuits. Although this paper uses a model for DNA self-assembly, it suggests that complex circuits can be produced by DNA templating.
Algorithmic self-assembly of DNA Sierpinski triangles by P.W.K. Rothemund, N. Papadakis and E. Winfree, PLOS Biology, vol. 2, no. 12 (2004).
This paper report on experiments to produce Sierpinski triangles using DNA.
Electronic nanostructures templated on self-assembled DNA scaffolds by S.H. Park, H. Yan, J.H. Reif, T.H. LaBean and G. Finkelstein, Nanotechnology, vol. 15, p. S525 (2004).
This is another paper reporting on experiments to produce electronic nanostructures using self-assembled DNA.
Programmable control of nucleation for algorithm self-assembly by R. Schulman and E. Winfree, DNA10 (2005).
A nucleation error occurs when an assembly grows from a tile other than the designated seed tile. This paper presents a type of tile set (the Zig-Zag tile set) to reduce the likelihood this will happen.