DNA Solution of the Maximal Clique Problem
- 17 October 1997
- journal article
- other
- Published by American Association for the Advancement of Science (AAAS) in Science
- Vol. 278 (5337), 446-449
- https://doi.org/10.1126/science.278.5337.446
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.Keywords
This publication has 10 references indexed in Scilit:
- Parallel Overlap Assembly for the Construction of Computational DNA LibrariesJournal of Theoretical Biology, 1997
- Accessing Genetic Information with High-Density DNA ArraysScience, 1996
- Making DNA AddScience, 1996
- Single-step assembly of a gene and entire plasmid from large numbers of oligodeoxyribonucleotidesGene, 1995
- Molecular Computation of Solutions to Combinatorial ProblemsScience, 1994
- DNA shuffling by random fragmentation and reassembly: in vitro recombination for molecular evolution.Proceedings of the National Academy of Sciences, 1994
- PCR jumping in clones of 30-million-year-old DNA fragments from amber preserved termites (Mastotermes electrodominicus)Cellular and Molecular Life Sciences, 1993
- DNA polymerase fidelity and the polymerase chain reaction.Genome Research, 1991
- Polymerase chain reaction-mediated gene synthesis: synthesis of a gene coding for isozyme c of horseradish peroxidase.Proceedings of the National Academy of Sciences, 1991
- Site-directed mutagenesis by overlap extension using the polymerase chain reactionGene, 1989