Can DNA Compute?

For biological systems, DNA is a master problem solver, storing and manipulating prodigious amounts of information. Recently, researchers have been investigating whether the problem-solving power of DNA can be used to solve nonbiological problems, specifically, problems from computer science that are out of the reach of traditional computers. Would a DNA computer actually work? To answer this question, one must turn to mathematics.

In a groundbreaking 1994 paper, Leonard Adleman described a laboratory experiment involving DNA and a problem known as the Directed Hamiltonian Path Problem. Because of their massive complexity, this problem and others like it have eluded solution by conventional computers; no known algorithm can solve them in a reasonable amount of time. DNA has the potential to solve these kinds of problems because of its capacity to store a great deal of information compactly and to speedily perform operations on that information. The idea is that DNA could be used to perform massively parallel searches much more quickly than on traditional computers.

In his experiment, Adleman took the first step toward making this idea a reality: He got test tubes of DNA to solve a particular instance of the Directed Hamiltonian Path Problem. Adleman's device did not solve the problem in all its generality. What it did do is provide the first physical implementation of the idea of using DNA for computation. But Adleman's device can carry out one and only one set of calculations, leaving open the question of whether an all-purpose DNA computer is a practical possibility. Before investment capital firms rush to develop the first prototype, they will want hard evidence that a DNA computer would actually work. And this raises two questions that are fundamentally mathematical: Can any problem be simulated by a DNA computer, and can an all-purpose DNA computer be constructed theoretically?

For traditional computers, these two questions have been answered affirmatively. And this is why traditional computers work: What they do can be represented mathematically and proven to produce the right answers. Fuses may blow, screens may freeze up, and the Pentium chip might be faulty, but the underlying mathematics is flawless. What the DNA computer needed was a similar mathematical bedrock. Happily for the investment capitalists, mathematicians have provided the proof.

Lila Kari, a mathematician at the University of Western Ontario, describes the mathematical foundations of the DNA computer in her paper, "DNA Computing: The Arrival of Biological Mathematics." Using a branch of mathematics called formal language theory, she describes a mathematical model for DNA computation based on the notion of a "splicing system"---a system of cutting and pasting operations that simulate the action of DNA recombination---formulated by Tom Head of SUNY Binghamton. Once this system is represented in the language of mathematics, Kari's joint work with Rudolf Freund and Gheorghe Paun shows how one can establish that a DNA computer would actually work by providing the proof of affirmative answers to those two key questions. These results lift the DNA computer out of the realm of science fiction and put it on a firm mathematical foundation.

Kari's paper "DNA Computing: The Arrival of Biological Mathematics" and further information on this subject can be found on her home page, http://www.csd.uwo.ca/~lila.

-Allyn Jackson