The Arrayed Primer Extension Method for DNA Microchip Analysis. Molecular Computation of Satisfaction Problems
详细信息 查看全文
- 作者：Michael C. Pirrung ; Richard V. Connors ; Amy L. Odenbaugh ; Michael P. Montague-Smith ; Nathan G. Walcott ; and Jeff J. Tollett
- 刊名：Journal of the American Chemical Society
- 出版年：2000
- 出版时间：March 8, 2000
- 年：2000
- 卷：122
- 期：9
- 页码：1873 - 1882
- 全文大小：818K
- 年卷期：v.122,no.9(March 8, 2000)
- ISSN：1520-5126
文摘
A high fidelity, surface-based method of nucleic acid analysis has been developed based on DNApolymerase extension of primer-template complexes on DNA microchips. The ability of the method todiscriminate against mismatches and provide an almost "digital" signal recommended it for molecularcomputation. A DNA computer with the capability of solving nondeterministic polynomial time (NP)-completeproblems (those whose time-complexity function rises exponentially with the problem size) in polynomialtime using this Arrayed Primer EXtension (APEX) method was experimentally demonstrated. An algorithminvolving extension of surface-bound primer-template complexes, representing solutions and clauses of aBoolean formula, is described for the solution of two-, three-, and four-variable satisfiability (SAT) problems,including a 3SAT, exploiting the theoretical concepts of Lipton. A discussion of the principles of nondeterministiccomputing with APEX is also provided.