Solution of the knapsack problem by deoxyribonucleic acid computing

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

doi:10.1143/jjap.37.5839

Solution of the knapsack problem by deoxyribonucleic acid computing

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

MEN - Biomedical Engineering

Osaka University

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

Abstract

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 10²³ per mol.

Original language	English
Pages (from-to)	5839-5841
Number of pages	3
Journal	Japanese Journal of Applied Physics
Volume	37
Issue number	10
DOIs	https://doi.org/10.1143/jjap.37.5839
Publication status	Published - 1998 Oct

Keywords

Computing
DNA
DNA computing
Knapsack problem
Ligation
PCR
Polymerase chain reaction

Access to Document

10.1143/jjap.37.5839

Cite this

@article{da9dc061038247d2b6df15d98bdc50ef,

title = "Solution of the knapsack problem by deoxyribonucleic acid computing",

abstract = "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.",

keywords = "Computing, DNA, DNA computing, Knapsack problem, Ligation, PCR, Polymerase chain reaction",

author = "Yohei Aoi and Tatsuo Yoshinobu and Katsuyuki Tanizawa and Kozo Kinoshita and Hiroshi Iwasaki",

year = "1998",

month = oct,

doi = "10.1143/jjap.37.5839",

language = "English",

volume = "37",

pages = "5839--5841",

journal = "Japanese Journal of Applied Physics",

issn = "0021-4922",

publisher = "Japan Society of Applied Physics",

number = "10",

}

TY - JOUR

T1 - Solution of the knapsack problem by deoxyribonucleic acid computing

AU - Aoi, Yohei

AU - Yoshinobu, Tatsuo

AU - Tanizawa, Katsuyuki

AU - Kinoshita, Kozo

AU - Iwasaki, Hiroshi

PY - 1998/10

Y1 - 1998/10

N2 - 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.

AB - 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.

KW - Computing

KW - DNA

KW - DNA computing

KW - Knapsack problem

KW - Ligation

KW - PCR

KW - Polymerase chain reaction

UR - http://www.scopus.com/inward/record.url?scp=0032182354&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032182354&partnerID=8YFLogxK

U2 - 10.1143/jjap.37.5839

DO - 10.1143/jjap.37.5839

M3 - Article

AN - SCOPUS:0032182354

SN - 0021-4922

VL - 37

SP - 5839

EP - 5841

JO - Japanese Journal of Applied Physics

JF - Japanese Journal of Applied Physics

IS - 10

ER -

Solution of the knapsack problem by deoxyribonucleic acid computing

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this