The August 1998 issue of Scientific American has an article "Computing with DNA" by Leonard Adleman. In this talk I would like to provide a brief description of Adleman's work because it could mark the beginning of a profound new development in computing power.
Adleman is a qualified mathematician and computer scientist. He was one of the inventors of the RSA public-key encryption system. Recently he studied molecular biology, including DNA manipulation. This is, of course, a controversial field but it evident that many "tools" have been developed to assist molecular biologists splice and rebuild DNA sequences. Custom sequences can now even be "made to order". The customer just specifies the particular sequences of A, T, G and C components and the supplier creates the sequence, duplicates it and sends the resulting DNA (a small white lump of paste in a test tube) to the customer.
His brilliant insight was to realise than the method by which DNA works
in nature is a form of Turing Machine and such a machine can be used to
solve computational problems. He therefore devised a way of applying
DNA manipulation techniques to the "Hamilton Path Problem" - for several
cities, some of which are connected by non-stop flights, does a path exist
to travel from A to B which passes through every other city once and only
once?
When the number of cities gets to around one hundred it could take
hundreds of years of conventional computer time to solve the problem, even
with the most advanced parallel processing available.
Adleman developed a method of manipulating DNA which, in effect, conducts
trillions of computations in parallel. Essentially he coded each city and
each possible flight as a sequence of 4 components. For example he coded
one city as GCAG and another as TCGG.
The incredible thing is that once the DNA sequences had been created
he simply "just added water" to initiate the "computation":. The DNA strands
then began their highly efficient process of creating new sequences based
on the input sequences.
If an "answer" to the problem for a given set of inputs existed then
it should amongst these trillions of sequences. The next (difficult)
step was to isolate the "answer" sequences. To do this Adleman used a range
of DNA tools. For example, one technique can test for the correct start
and end sequences, indicating that the strand has a solution for the start
and end cities. Another step involved selecting only those strands which
have the correct length, based on the total number of cities in the problem
(remembering that each city is visited once).
Finally another technique was used to determine if the sequence for
each city was included in the strand. If any strands were left after
these processes then:
Scientists and mathematicians around the world are now looking at the application of these techniques to a whole range of "intractable" computing problems. DNA computers won't be replacing the common old PC in the foreseeable future but this development could well go down as a significant step in human history: the merging of two great discoveries of the 20th Century - computing and molecular biology.
Update