DNA solution of the maximal clique problem.
The maximal clique problem has been solved by means of molecular biology techniques. A pool of DNA molecules corresponding to the total ensemble of six-vertex cliques was built, followed by a series of selection processes. The algorithm is highly parallel and has satisfactory fidelity. This work represents further evidence for the ability of DNA computing to solve NP-complete search problems.
Ouyang
Q
Q
NEC Research Institute, 4 Independence Way, Princeton, NJ 08540, USA.
Kaplan
P D
PD
Liu
S
S
Libchaber
A
A
D000465:Algorithms; D001483:Base Sequence; D003205:Computing Methodologies; D004247:DNA / Q000378:metabolism; D004262:DNA Restriction Enzymes / Q000378:metabolism; D004926:Escherichia coli / Q000235:genetics; D008969:Molecular Sequence Data; D009838:Oligodeoxyribonucleotides; D016133:Polymerase Chain Reaction
D009838:Oligodeoxyribonucleotides; D004247:DNA; D004262:DNA Restriction Enzymes