The particular molecular-scale devices that are the topic of this article are known as DNA nanostructures. As will be explained, DNA nanostructures have some unique advantages among nanostructures: they are relatively easy to design, fairly predictable in their geometric structures, and have been experimentally implemented in a growing number of laboratories around the world. They are constructed primarily of synthetic DNA. A key principle in the study of DNA nanostructures is the use of self-assembly processes to actuate the molecular assembly. Since self-assembly operates naturally at the molecular scale, it does not suffer from the limitation in scale reduction that restricts lithography or other more conventional top-down manufacturing techniques.
This article illustrates the way in which computer science techniques and methods influence this emerging field. Some of the key questions one might ask about biomolecular devices include:
- What is the theoretical basis for these devices?
- How will such devices be designed?
- How can we simulate them prior to manufacture?
- How can we optimize their performance?
- How will such devices be manufactured?
- How much do the devices cost?
- How scalable is the device design?
- How will I/O be done?
- How will they be programmed?
- What efficient algorithms can be programmed?
- What will be their applications?
- How can we correct for errors or repair them?
Note that these questions are exactly the sort of questions that computer scientists routinely ask about conventional computing devices. The discipline of computer science has developed a wide variety of techniques to address such basic questions, and we will later point out some that have an important impact on molecular-scale devices.
DNA Nanotechnology and its Use to Assemble Molecular-Scale Devices. In general, nanoscience research is highly interdisciplinary. In particular, DNA self-assembly uses techniques from multiple disciplines, such as biochemistry, physics, chemistry, and material science, as well as computer science and mathematics. While this makes the topic quite intellectually exciting, it also makes it challenging for a typical computer science reader. Having no training in biochemistry, he or she must obtain a coherent understanding of the topic from a short article. For this reason, this article was written with the expectation that the reader is a computer scientist with limited background knowledge of chemistry or biochemistry (see the sidebar “A Brief Introduction to DNA”; in the sidebar “Why Use DNA to Assemble Molecular-Scale Devices?” we provide some reasons why DNA is uniquely suited for this application; the sidebar “Manipulation of DNA” lists some known enzymes used for manipulation of DNA nanostructures).
The area of DNA self-assembled nanostructures and robotics is by no means simply a theoretical topic—many dramatic experimental demonstrations have already been made and a number of these will be discussed. The complexity of these demonstrations has been increasing at an impressive rate (even in comparison to the rate of improvement of silicon-based technologies).
Molecular-scale devices using DNA nanostructures have been engineered to have various capabilities, including: execution of molecular-scale computation; use as scaffolds or templates for the further assembly of other materials (such as scaffolds for various hybrid molecular electronic architectures or perhaps high-efficiency solar cells); robotic movement and molecular transport; exquisitely sensitive molecular detection; amplification of single molecular events; and transduction of molecular sensing to provide drug delivery.
Adleman’s Initial Demonstration of a DNA-based Computation
Adleman’s Experiment. The field of DNA computing began in 1994 with a laboratory experiment described in [1]. The goal of the experiment was to find a Hamiltonian path in a graph, which is a path that visits each node exactly once. To solve this problem, a set of single-stranded DNA (ssDNA) were designed based on the set of edges of the graph. When combined in a test tube and cooled, they self-assembled into double-stranded DNA (dsDNA). Each of these DNA nanostructures was a linear DNA helix that corresponded to a path in the graph. If the graph had a Hamiltonian path, then one of these DNA nanostructures encoded the Hamiltonian path. By conventional biochemical extraction methods, Adleman was able to isolate only DNA nanostructures encoding Hamiltonian paths, and by determining their sequence, the explicit Hamiltonian path. It should be mentioned that this landmark experiment was designed and experimentally demonstrated by Adleman alone, a computer scientist with limited training in biochemistry.
The Non-Scalability of Adleman’s Experiment. While this experiment founded the field of DNA computing, it was not scalable in practice, since the number of different DNA strands needed increased exponentially with the number of nodes of the graph. Although there can be an enormous number of DNA strands in a test tube (1015 or more, depending on solution concentration), the size of the largest graph that could be solved by Adleman’s method was limited to at most a few dozen nodes. This is not surprising, since finding the Hamiltonian path is an NP-complete problem, whose solution is likely to be intractable using conventional computers. Even though DNA computers operate at the molecular scale, they are still equivalent to conventional computers (for example, deterministic Turing machines) in computational power. This experiment provided an important lesson to the DNA computing community (which is now well recognized): to carefully examine scalability issues and to judge any proposed experimental methodology by its scalability.
Autonomous Biomolecular Computation. Shortly following Adleman’s experiment, there was a burst of further experiments in DNA computing, many of which were quite ingenious. However, almost none of these DNA computing methods were autonomous and instead required many tedious laboratory steps to execute. In retrospect, one of the most notable aspects of Adleman’s experiment was that the self-assembly phase of the experiment was completely autonomous—it required no exterior mediation. This autonomous property makes an experimental laboratory demonstration much more feasible as the scale increases. The remainder of this article focuses on autonomous devices for biomolecular computation based on self-assembly.
Self-Assembled DNA Tiles and Lattices
Computation By Self-Assembly. The most basic way that computer science ideas have influenced DNA nanostructure design is via the pioneering work by theoretical computer scientists on a formal model of 2D tiling due to Wang in 1961, which culminated in a proof by Berger in 1966 that universal computation could be done via tiling assemblies. Winfree was the first to propose applying the concepts of computational tiling assemblies to DNA molecular constructs. His core idea was to use tiles composed of DNA to perform computations during their self-assembly process. To better understand this idea, see the sidebar “DNA Nanostructures.”
DNA Tiles and Lattices. A DNA tile is a DNA nanostructure that has a number of sticky ends on its sides, which are termed pads. A DNA lattice is a DNA nanostructure composed of a group of DNA tiles that are assembled together via hybridization of their pads. Generally, the strands composing the DNA tiles are designed to have a melting temperature above those of the pads, ensuring that when the component DNA molecules are combined together in solution, first the DNA tiles assemble, and only then, as the solution is further cooled, do the tiles bind together via hybridization of their pads.
To program a tiling assembly, the pads of tiles are designed so the tiles assemble together as intended. Proper designs ensure that only the adjacent pads of neighboring tiles are complementary, so only those pads hybridize together (see the sidebar “DNA Tiles”). For a recent review of DNA technology, see [2].
Autonomous Finite State Computation Using Linear DNA Nanostructures
The first experimental demonstrations of computation using DNA tile assembly was [3]. It demonstrated a two-layer, linear assembly of TX tiles that executed a bit-wise cumulative XOR computation. In this computation, n bits are input and n bits are output, where the ith output is the XOR of the first i input bits. This is the computation occurring when one determines the output bits of a full-carry binary adder circuit. The experiment [3] is described further in the sidebar “Sequential Boolean Computation via a Linear DNA Tiling Assembly.” This experiment [3] provided answers to some of the most basic questions that are most likely to be of interest and concern to a computer scientist:
How can one provide data input to a molecular computation using DNA tiles? In this experiment the input sequence of n bits was defined as an “input” ssDNA strand with the input bits (1s and 0s) encoded by distinct short subsequences. Two different tile types (depending on whether the input bit was 0 or 1, these had specific stick-ends and specific subsequences at which restriction enzymes can cut the DNA backbone) were available to assemble around each of the short subsequences comprising the input strand, forming the blue input layer illustrated in the sidebar “Sequential Boolean Computation via a Linear DNA Tiling Assembly.”
How can one execute a step of computation using DNA tiles? To execute steps of computation, the TX tiles were designed to have pads at one end that encoded the cumulative XOR value. Also, since the reporter strand segments ran though each such tile, the appropriate input bit was also provided within its structure. These two values implied the opposing pad on the other side of the tile to be the XOR of these two bits.
How can one determine and/or display the output values of a DNA tiling computation? The output in this case was read by determining which of two possible cut sites (endonuclease cleavage sites) were present at each position in the tile assembly. This was executed by first isolating the reporter strand, then digesting separate aliquots with each endonuclease separately and the two together. Finally these samples were examined by gel electrophoresis, and the output values were displayed as banding patterns on the gel.
Another method for output is the use of atomic force microscopy (AFM) observable patterning. The patterning was made by designing the tiles computing a bit 1 to have a stem loop protruding from the top of the tile. The sequence of this molecular patterning was clearly viewable under appropriate AFM imaging conditions.
Although only very simple computations, the experiments of [3] and [10] demonstrated for the first time methods for autonomous execution of a sequence of finite-state operations via algorithmic self-assembly, as well as for providing inputs and for outputting the results.
Autonomous Finite-State Computations via Disassembly of DNA Nanostructures. An alternative method for autonomous execution of a sequence of finite-state transitions was subsequently developed by [8]. Their technique essentially operated in the reverse of the assembly methods described previously and instead was based on disassembly. They began with a linear DNA nanostructure whose sequence encoded the inputs and then executed a series of steps that digested the DNA nanostructure from one end. On each step, a sticky end at one end of the nanostructure encoded the current state, and the finite transition was determined by hybridization of the current sticky end with a small “rule” nanostructure encoding the finite-state transition rule. Then a restriction enzyme, which recognized the sequence encoding the current input, as well as the current state, cut the appended end of the linear DNA nanostructure to expose a new a sticky end encoding the next state.
Conclusion
Other significant topics, not addressed in this article include:
- Assembling patterned and addressable 2D DNA lattices, such as attaching materials to DNA [11], and methods for programmable assembly of patterned 2D DNA lattices [5, 6, 9].
- Autonomous molecular transport devices self-assembled from DNA [3, 12].
- Future challenges for self-assembled DNA nanostructures, such as error correction and self-repair at the molecular scale [4], and 3D DNA lattices.
In attempting to understand these modern developments, it is worth recalling that mechanical methods for computation date back to the very onset of computer science, for example, to the cog-based mechanical computing machine of Babbage. Lovelace stated in 1843 that Babbage’s “Analytical Engine weaves algebraic patterns just as the Jacquard-loom weaves flowers and leaves.” In some of the recently demonstrated methods for biomolecular computation, computational patterns were essentially woven into molecular fabric (DNA lattices) via carefully controlled and designed self-assembly processes [6, 9]. We have observed that many of these self-assembly processes are computational-based and programmable, and it seems likely that computer science techniques will be essential to the further development of this emerging field of biomolecular computation.
Figure. Structure of a DNA double helix (created by Michael Ströck and released under the GNU Free Documentation License).
Figure. A stem-loop and a sticky end.
Figure. A Holliday junction (created by Miguel Ortiz-Lombardía, CNIO, Madrid, Spain).
Figure. Sequential Boolean computation via a linear DNA tiling assembly (adapted with permission from [3]).
Join the Discussion (0)
Become a Member or Sign In to Post a Comment