 |
 |
Top Right: Each city (vertex) is represented by a different sequence of nucleotides (6 here, but Adleman used 20). |
 |
 |
Bottom Right: A DNA linker (edge) joining two city (vertex) strands. |
DNA Computing
by Mike Wisz
In a test tube somewhere at a lab in USC, one-fiftieth of a teaspoon of DNA chugged away at a problem, perhaps the first ancestor of a future generation of computers that will leave today's supercomputers in the dust. This past November, Dr. Leonard Adleman found a way to exploit the speed and efficiency the biological reactions to solve the "Hamiltonian path problem," also known as the "traveling salesman problem." His DNA computing experiment has been heralded as the "first example of true nanotechnology", and even the "start of a new era," forging an unprecedented link between computational science and life science.
|
|
Top Right: Each city (vertex) is represented by a different sequence of nucleotides (6 here, but Adleman used 20). |
|
|
Bottom Right: A DNA linker (edge) joining two city (vertex) strands. |
Graphics by Andrew Huang
All computers in existence today make use of binary code - 1's and 0's, or on's and off's on the circuits of a computer chip, forming the basis for every calculation a computer performs, from simple addition to the solution of the most complex differential equations. Since the DNA molecule is also a code, but instead made up of a sequence of four bases which pair up in a predictable manner, Adleman saw the possibility for using it as a molecular computer. However, rather than relying on the position of electronic switches on a microchip, Adleman relied on the much faster reactions of DNA nucleotides binding with their complements, a brute force method that would indeed work.
The "Hamiltonian path problem" basically involves finding all the possible paths between a certain number of vertices. The name "traveling salesman problem" comes from viewing each vertex as a city, with the problem to find all possible routes for a salesman passing through each of these cities. Adleman used DNA to solve a system of six vertices, which is not difficult for modern computers, but as the number of cities grows so does the number of paths between them, making a 1,000 city path impossible to solve for even the best supercomputers.
Adleman's first step was to synthesize DNA strands of known sequences, each strand 20 nucleotides long. He represented each of the six vertices of the path by a separate strand, and further represented each edge between two consecutive vertices, such as 1 to 2, by a DNA strand which consisted of the last ten nucleotides of the strand representing vertex 1 plus the first 10 nucleotides of the vertex 2 strand. Then, through the sheer amount of DNA molecules (3x1013 copies for each edge in this experiment!) joining together in all possible combinations, many random paths were generated.
 |
 |
 |
The travelling salesman problem: as the number of cities grows, even supercomputers have difficulty finding the shortest path. |
Adleman used well-established techniques of molecular biology to weed out the Hamiltonian path, the one that entered all vertices, starting at one and ending at six. After generating the numerous random paths in the first step, he used polymerase chain reaction (PCR) to amplify and keep only the paths that began on vertex 1 and ended at vertex 6. The next two steps kept only those strands that passed through six vertices, entering each vertex at least once. At this point, any paths that remained would code for a Hamiltonian path, thus solving the problem.
Although Adleman admits that he is unsure how to proceed for paths much larger than six vertices, the power of molecular computers is still worth comparing to today's systems. In speed, the DNA clearly wins the race, performing 1,000 operations per second more than the fastest supercomputers (which execute about 1012 operations per second). To get a better idea of the speed, consider that a typical desktop computer performs a thousand million times slower than the DNA, a measly 106 operations per second!
In energy efficiency, a biological system such as a cell can perform 2x1019 power operations using one joule of energy (the amount of energy needed to burn a 100-watt light bulb for a second), while a supercomputer only manages 1010 operations, making it 1010 less energy efficient! Just as the cell pushes the limit of the second law of thermodynamics, which predicts that one joule can fuel a maximum of 34x1019 irreversible power operations, the DNA computer's energy consumption from DNA strand synthesis and PCR should also be small compared to that used up by a supercomputer.
The potential for information storage in molecular computers follows the same trend as speed and efficiency. While storage media of today, such as videotapes, store information at a density of one bit per 1012 cubic nanometers, the molecules of DNA make this figure seem ridiculous, with an information storage density of 1 bit per cubic nanometer - a trillion times less space!
 |
| DNA finds a solution! A Hamiltonian path with all vertices included is isolated and recovered |
Even though Adleman's molecular computer would have a hard time multiplying two 100-digit integers, an easy task for one of today's electronic computers, its capability to solve complex problems is unparalleled. However, as work continues in this exciting area, molecular computers may impress us once again and challenge the dominance of electronic systems in solving even more types of problems. After all, the DNA based system of computation has had millions of years to evolve and perfect itself, while man-made systems have only existed for a small fraction of this span. It is an impressive computer indeed that can spend eons producing new and varied organisms through trial and error until it finally finds a solution - the intelligent species we call human beings. The computers of tomorrow are on the threshold.
Mike Wisz is a physics senior