DNA SOLUTION OF THE MAXIMAL CLIQUE PROBLEM

Authors
OUYANG Q KAPLAN PD LIU SM LIBCHABER A
Citation
Q. Ouyang et al., DNA SOLUTION OF THE MAXIMAL CLIQUE PROBLEM, Science, 278(5337), 1997, pp. 446-449
Citations number
15
Categorie Soggetti
Multidisciplinary Sciences
Journal title
Science → ACNP
ISSN journal
00368075
Volume
278
Issue
5337
Year of publication
1997
Pages
446 - 449
Database
ISI
SICI code
0036-8075(1997)278:5337<446:DSOTMC>2.0.ZU;2-J
Abstract
The maximal clique problem has been solved by means of molecular biolo gy techniques. A pool of DNA molecules corresponding to the total ense mble of six-vertex cliques was built, followed by a series of selectio n processes. The algorithm is highly parallel and has satisfactory fid elity. This work represents further evidence for the ability of DNA co mputing to solve NP-complete search problems.