form the backbone of the DNA single strand. Since nucleotides may differ only by their bases, a DNA strand can be viewed as simply a word over the four-letter alphabet {A,C,G,T}. A DNA single strand has an orientation, with one end known as the 5′ end, and the other as the 3′ end, based on their chemical properties. By convention, a word over the DNA alphabet represents the corresponding DNA single strand in the 5′ to 3′ orientation, that is, the word GGTTTTT stands for the DNA single strand 5′– GGTTTTT – 3′. A crucial feature of DNA single strands is their Watson-Crick complementarity: A is complementary to T, G is comple-

RNA. While similar to DNA, RNA differs in three main aspects: RNA is usually single-stranded while DNA is usually double-stranded, RNA nucleotides contain the sugar ribose, while DNA nucleotides contain the sugar deoxyribose, and in RNA the nucleotide Uracil, U, substitutes for Thymine, which is present in DNA.

There are many possible DNA bio-operations that one can use for computations, ²¹ such as: cut-and-paste operations achievable by enzymes, synthesizing desired DNA strands up to a certain length, making exponentially many copies of a DNA strand, and reading out the sequence of a DNA strand.

gained several new dimensions. One of the most significant achievements of molecular computing has been its contribution to the massive stream of research in nanosciences, by providing computational insights into a number of fundamental issues. Perhaps the most notable is its contribution to the understanding of self-assembly, which is among the key concepts in nanosciences. ³⁰ Recent experimental research into programmable molecular-scale devices has produced impressive self-assembled DNA nanostructures³⁵ such as cubes, octahedra, Sierpinski triangles, ³² DNA origami, or intricate nanostructures that achieve computation

 

Paul W.K. rothemund, a senior research associate at california institute of technology, has developed a method of creating nanoscale shapes and patterns using dnA. the smiley faces are actually giant dnA complexes called “scaffolded dnA origami.” rothemund notes that while the smiley face shape may appear silly, there is serious science behind it. he hopes to use this dnA origami (and other dnA nanotechnologies) to build smaller, faster computers and devices. For more on his work, visit http://www.dna. caltech.edu/~pwkr/.

 

mentary to C, and two complementary DNA single strands with opposite orientation bind to each other by hydrogen bonds between their individual bases. In so doing, they form a stable DNA double strand resembling a helical ladder, with the backbones at the outside and the bound pairs of bases lying inside. For example, the DNA single strand 5′– AAAAACC – 3′ will bind to the DNA single strand 5′– GGTTTTT – 3′ to form the 7 base-pair-long (7bp) double strand

 

5′ − AAAAACC − 3′ 3′ − TTTTTGG − 5′

 

Another molecule that can be used for computation is ribonucleic acid,

These bio-operations and the Watson-Crick complementary binding have all been used to control DNA computations and DNA robotic operations. While initial experiments solved simple instances of computational problems, more recent experiments tackled successfully sophisticated computational problems, such as a 20-variable instance of the 3-Satisfiability-Problem. The efforts toward building an autonomous molecular computer include implementations of computational state transitions with biomolecules, and a DNA implementation of a finite automaton with potential applications to the design of smart drugs.

More importantly, since 1994, research in molecular computing has

such as binary counting, or bit-wise cumulative XOR. Other experiments include the construction of DNA-based logic circuits, and ribozymes that can be used to perform logical operations and simple computations. In addition, an array of ingenious DNA nanomachines⁸ were built with potential uses to nanofabrication, engineering, and computation: molecular switches that can be driven between two conformations, DNA “tweezers,” DNA “walkers” that can be moved along a track, and autonomous molecular motors.

A significant amount of research in molecular computing has been dedicated to the study of theoretical models of DNA computation and their properties. The model of DNA computing in-