DNA Computing Overview

| People | Research Areas | Publications | Calculation Programs | Home |


DNA Computing Overview

I. Summary

This research project is aimed at the development and characterization of complex mixtures of DNA molecules attached to surfaces. The attachment chemistry, hybridization chemistry and enzymatic activity of the adsorbed DNA molecules will be characterized by a variety of spectroscopic and biochemical methods, and subsequently optimized for use in (i) the manipulation of DNA sequences in molecular computing strategies and (ii) the high density storage and retrieval of information by DNA hybridization chemistry.

II. Background

The manipulation of complex DNA solutions with genetic engineering tools has been proposed recently as a chemical methodology for solving instances of computationally intractable (so- called NP-complete) combinatorial problems. In this methodology, every possible solution to a particular mathematical problem is represented by a specific DNA strand. Using combinatorial chemistry methods, it is relatively easy to generate a "solution space" of, say, 10^10 different DNA molecules in a single test tube. Each of these DNA molecules is capable of hybridizing (i.e., forming a hydrogen-bonded duplex structure) with a unique complementary DNA strand. DNA molecules which are hybridized ("double-stranded DNA") can be distinguished from molecules which are not hybridized ("single-stranded DNA") by various enzymatic reactions. It is therefore possible to identify the presence of a particular "solution" (i.e., DNA molecule) to a mathematical problem by hybridization chemistry. The DNA computation strategy requires a series of hybridization operations in order to select the subset of the DNA molecules that are appropriate solutions to a particular mathematical problem. In the original papers, the chemical manipulations are envisioned to be carried out in test tubes and the appropriate DNA molecules are removed from solution by hybridization to complementary DNA strands affixed to magnetic beads. The number of different types of beads required for a particular mathematical problem scales as the number of operations in the algorithm, and can reach into the thousands. The goal of this project is to design high density, chemically complex surfaces that can replace the test tube/magnetic bead methodology and simplify the task of performing the thousands of successive separations by hybridization that will be required in any DNA computing scheme. Achieving this goal will require a fundamental understanding of the chemical nature of binding interactions between DNA molecules and surfaces.

III. Project Design and Goals

Our strategy will be to the create a surface onto which all of the DNA molecules that represent possible solutions to a mathematical problem are bound. The DNA must be attached to the surface in a high density fashion, yet each DNA strand must remain accessible to hybridization from solution and to enzymatic reactions. Initially, planar surfaces coated with well-defined self-assembled monolayers will be used to control the attachment chemistry and DNA surface coverage. Operations on the surface "solution space" will be performed by exposure of the surface to various chemical solutions, and the unwanted DNA strands will be removed. This approach will greatly reduce the possibility of losing DNA molecules during solution transfer operations, and simplifies the procedure of identifying all the remaining DNA molecules after the series of operations are complete. Our overall goal will be to demonstrate that these complex mixtures of DNA molecules attached to surfaces can be used to solve mathematical problems and are also capable of storing large amounts of information.

The following is a list of specific goals for the project that are required to accomplish our overall strategy of creating chemically complex surfaces for use in DNA computing schemes:

1. Solution Space Representations on Surfaces: Surface Attachment Chemistry

The first step in this project will be to create surfaces with a large number of different DNA molecules. The molecules can be created by combinatorial chemistry methods in solution, and then adsorbed to the surface by an appropriate attachment chemistry. Various types of self- assembled monolayers on gold (attached via a thiolate linkage) or silica or silicon (attached via a silane linkage) can be used to control the adsorption of modified DNA molecules to the surface. The characterization of these surfaces will be accomplished by a combination of biochemical assays, spectroscopic measurements and scanning probe microscopies. The molecules need not be organized on the surface in an addressable fashion, but need to be as densely packed as possible while still allowing access from solution. We will determine how to adsorb the DNA molecules onto the surface while still maintaining their biochemical activity, and how many copies of a particular DNA strand are required to insure that it will be consistently recognized in all subsequent chemical reactions.

2. Implementation of Operations on Surfaces: DNA Surface Hybridization Chemistry and Enzymatic Activity

The next step will be to demonstrate that a subset of the molecules on the surface can be addressed via hybridization from solution and removed by an enzymatic reaction. This chemical process is how we will implement mathematical operations on the surface-bound DNA molecules. The first question that needs to be addressed is how adsorption to a surface effects the DNA hybridization chemistry and the ability of enzymes (e.g., exonucleases) to identify and react with the adsorbed molecules. These surface effects need to be minimized by including spacer DNA strands or by modifying the surface chemistry in order to insure that the attached DNA molecules remain accessible from solution. Since we wish to perform many operations on the DNA strands, the accuracy and specificity of this chemistry needs to be determined precisely (e.g., by the adsorption of a variety of test DNA strands) in order to ascertain the amount of errors that will be present in a given DNA calculation.

3. Solution of a Simple Mathematical Problem: DNA Sequence Selection, Algorithm Development and Solution Identification

Once we have learned how to make surfaces that contain a complete and active set of DNA molecules for a given solution space and have learned how to manipulate this surface population through hybridization and enzymatic reactions, we will attempt to solve a simple mathematical problem to demonstrate the feasibility of this surface manipulation methodology. One simple problem that should be achievable by DNA manipulations on surfaces is a 3-SAT; we expect to be able to eventually handle much more complex mathematical systems. Solution of this problem requires three steps: (i) selection of the appropriate DNA molecules to represent solution space on the surface, (ii) translation of the mathematical operations into a hybridization operation algorithm that can be applied to the surface to remove all DNA molecules that are not valid solutions, and (iii) identification (by either direct sequencing or cloning) of the remaining DNA molecules on the surface that represent valid solutions to the mathematical problem. We plan to first demonstrate the viability of this surface-based methodology on 5-variable 3-SAT problems (which have a solution space of 2^5 = 32 DNA molecules) and then build up to more complex surfaces (e.g., 10 variables = 1024 DNA molecules, 20 variables = 10^6, 30 variables = 10^9, etc.).

4. The Next Step: Ligation Approaches on Surfaces

In addition to DNA hybridization chemistry followed by enzymatic removal from the surface, we will also determine how to implement genetic engineering techniques for the marking of particular DNA strands by adding an additional DNA sequence segment (ligation). The ligation of additional bases onto particular DNA strands adds an additional level of complexity to the DNA populations on the surfaces; this additional complexity will permit us to design new DNA hybridization algorithms that are appropriate for more difficult mathematical problems (e.g., circuit SAT and graph-theoretic problems).

5. Other Applications: Solution Space Surfaces as Information Storage Devices

The creation of complex DNA mixtures on surfaces will initially be employed as a means of creating a large "solution space" for DNA computing strategies. However, these same surfaces can also be employed as a means of information storage. For example, large data sets of information can be classified and stored on the complex DNA surfaces with various additional DNA segments as tags. Searches through this large database could in principle be accomplished by the same hybridization identification, removal and ligation operations that will be used in the DNA computing studies. Thus, in addition to the DNA computing experiments, we will design complex DNA surfaces specifically for use in information storage and retrieval, and then experimentally determine the reliability and stability of these surfaces.


Return to the DNA computing page