The Arrayed Primer Extension Method for DNA Microchip Analysis. Molecular Computation of Satisfaction Problems
Citations Over TimeTop 10% of 2000 papers
Abstract
A high fidelity, surface-based method of nucleic acid analysis has been developed based on DNA polymerase extension of primer−template complexes on DNA microchips. The ability of the method to discriminate against mismatches and provide an almost “digital” signal recommended it for molecular computation. A DNA computer with the capability of solving nondeterministic polynomial time (NP)-complete problems (those whose time−complexity function rises exponentially with the problem size) in polynomial time using this Arrayed Primer EXtension (APEX) method was experimentally demonstrated. An algorithm involving extension of surface-bound primer−template complexes, representing solutions and clauses of a Boolean 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 nondeterministic computing with APEX is also provided.
Related Papers
- To design PCR primers with Oligo 6 and Primer Premier 5(2004)
- → The organisation and management of agricultural extension and farmer-assistance—A note on developments in Botswana. Part 1: Organisation for extension and some extension problems(1980)2 cited
- Study of n-dimensional Extension Set(2001)
- Preliminary Discussion on Several Primer Sealers(2005)