More general applications of DNA computing

Without performing the actual molecular biology, Lipton suggested a modified and possibly more generally applicable approach. He designed a DNA-algorithm which solves the notorious satisfiability problem (SAT), which consists of a Boolean formula F with m clauses in the form Ui A U2 A. .. A Cm- Each clause is a formula 

Lipton s (hypothetical) DNA computer works as follows For k variables, 2 DNA strands are generated which encode the possible values of the variables. For instance, with 3 variables, we need 6 strands for a = 0,a = 1. = 1. In the initial DNA pool, these are linked up to form all the possible solutions of the problem. From this pool, molecules which satisfy the first clause of the problem are extracted in k (or less) steps. For instance, ifCi isx = 0Vy = lV.2 = l, three selective extractions of molecules meeting one of these conditions are carried out (each one from the initial pool, as we are dealing with the OR operation) and the extracts are combined (Fig. 2.14). To the solution of the combined extracts, extraction procedures corresponding to the second clause are applied (extracting from the extracts rather than from the initial pool corresponds to the logical AND operation). 

More generally, the variables can be replaced by fomulas, and any Boolean operations permitted, leading to general Boolean problems that are still NP-complete and can still be solved in a number of DNA experiments which is linear in the size of the formula. Furthermore, Lipton showed that DNA computing should solve SAT problems for general contact networks. 

However, all this is theory thus far, and experiments have to show that DNA really performs as it is told to do in these experiments. One of the practical aspects is that DNA replication has a natural error rate, which must not interfere with the results of the computation. 

Furthermore, replacing a computer by a molecular biologist or lab technician performing endless sequences of tedious extraction or replication procedures does not look like a step in the right direction. Therefore, practical proposals will also have to address the issue of automatization, ideally on a molecular level, with immobilized programmed enzymes doing all the work which L. Adleman did with his own hands in the very first demonstration of DNA computation. 

---