Making DNA computers error resistant

Abstract

We describe methods for making volume decreasing algorithms more resistant to certain types of errors. Such error recovery techniques are crucial if DNA computers ever become practical. Our first approach relies on applying PCR at various stages of the computation. We analyze its performance and show that it increases the survival-probability of various strands to acceptable proportions. Our second approach relies on changing the method by which information is encoded on DNA strands. This encoding is likely to reduce false negative errors during the bead separation procedure. 1 Introduction In the short history of DNA (deoxyribonucleic acid) based computing there have already been a number of exciting results. It all started with Adleman's [A] beautiful insight that showed that biological experiments could solve the Directed Hamiltonian Path problem (DHP). Then, Lipton [L] showed how to use DNA to solve more general problems, namely to find satisfying assignments for arbitrary (direct...