DNA Computing

Table of Contents

The field of DNA Computing was initially developed by Leonard Adleman of the University of Southern California. In 1994, Adleman demonstrated a proof-of-concept use of DNA as form of computation which was used to solve the seven-point Hamiltonian path problem. Since the initial Adleman experiments, advances have been made, and various Turing machines have been proven to be constructable.

Some of the striking features of DNA Computing

You won’t believe where scientists have found the new material they need to build the next generation of microprocessors. Millions of natural supercomputers exist inside living organisms, including your body. DNA (deoxyribonucleic acid) molecules, the material our genes are made of, have the potential to perform calculations many times faster than the world’s most powerful human-built computers. DNA might one day be integrated into a computer chip to create a so-called biochip that will push computers even faster. DNA molecules have already been harnessed to perform complex mathematical problems.
While still in their infancy, DNA computers will be capable of storing billions of times more data than your personal computer. In this article, you’ll learn how scientists are using genetic material to create nano-computers that might take the place of silicon-based computers in the next decade.
DNA computing is a form of computing which uses DNA and molecular biology, instead of the traditional silicon-based computer technologies. A single gram of DNA with volume of 1 cm³ can hold as much information as a trillion compact discs, approximately 750 terabytes. There are works over one dimensional lengths, bidimensional tiles, and even three dimensional DNA graphs processing.

Characteristics of DNA

Three billion years of evolution have left us with an untapped legacy, a tool-chest for the 21st century: the cell. The cell is full of wondrous molecules. Molecules that store information, molecules that store energy, molecules that act like motors, molecules that act like structural material, molecules that cut and molecules that paste… There are thousands of these molecules in the cell. Each is incredibly small (a few nano-meters in each dimension), each is extraordinarily precise and ultra-specific, each functions with an energy efficiency that is on the cusp of what is thermodynamically feasible. Thanks to the recent efforts of molecular biologists, these tools are being taken from the cell and made commercially available at an extraordinarily low price. Take DNA. It is a wonderful way to store information – it has been storing the “blueprint for life” for several billion years. One gram of DNA, which would occupy about 1 cubic centimeter when dry, can hold as much information as approximately one trillion CDs. One can write down a sequence of A, T, C and Gs, email it to a DNA synthesizer and receive the next day a tube containing about 10¹⁷molecules each with the requested sequence. For a sequence of length 20, the cost is about $30 – that’s about 30 femptocents (a femptocent is 1 one-thousand-trillionth of a cent) per molecule. Another example is polymerase. This is a protein that acts like a juggler on a tightrope. It ‘hops’ onto a strand of DNA, ‘walks’ down it and ‘reads’ its sequence; all the while, it is ‘reaching’ into the surrounding solution, ‘grabbing’ new A, T, C and Gs and sticking

them together to form a new strand of DNA that is Watson-Crick complementary to the strand it started with.

The data density of DNA is impressive. Just like a string of binary data is encoded with ones and zeros, a strand of DNA is encoded with four bases, represented by the letters A, T, C, and G. The bases (also known as nucleotides) are spaced every 0.35 nanometers along the DNA molecule, giving DNA a remarkable data density of nearly 18 Mbits per inch. In two dimensions, if you assume one base per square nanometer, the data density is over one million Gbits per square inch.

Compare this to the data density of a typical high performance hard drive, which is about 7 Gbits per square inch — a factor of over 10 0,000 smaller.

Operations in DNA

In the cell, DNA is modified biochemically by a variety of enzymes, which are tiny protein machines that read and process DNA according to nature’s design. There is a wide variety and number of these “operational” proteins, which manipulate DNA on the molecular level. For example, there are enzymes that cut DNA and enzymes that paste it back together. Other enzymes function as copiers and others as repair units. Molecular biology, Biochemistry, and Biotechnology have developed techniques that allow us to perform many of these cellular functions in the test tube. It’s this cellular machinery, along with some synthetic chemistry, that makes up the palette of operations available for computation. Just like a CPU has a basic suite of operations like addition, bit-shifting, logical operators (AND, OR, NOT NOR), etc. that allow it to perform even the most complex calculations, DNA has cutting, copying, pasting, repairing, and many others. And note that in the test tube, enzymes do not function sequentially, working on one DNA at a time. Rather, many copies of the enzyme can work on many DNA molecules simultaneously. This is the power of DNA computing, that it can work in a massively parallel fashion.

Comparison between conventional computer and DNA computer

