title: DNA solution of the maximal clique problem.
abstract: 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.
authors.affiliation: NEC Research Institute, 4 Independence Way, Princeton, NJ 08540, USA.
authors.forename: Q
authors.initials: Q
authors.lastname: Ouyang
authors.forename: P D
authors.initials: PD
authors.lastname: Kaplan
authors.forename: S
authors.initials: S
authors.lastname: Liu
authors.forename: A
authors.initials: A
authors.lastname: Libchaber
mesh_terms: 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
chemical_list: D009838:Oligodeoxyribonucleotides; D004247:DNA; D004262:DNA Restriction Enzymes