DNA Computing Research

NB: This is older work from when I was in graduate school at Caltech.
It is no longer an active area of research in my group.

Error reduction

  • Unreliable basic operations are a major concern when thinking about implementing DNA computing algorithms in the laboratory. Rather than attempting to improve these biotechnology primitives, it is possible to modify the algorithms that one implements in order to achieve a resiliance to errors.
  • In collaboration with Erik Winfree I wrote a paper, On the reduction of errors in DNA computation, which describes several methods for doing this.
    (A modified version also appeared as the second half of our longer paper A Sticker based model for DNA computation, presented at the DIMACS conference in June 1996.)

Stickers model

  • Many physical encodings of information in DNA-like molecules are possible. I wrote a paper with Erik Winfree and other members of Len Adleman's research group proposing one such encoding in which bit values are indicated by the presence or absence of an annealed tag called a sticker on a backbone strand.
  • The paper, A Sticker based model for DNA computation, appeared in the Journal of Computational Biology.
    (A modified version also appeared as the first half of our longer paper.
  • I presented this paper at the 2nd Annual Workshop on DNA Based Computers which was held in Princeton June 10-12 1996. The colour 35mm slides from that talk are available here as a package of 24 gifs, about 1 meg total size.)

Cracking DES

  • There has been a lot of debate as to whether DNA computing can tackle difficult real world problems using reasonable volumes and masses of materials and in reasonable times. To make the point that this can in fact be done, Len Adleman's research group wrote a paper in JCB titled On applying molecular computation to the data encryption standard.
    (An earlier version was also presented at the DIMACS conference in June 1996.)

The AMS has published a book of the proceedings of the conference, which was volume 44 of the series.

Science news
There have been a couple of short magazine pieces featuring the DNA computing research on this page.
Science News vol.150 (13 July 1996)
Science News vol.149 (22 June 1996)


[ | Information | Research | Teaching | Professional | ]

Sam Roweis, Vision, Learning and Graphics Group, NYU, www.cs.nyu.edu/~roweis