Solution of the knapsack problem by deoxyribonucleic acid computing

Yohei Aoi, Tatsuo Yoshinobu, Katsuyuki Tanizawa, Kozo Kinoshita, Hiroshi Iwasaki

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


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 arc expected to realize a massively parallel computation of the order of 1023 per mol.

Original languageEnglish
Pages (from-to)5839-5841
Number of pages3
JournalJapanese Journal of Applied Physics
Issue number10
Publication statusPublished - 1998 Oct


  • Computing
  • DNA
  • DNA computing
  • Knapsack problem
  • Ligation
  • PCR
  • Polymerase chain reaction


Dive into the research topics of 'Solution of the knapsack problem by deoxyribonucleic acid computing'. Together they form a unique fingerprint.

Cite this