Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 1997 Oct 17;278(5337):446-9.
doi: 10.1126/science.278.5337.446.

DNA solution of the maximal clique problem

Q Ouyang  1 , P D Kaplan, S Liu, A Libchaber
Affiliations

DNA solution of the maximal clique problem

Q Ouyang et al. Science. .

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.

PubMed Disclaimer

LinkOut - more resources