BIOLOGICAL INSPIRATION FOR COMPUTING 295
Given a set of tiles with the appropriate pads, any arbitrary pattern of tiles can be created. Simple,
periodic patterns have been successfully fabricated and formed from a variety of different DNA tiles,^140
and large superstructures involving these systems and containing tens of thousands of tiles have been
observed. However, nonperiodic structures are more generally useful (e.g., for circuit layouts), and
larger tile sets with more complicated association rules are currently being developed for the assembly
of such patterns.
The design of the pads is a critical element of DNA self-assembly. Since the sticky ends are com-
posed of a sequence of bases, the set of different possible sticky ends is very large. However, there are
physical constraints that restrict the sequences chosen; pads and their complements should be suffi-
ciently different from other matched pairs, as to avoid unintended hybridization; they should avoid
palindromes, and so on.^141 Most importantly, the entire set of pads must be designed so as to produce
the desired overall assembly.
The process of DNA self-assembly requires two steps: the first is the creation of the tiles, by mixing
input strands of DNA together; then, the tiles are placed in solution and the temperature is lowered
slowly until the tiles’ pads connect and the overall structure takes form. This process of annealing can
take from several seconds to hours.
Multistrand DNA Nanostructures and Arrays
The creation of three-dimensional objects with multistrand DNA structures has been pursued for many years
by researchers such as Ned Seeman at New York University. Computer scientists such as Erik Winfree at the
California Institute of Technology and John Reif at Duke University have been using the assembly of these
nanostructures to create mosaics and tile arrays on surfaces. The application of computer science concepts to
“program” the self-assembly of materials is the eventual goal. Since single-stranded RNA forms many biolog-
ically functional structures, researchers are also pursuing the use of RNA as well as DNA for these self-
assembling systems.^9(^1) A.C. Pease, D. Solas, E.J. Sullivan, M.T. Cronin, C.P. Holmes, and S.P.A. Fodor, “Light-generated Oligonucleotide Arrays for Rapid DNA
Sequence Analysis,” Proceedings of the National Academy of Sciences 91(11):5022-5026, 1994.
(^2) See http://www.affymetrix.com and http://www.nanogen.com.
(^3) See http://www.caliper.com; and http://www.alcara.com.
(^4) A.G. Frutos, A.E. Condon, L.M. Smith, and R.M. Corn, “Enzymatic Ligation Reactions of DNA ‘Words’ on Surfaces for DNA Computing,”
Journal of the American Chemical Society 120 (40):10277-10282, 1998. Also, Q. Liu, L. Wang. A.G. Frutos, A.E. Condon, R.M. Corn, and
L.M. Smith, “DNA Computing on Surfaces,” Nature 403:175-179, 2000.
(^5) C.A. Mirkin, R.L. Letsinger, R.C. Mucic, and J.J. Storhoff, “A DNA-based Method for Rationally Assembling Nanoparticles into Macro-
scopic Materials,” Nature 382(6592):607-609, 1996; T.A. Taton, C.A. Mirkin, and R.L. Letsinger, “Scanometric DNA Array Detection with
Nanoparticle Probes,” Science 289(5485):1757-1760, 2000.
(^6) F. Zeng and S.C. Zimmerman, “Dendrimers in Supramolecular Chemistry: From Molecular Recognition to Self-Assembly,” Chemical
Review 97(5):1681-1713, 1997; M.S. Shchepinov, K.U. Mir, J.K. Elder, M.D. Frank-Kamenetskii, and E.M. Southern, “Oligonucleotide
Dendrimers: Stable Nano-structures,” Nucleic Acids Research 27(15):3035-3041, 1999.
(^7) A. Maranthe, A.E. Condon, and R.M. Corn, “On Combinatorial Word Design,” DIMACS Series in Discrete Mathematics and Theoretical
Computer Science 54:75-90, 2000.
(^8) C. Mao, T. LaBean, J.H. Reif, and N.C. Seeman, “Logical Computation Using Algorithmic Self-Assembly of DNA Triple Crossover
Molecules,” Nature 407(6803):493-496, 2000.
(^9) E. Winfree, F. Liu, L.A. Wenzler, and N.C. Seeman, “Design and Self-Assembly of Two-Dimensional DNA Crystals,” Nature
394(6693):539-544, 1998.
(^140) C. Mao, “The Emergence of Complexity: Lessons from DNA,” PLoS Biology 2(12):e431, 2004, available at http://www.
plosbiology.org/archive/1545-7885/2/12/pdf/10.1371_journal.pbio.0020431-S.pdf.
(^141) T.H. LaBean, “Introduction to Self-Assembling DNA Nanostructures for Computation and Nanofabrication,” Computa-
tional Biology and Genome Informatics, J.T.L. Wang et al., eds., World Scientific, Singapore, 2003.