CH391L/S13/DNA Computing
Introduction
DNA Computing is the performing of computations using biological molecules, and DNA specifically, instead of traditional silicon. The idea of using molecules in general for computation was first proposed by in 1959 by American physicist Richard Feynman, but it took until 1994 for the first successful experiment using molecules for computation.
History
A computer scientist at the University of Southern California named Leonard Adleman first came up with the idea of using DNA for computing purposes after reading "Molecular Biology of the Gene," a book written by James Watson (co-discoverer of the structure of DNA).
In 1994 Adleman published an article in the journal Science[1] that proposed how DNA could be used to solve a well-known mathematical problem, called the directed Hamilton Path problem, also known as the "traveling salesman" problem. The goal of the problem is to find the shortest path between a number of cities, going through each city only once. This experiment was significant because it showed that information could indeed be processed using the interactions between strands of synthetic DNA.
"He represented each of the seven cities as separate, singlestranded DNA molecules, 20 nucleotides long, and all possible paths between cities as DNA molecules composed of the last ten nucleotides of the departure city and the first ten nucleotides of the arrival city. Mixing the DNA strands with DNA ligase and adenosine triphosphate (ATP) resulted in the generation of all possible random paths through the cities. However, the majority of these paths were not applicable to the situation–they were either too long or too short, or they did not start or finish in the right city. Adleman then filtered out all the paths that neither started nor ended with the correct molecule and those that did not have the correct length and composition. Any remaining DNA molecules represented a solution to the problem."[2]
Challenges
Adleman's experiment is an example of an NP-complete problem (from non-polynomial) for which no known efficient (i.e. polynomial time) algorithm exists. It has been proposed that these types of problems are ideal for the massive parallelism of biology. Whereas traditional computers are designed to perform one calculation very fast, DNA strands can produce billions of potential answers simultaneously.
However, because in most difficult problems the number of possible solutions grows exponentially with the size of the problem, even relatively small problems would require massive amounts of DNA to represent all possible answers. For example, it has been estimated that scaling up the Hamilton Path Problem to 200 cities would require a weight of DNA that exceeds that of the earth. For this reason and others, the field has changed focus to other areas.
DNA-based Logic
The fundamental building blocks of computing are based on logic circuits or "gates", such as AND, OR, NOT. Using Adleman's work, other researchers have been developing DNA-based logic circuits that are useful in a variety of ways, like performing mathematical and logical operations and recognizing patterns. Progress is even being made in in-cell programming, opening up the doors to, for example, advanced cancer treatments.
Strand Displacement
Perhaps the best-known advances in the field are by a group of researchers at Caltech led by Erik Winfree. In strand-displacement, the inputs are free-floating single strands of DNA or RNA, and logic gates are made from two or more strands, with one being the future output signal. If an input strand has a complementary "tab" to a logic gate, it binds and then displaces the output strand, which then detaches. The output strand then becomes an input to another logic gate, in propagation. In a 2011 paper, Winfree together with colleague Lulu Qian used this technique to build a circuit, made of 74 different DNA strands, capable of calculating the square roots of four-digit binary numbers (aka 0 to 15).[3]
DNAzymes
At Columbia University, Milan Stojanovic has built circuits using a sister to strand displacement that is based on deoxyribozymes or DNAzymes, which are synthetically made, single-stranded DNA sequences that cut other DNA strands in specific places. Stojanovic makes logic gates by adding "stem loops" to the DNAzyme, which prevent it from working. When input strands bind to complementary sequences on the loop, the loop breaks, thus allowing the DNAzyme to activate and turning the gate on. It then interacts with other strands in a cascading fashion. Stojanovic used this method to build circuits able to play tic-tac-toe.[4]
Enzymes
Logic can also be created using methods that more closely resemble operation inside of living cells. A group led by Yaakov Benenson at the Swiss Federal Institute of Technology (ETH Zurich) and Ron Weiss of MIT is creating circuits using common enzymes like polymerases, nucleases and exonucleases that operate inside cells, utilizing existing cellular infrastructure. In 2011, the team created a circuit capable of recognizing cervical cancer and then destroying the cell it is found within. It works by looking for five microRNAs specific to cervical cancer; when all five are at the right levels, the circuit activates, producing a protein that causes the cell to self-destruct.[5]
Algorithmic self-assembly
DNA computing has benefitted from the separate and distinct field of DNA nanotechnology. The founder of the field, American biochemist Nadrian Seeman, has worked with Erik Winfree to show how two-dimensional sheets of DNA "tiles" could self assemble into other, larger structures. Winfree and his student Paul Rothemund then demonstrated how these structures could be used for computing purposes in a 2004 paper that describes the self assembly of fractal called a Sierpinski gasket, which won them the 2006 Feynman Prize in Nanotechnology. Winfree's major insight was that the tiles could be used as "Wang tiles", meaning the assembly of the structure was capable of computation.[6]
Storage
DNA can be treated as a highly stable and compact storage medium. In 2012, George Church, a bioengineer and geneticist at Harvard, succeeded in storing 1000 times the largest data size previously achieved using DNA. Church encoded 700 terabytes of information into a single gram of DNA. For comparison, storing the same amount of information using the densest electronic medium would require 330 pounds of hard-drives.
His methodology was synthesizing 96-bit strands, with each base representing a binary value (ex: T and G = 1, A and C = 0). The "data" in question was 70 billion copies of his latest book, "Regenesis: How Synthetic Biology Will Reinvent Nature and Ourselves"
To read the DNA, Church simply sequenced it using next-generation sequencing, converting each of the bases back into binary. Each strand of DNA had a 19-bit address block at the start so the DNA can be sequenced out of order and then sorted into usable data using the addresses.
Breaking News
On March 28, 2013, Drew Endy and his team of researchers at Stanford University published a paper[7] in Science that outlines how to create single-layer, transcriptor-based logic gates utilizing a three-terminal device architecture to control the flow of RNA polymerase along DNA. Endy has open-sourced these transcriptors through the Registry of Standard Biological Parts, and an informational video is available here.