A conventional computer represents information on silicon chips as a series of electrical impulses zeroes and ones and manipulates the information by performing mathematical computations with those zeroes and ones.
By contrast, a DNA computer represents information as a pattern of molecules in a strand of synthetic DNA. That information is manipulated by subjecting it to precisely designed chemical reactions that may mark the strand, lengthen it, or eve
Researchers think computers made from DNA would be well suited to tackle problems that are time-consuming for conventional computers. Sequences of DNA can be crafted to represent specific patterns of information, and chemical reactions manipulate the DNA — much as mathematical computations operate on information stored in today’s computers.
Unlike conventional computers, DNA computers perform calculations parallel to other calculations. Conventional computers operate linearly, taking on tasks one at a time. It is parallel computing that allows DNA to solve complex mathematical problems in hours, whereas it might take electrical computers hundreds of years to complete them.

Working of DNA computing

The gold-coated square of glass doesn’t look like a memory chip-or like any other computer component, for that matter.

But the glass, less than an inch square, is one key to building a radically different kind of computer, one that uses DNA instead of silicon to store and manipulate information. Eventually, proponents say, the technology could produce DNA-based computers that would be better even than supercomputers in solving certain types of problems.

Most of the possible answers are incorrect, but one or a few may be correct, and the computer’s task is to check each of them and winnow out the incorrect ones. The DNA computer does that by subjecting all of the strands simultaneously to a series of chemical reactions that mimic the mathematical computations an electronic computer would

By orchestrating many such operations, researchers can use the enzymes to perform sophisticated logical and mathematical computations perform on each possible answer.

When the chemical reactions are complete, researchers analyze the strands to find the answer — for instance, by locating the longest or the shortest strand and decoding it to determine what answer it represents.

The advantage of the DNA approach is that it works in “parallel,” processing all possible answers simultaneously. An electronic computer can analyze only one potential answer at a time. Problems that have many possible answers can take a long time to solve, even for supercomputers that contain hundreds of electronic processors operating in parallel.

When a message is encrypted according to the standard, the coding relies on one of 72 quadrillion “keys,” or encoding instructions. A message coded in this way is hard to crack, because there is no way to know which specific key was used. Testing all possible keys on an electronic computer would take an enormous But a DNA computer could test all of the keys at the same time, find the right

one, and pass it to a human code-breaker for use in translating the message. A highly automated version of a DNA computer might be able to produce the answer in as little as two hour’s amount of time.

A short length of DNA represented an arrangement with many connections, while a long strand represented an arrangement with few connections.

To find out precisely which points were connected in that strand, the researchers used a virus to infect an Escherichia coli bacterium with the strand of DNA. The bacterium manufactured multiple copies of the strand. After about a day, the researchers were able to extract enough of the genetic material to read its code, representing the correct answer — in this case, connections among points 2, 3, 4, and 5.

The DNA computer took about a day to produce that answer, which a conventional computer would have yielded in the blink of an eye. But for larger versions of the problem — perhaps 50 cities or more — the DNA computer probably would be faster than a conventional computer, particularly if there are further advances in processes for synthesizing and decoding DNA quickly,

The Wisconsin researchers, using DNA that is anchored to a surface, have been trying to compute the answer to what’s known in computer-science circles as the “satisfiability” problem. It seeks a sequence of zeroes and ones to use in a predetermined formula so that the formula produces the value 1. An ordinary computer would have to try each possible sequence of zeroes and ones in the formula until it found a sequence that resulted in the desired answer.

But the Wisconsin researchers represent each possible sequence of zeroes and ones as a separate strand of DNA attached to the gold-covered glass plate. They are developing a series of chemical reactions, representing the mathematical formula that would mark all of the strands that do not satisfy the formula. After the reactions are completed, the marked strands would be cut away with enzymes. The remaining strands, if any, would represent numerical values that satisfy the formula.

He believes that the DNA computing, which he prefers to call “biomolecular computation,” may have its biggest impact in completely different ways — for example, enabling a computing system to read and decode natural DNA directly. Such a computer also might be able to perform DNA “fingerprinting” — matching a sample of DNA, such as that in blood found at a crime scene, with the person from whom it came.

“That,” Dr. Reif says, “could be the killer application for biomolecular computation.”

Measurements of electrical conductivity of DNA

A team of Dutch researchers has made the first direct measurements of the electrical conductivity of an individual strand of DNA – the building block of life. Cees Dekker from Delft University of Technology and colleagues designed two metal electrodes spaced just 4 nanometers apart – the smallest distance ever achieved by lithography. They then used a new ‘electrostatic trapping’ technique to bridge the electrodes with a single DNA molecule. The group discovered that short DNA molecules behave like large-bandgap semiconductors (Nature 403 635).

The Delft group fabricated the electrodes by making a slit in a silicon nitride film with standard lithography. A series of platinum layers were then sputtered across the slit until the gap was reduced to 4 nanometers. The electrodes were then immersed in a droplet of dilute DNA solution. A voltage applied between the electrodes generated an intense electric field, attracting a single molecule strand between the electrodes. Once the molecule was in place, the group could investigate how electrons are transferred in DNA.

