DNA solution of the maximal clique problem

被引：390

作者：

Ouyang, Q ^{[1
]}

Kaplan, PD ^{[1
]}

Liu, SM ^{[1
]}

Libchaber, A ^{[1
]}

机构：

[1] ROCKEFELLER UNIV,CTR STUDIES PHYS & BIOL,NEW YORK,NY 10021

来源：

SCIENCE | 1997年 / 278卷 / 5337期

关键词：

D O I：

10.1126/science.278.5337.446

中图分类号：

O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];

学科分类号：

07 ; 0710 ; 09 ;

摘要：

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.

引用

页码：446 / 449

页数：4

共 15 条

[1] MOLECULAR COMPUTATION OF SOLUTIONS TO COMBINATORIAL PROBLEMS [J].

ADLEMAN, LM .

SCIENCE, 1994, 266 (5187) :1021-1024

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[3]

CASTI J, 1997, NEW SCI, V2082, P30

[4] Accessing genetic information with high-density DNA arrays [J].

Chee, M ;

Yang, R ;

Hubbell, E ;

Berno, A ;

Huang, XC ;

Stern, D ;

Winkler, J ;

Lockhart, DJ ;

Morris, MS ;

Fodor, SPA .

SCIENCE, 1996, 274 (5287) :610-614

[5] PCR JUMPING IN CLONES OF 30-MILLION-YEAR-OLD DNA FRAGMENTS FROM AMBER PRESERVED TERMITES (MASTOTERMES-ELECTRODOMINICUS) [J].

DESALLE, R ;

BARCIA, M ;

WRAY, C .

EXPERIENTIA, 1993, 49 (10) :906-909

[6]

Eckert K A, 1991, PCR Methods Appl, V1, P17

[7] Making DNA add [J].

Guarnieri, F ;

Fliss, M ;

Bancroft, C .

SCIENCE, 1996, 273 (5272) :220-223

[8] SITE-DIRECTED MUTAGENESIS BY OVERLAP EXTENSION USING THE POLYMERASE CHAIN-REACTION [J].

HO, SN ;

HUNT, HD ;

HORTON, RM ;

PULLEN, JK ;

PEASE, LR .

GENE, 1989, 77 (01) :51-59

[9] POLYMERASE CHAIN REACTION-MEDIATED GENE SYNTHESIS - SYNTHESIS OF A GENE CODING FOR ISOZYME-C OF HORSERADISH-PEROXIDASE [J].

JAYARAMAN, K ;

FINGAR, SA ;

SHAH, J ;

FYLES, J .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1991, 88 (10) :4084-4088

[10] Parallel overlap assembly for the construction of computational DNA libraries [J].

Kaplan, PD ;

Qi, OY ;

Thaler, DS ;

Libchaber, A .

JOURNAL OF THEORETICAL BIOLOGY, 1997, 188 (03) :333-341

← 1 2 →