Solution of the knapsack problem by deoxyribonucleic acid computing

Deoxyribonucleic acid (DNA) computing is executed to demonstrate that it is capable of solving a simple instance of the knapsack problem, which is known to be NP-complete. DNA molecules with different lengths coding the data are prepared, and the algorithm is implemented as molecular biological processes such as ligation,polymerase chain reaction (PCR), and DNA sequencing. The scheme of encoding, experimental procedures and results are described, and the scalability of the present method is discussed. Reactions between DNA molecules are expected to realize a massively parallel computation of the order of 10(23) per mol.