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, 21 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. 30 Recent experimental research
into programmable molecular-scale
devices has produced impressive self-assembled DNA nanostructures35 such
as cubes, octahedra, Sierpinski triangles, 32 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 nanomachines8 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-