“The results show that the charge carriers are being mediated by the molecular bands of DNA,” says Dekker, “but more research is needed to explore DNA’s electrical properties under a large variety of conditions.”

A Successor to Silicon

Silicon microprocessors have been the heart of the computing world for more than 40 years. In that time, manufacturers have crammed

more and more electronic devices onto their microprocessors. In accordance with Moore’s Law, the number of electronic devices put on a microprocessor has doubled every 18 months. Moore’s Law is named after Intel founder Gordon Moore, who predicted in 1965 that microprocessors would double in complexity every two years. Many have predicted that Moore’s Law will soon reach its end, because of the physical speed and miniaturization limitations of silicon microprocessors.

DNA computers have the potential to take computing to new levels, picking up where Moore’s Law leaves off. There are several advantages to using DNA instead of silicon:

As long as there are cellular organisms, there will always be a supply of DNA.

The large supply of DNA makes it a cheap resource.
Unlike the toxic materials used to make traditional microprocessors, DNA biochips can be made cleanly.
DNA computers are many times smaller than today’s computers.

DNA’s key advantage is that it will make computers smaller than any computer that has come before them, while at the same time holding more data. One pound of DNA has the capacity to store more information than all the electronic computers ever built; and the computing power of a teardrop-sized DNA computer, using the DNA logic gates, will be more powerful than the world’s most powerful supercomputer. More than 10 trillion DNA molecules can fit into an area no larger than 1 cubic centimeter (0.06 cubic inches). With this small amount of DNA, a computer would be able to hold 10 terabytes of data, and perform 10 trillion calculations at a time. By adding more DNA, more calculations could be performed.

Experiment regarding measurements of conductivity of DNA

Last year Hans-Werner Fink and Christian Schönenberger from the University of Basel, Switzerland made the first measurements of the conductivity of a ‘rope’ of DNA molecules. They made their measurements by placing discrete amounts of DNA molecules in a water-based solution. A tiny droplet of the solution was then placed onto a gold-coated carbon foil. Blotting paper was then used to remove most of the water on the device, causing some of the individual DNA molecules to span the holes in the foil. According to their calculations, these strands coalesce into a DNA ‘rope’ 2 microns in diameter. By using a low-energy coherent electron beam from a LEEP microscope, Fink and Schönenberger were able to visualize the DNA strands without damaging the molecules. Next they used a mechanical tip to break one end of the DNA rope away from the foil. The tip was then used to create a small measurable voltage between this end of the rope and the foil.

They suggested that the molecules were ohmic conductors with fairly high conductivity.

Improvements in DNA computer by Adleman and his colleagues

Scientists have previously used DNA computers to crack computational problems with up to nine variables, which involve selecting the correct answer from 512 possible solutions. But now Adleman’s team has shown that a similar technique can solve a problem with 20 variables, which has 2²⁰ or 1048576 possible solutions.

Adleman and colleagues chose an ‘exponential time’ problem, in which each extra variable doubles the amount of computation needed. This is known as an NP-complete problem, and is notoriously difficult to solve for a large number of variables. Other NP-complete problems include the ‘traveling salesman’ problem – in which a salesman has to find the shortest route between a numbers of cities and the calculation of interactions between many atoms or molecules.

Adleman and co-workers expressed their problem as a string of 24 ‘clauses’, each of which specified a certain combination of ‘true’ and ‘false’ for three of the 20 variables. The team then assigned two short strands of specially encoded DNA to all 20 variables, representing ‘true’ and ‘false’ for each one.

In the experiment, a gel-filled glass cell represents each of the 24 clauses. The strands of DNA corresponding to the variables and their ‘true’ or ‘false’ state – in each clause were then placed in the cells.

Each of the possible 1 048 576 solutions were then represented by much longer strands of specially encoded DNA, which Adleman’s team added to the first cell. If a long strand had a ‘subsequence’ that complemented all three short strands, it bound to them. But otherwise it passed through the cell.

To move on to the second clause of the formula, a fresh set of long strands was sent into the second cell, which trapped any long strand with a ‘subsequence’ complementary to all three of its short strands. This process was repeated until a complete set of long strands had been added to all 24 cells, corresponding to the 24 clauses. The long strands captured in the cells were collected at the end of the experiment, and these represented the solution to the problem.

According to Adleman and co-workers, their demonstration represents a watershed in DNA computation comparable with the first time that electronic computers solved a complex problem in the 1960s. They are optimistic that such ‘molecular computing’ could ultimately allow scientists to control biological and chemical systems in the way that electronic computers control mechanical and electrical systems now.

