The DNA Computer

      Talk given at the Australian Open Access User Group meeting on 13 October 1998
      by Michael Paine.

      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? pic
      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. pic
      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:

      • a solution to the problem existed, and
      • the answer(s) would be in the sequence(s) on the remaining strands.
      His attempt at solving a seven-city, 14 flight map took seven days of lab work. This particular problem can be manually solved in a few minutes but the key point about Adleman's work is that it will work on a much larger scale, when manual or conventional computing techniques become overwhelmed. "The DNA computer provides enormous parallelism... in one fiftieth of a teaspoon of solution approximately 10 to the power 14 DNA 'flight numbers' were simultaneously concatenated in about one second".

      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

      • 17 June 1999: BBC item Biological Computer Prototype Unveiled
      • 9 Mar 2000 ExoScience: DNA computer solves chess problem.
      • 22 Nov 01 BBC: Test tube holds a trillion computers + Nature.
      • 27 Feb 03 SciAm: New DNA Computer Functions sans Fuel.
      • 5 Nov 08 SciAm ($): Smart DNA: Programming the Molecule of Life for Work and Play.
      • 3 Jun 11 New Scientist: See-saw logic gates make DNA computing easier.
      • 311 May 19 New Scientist: DNA coated with silica could store masses of data in a single gram.
      • 1 Sep 24! New Scientist: DNA computer can play chess and solve sudoku puzzles.


      Go to main web page