Publications on DNA based Computers

Here is the text of the New-York times article on DNA computing from 4/11/95.

Here is the text of the WIRED magazine article on DNA computing from August 95. It gives a nice overview of the subject. The original magazine article contains lots of figures which are not present here.

Papers on DNA computing from Princeton

• Breaking DES Using a Molecular Computer. By Dan Boneh, Richard Lipton and Chris Dunworth.

  Recently Adleman has shown that a small traveling salesman problem can be solved by molecular operations. In this paper we show how the same principles can be applied to breaking the Data Encryption Standard (DES). Our method is based on an encoding technique presented by Lipton. We describe in detail a library of operations which are useful when working with a molecular computer. We estimate that given one arbitrary (plain-text, cipher-text) pair, one can recover the DES key in about 4 months of work. Furthermore, if one is given cipher-text, but the plain text is only known to be one of several candidates then it is still possible to recover the key in about 4 months of work. Finally, under chosen cipher-text attack it is possible to recover the DES key in one day using some preprocessing.

• On the Computational Power of DNA. By Dan Boneh, Richard Lipton, Chris Dunworth and Jiri Sgall.

  We extend the results of Lipton to show how DNA based computers can be used to solve the satisfiability problem for circuits. We show that our methods enable random sampling of satisfying assignemnts. Furthermore, we show how one can solve optimization problems directly without first solving several decision problems. Finally we suggest a procedure for evaluating functions in the polynomial hierarchy.

• Making DNA Computers Error Resistant. By Dan Boneh and Richard Lipton,

  Recently Lipton showed that the formula satisfaction problem can be solved using a DNA based computer. The algorithm ignored the effects of errors that occur during biological experiments. In this paper we show that Lipton's algorithm can be made resistant to errors. In addition, we present a new circuit satisfaction algorithm which can be made error resistant using the same techniques.

• A Divide and Conquer Approach to Sequencing. By Dan Boneh and Richard Lipton,

  We suggest an approach to sequencing based on a ``divide and conquer method''. This approach eliminates the need for solving a hard NP-complete problem which arises when using traditional sequencing techniques. At the present time this algorithm has not been tried out in the lab. However, computer simulations using parts of the human genome provide some encouraging data.

• Batching DNA Computations. By Dan Boneh and Richard Lipton,

  In this short note we point out that in some cases batching computations on a molecular computer is very cheap. This is especially useful for breaking cryptosystems and can be useful for other applications as well.