Liu Q, Wang L, Frutos A G, Condon A E, Corn R M, Smith L M
Department of Chemistry, University of Wisconsin, Madison 53706, USA.
Nature. 2000 Jan 13;403(6766):175-9. doi: 10.1038/35003155.
DNA computing was proposed as a means of solving a class of intractable computational problems in which the computing time can grow exponentially with problem size (the 'NP-complete' or non-deterministic polynomial time complete problems). The principle of the technique has been demonstrated experimentally for a simple example of the hamiltonian path problem (in this case, finding an airline flight path between several cities, such that each city is visited only once). DNA computational approaches to the solution of other problems have also been investigated. One technique involves the immobilization and manipulation of combinatorial mixtures of DNA on a support. A set of DNA molecules encoding all candidate solutions to the computational problem of interest is synthesized and attached to the surface. Successive cycles of hybridization operations and exonuclease digestion are used to identify and eliminate those members of the set that are not solutions. Upon completion of all the multistep cycles, the solution to the computational problem is identified using a polymerase chain reaction to amplify the remaining molecules, which are then hybridized to an addressed array. The advantages of this approach are its scalability and potential to be automated (the use of solid-phase formats simplifies the complex repetitive chemical processes, as has been demonstrated in DNA and protein synthesis). Here we report the use of this method to solve a NP-complete problem. We consider a small example of the satisfiability problem (SAT), in which the values of a set of boolean variables satisfying certain logical constraints are determined.
DNA计算作为一种解决一类棘手计算问题的方法被提出，这类问题的计算时间会随着问题规模呈指数增长（即“NP完全”或非确定性多项式时间完全问题）。该技术原理已通过哈密顿路径问题的一个简单示例在实验中得到证明（在这种情况下，是找到几个城市之间的航空飞行路线，使得每个城市仅被访问一次）。其他问题的DNA计算方法也已得到研究。一种技术涉及将DNA的组合混合物固定并在载体上进行操作。合成一组编码感兴趣计算问题所有候选解的DNA分子，并将其附着在表面。通过连续的杂交操作和核酸外切酶消化循环来识别和消除该集合中那些不是解的成员。在所有多步循环完成后，使用聚合酶链反应来扩增剩余分子，从而识别出计算问题的解，然后将这些分子与一个寻址阵列进行杂交。这种方法的优点是其可扩展性和自动化潜力（使用固相形式简化了复杂的重复化学过程，正如在DNA和蛋白质合成中所证明的那样）。在此，我们报告使用这种方法来解决一个NP完全问题。我们考虑可满足性问题（SAT）的一个小示例，其中要确定一组满足某些逻辑约束的布尔变量的值。
