A Surface-Based Approach to DNA Computation

A new model of DNA-based computation is presented. The main difference between this model and that of Adleman is in manipulation of DNA strands that are first immobilized on a surface. This approach greatly reduces losses of DNA molecules during purification steps. A simple, surface-based model of computation is described and it is shown how to implement an exhaustive search algorithm for the SAT problem on this model. Partial experimental progress in solving a 5-variable SAT instance is described, and possible extensions of our model that allow general computations are discussed. Liu, Guo, Corn and Smith are in the Chemistry Department, Condon is in the Computer Sciences Department and Lagally is in the Materials Sciences Department. Email address for further communication: condon @cs.wisc.edu. 1 Introduction Adleman [1] and subsequently Lipton [5] described how genetic engineering tools can be used to solve instances of NP-complete combinatorial problems. Their work has led to h..