The success of the Adleman DNA computer proves that DNA can be used to calculate complex mathematical problems. However, this early DNA computer is far from challenging silicon-based computers in terms of speed. The Adleman DNA computer created a group of possible answers very quickly, but it took days for Adleman to narrow down the possibilities. Another drawback of his DNA computer is that it requires human assistance.

Introducing Logical-Gates into DNA computing

Three years after Adleman’s experiment, researchers at the University of Rochester developed logic gates made of DNA. Logic gates are a vital part of how your computer carries out functions that you command it to do. These gates convert binary code moving through the computer into a series of signals that the computer uses to perform operations. Currently, logic gates interpret input signals from silicon transistors, and convert those signals into an output signal that allows the computer to perform complex functions.

The Rochester team’s DNA logic gates are the first step toward creating a computer that has a structure similar to that of an electronic PC. Instead of using electrical signals to perform logical operations, these DNA logic gates rely on DNA code. They detect fragments of genetic material as input, splice together these fragments and form a single output. For instance, a genetic gate called the “And gate” links two DNA inputs by chemically binding them so they’re locked in an end-to-end structure, similar to the way two Legos might be fastened by a third Lego between them. The researchers believe that these logic gates might be combined with DNA microchips to create a breakthrough in DNA computing.

DNA computer components — logic gates and biochips — will take years to develop into a practical, workable DNA computer. If such a computer is ever built, scientists say that it will be more compact, accurate and efficient than conventional computers. In the next section, we’ll look at how DNA computers could surpass their silicon-based predecessors, and what tasks these computers would perform.

First game-playing DNA computer revealed

The first game-playing DNA computer has been revealed – an enzyme-powered tic-tac-toe machine that cannot be beaten.

The human player makes his or her moves by dropping DNA into 3 by 3 square of wells that make up the board. The device then uses a complex mixture of DNA enzymes to determine where it should place its nought or cross, and signals its move with a green glow.

The device, dubbed MAYA, was developed by Milan Stojanovic, at Columbia University in New York, and Darko Stefanovic, at the University of New Mexico in Albuquerque. Kobi Benenson, who works on other DNA approaches at the Weizmann Institute in Israel, says the work demonstrates the most complex use of molecules as logic gates to date, and “represents a significant advance in DNA computing.”

More complex computational tasks than noughts and crosses could be tackled with different arrangements of the enzymes. But the pair acknowledges that the approach will never rival silicon computers, because human action is needed to operate the gates in system and it is not reusable.

“Its lovely work,” says Peter Bentley, a computer scientist linked to University College London. But he notes that a system that cannot be extended much further than playing tic-tac-toe “is merely a novelty”. Stojanovic and Stefanovic are aware of this and are now focusing on developing simple decision-making solutions that can operate in vivo. Molecules could, for example, assess faults in a living cell and then either kill or repair it.

Snip apart

In previous DNA computing schemes, all of the elements are mixed in a test tube and the answer to the calculation is deduced from the product of the reaction. MAYA is the first interactive system. The nine wells occupy just one square centimetre and each contains

Mixtures of the enzymes that act as molecular logic gates.

The human player has nine types of DNA strand, each with a sequence specific to a particular square. To make a move, one type of strand is added to all the squares, as all must be aware of the choice.

The DNA strands are the on-switch for the “deoxyribozyme” enzymes. The enzymes’ output, when activated by the required DNA strand, is to snip apart molecules in the mixture, which produces the green glow.

The enzyme gates are carefully constructed and distributed so that after the human’s move, the enzymes unlock only in one well. This is “quite ingenious” says Benenson. Because tic-tac-toe is a simple game, the computer could be designed so that it always wins or draws.

Stojanovic has lost to MAYA more than a 100 times. “We could have programmed it to lose sometimes, to make humans happy,” he told New Scientist. “But to say ‘the automaton can not be defeated’ has a nice ring to it.”

Molecular biologists are beginning to unravel the information-processing tools-such as enzymes, copying tool, proofreading mechanisms and so on- that evolution has spent billions of years refining. Now we’re taking those tools in large numbers of DNA molecules and using them as biological computer processors.

Here’s how it works. Information specifying a computational problem too complex for even a supercomputer is encoded in DNA. Then various molecular-biological tools are used to process this information.

In a hot-tub sized vat of DNA, at normal laboratory concentration, one might easily imagine having 10 ²¹ DNA molecules, each potentially encoding 400 bits of information. That’s 100,000 billion times as much information as you can store in your 1 gigabyte hard disk. Each of these molecules acts, in a sense, as a separate processor in a giant multiprocessor. So, in effect, we have a thousand billion processors

Sounds exciting, even Saganesque. But there are problems. One is that the algorithm proposed so far uses really slow molecular-biological operations. Each primitive operation in the DNA computer takes hours. That’s a clock rate maybe 10 ¹¹ times slower than your 100MHz Pentium.