A BIOLOGICAL MOLECULE BASED COMPUTING METHOD BASED ON A BLOCKING PRINCIPLE

摘要

A computational method that makes use of DNA molecules is disclosed. The method can be summarized as follows. First, a set of DNA molecules representing (by their sequences) all possible assignment to all variables of a given computational problem is generated (this is the so-called combinatorial library of the problem). Second, all the DNA molecules representing assignments which do not correspond to solutions of the problem are inactivated (blocked) for reproduction or detection. Finally, one has to check only whether any active (non-blocked) molecules remain: a solution of the problem exists if and only if any such molecules remain. In principle this allows to solve computationally difficult problems. We illustrate our method by outlining a solution for the famous satisfiability problem using the polymerase chain reaction (PCR) method only.