A novel computing model of the maximum clique problem based on circular DNA

被引：9

作者：

Yang Jing ^{[1
]}

Zhang Cheng ^{[1
]}

Xu Jin ^{[1
]}

Liu XiangRong ^{[1
]}

Qiang XiaoLi ^{[1
]}

机构：

[1] Peking Univ, Sch Elect Engn & Comp Sci, Key Lab High Confidence Software Technol, Inst Software,Minist Educ, Beijing 100871, Peoples R China

来源：

SCIENCE CHINA-INFORMATION SCIENCES | 2010年 / 53卷 / 07期

基金：

中国国家自然科学基金;

关键词：

DNA-based computing model; circular DNA molecules; NP-complete problem; circligase; streptavidin-coated magnetic beads; MOLECULAR COMPUTATION;

D O I：

10.1007/s11432-010-4009-6

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A novel DNA-based model is developed to calculate NP-complete problems, which is made of circular DNA molecules, streptavidin-coatecl magnetic beads and DNA circligase. To test the feasibility of the model, we apply it to compute a five-node maximum clique problem (MCP). During the computation, DNA molecule structures were transformed between linear DNA and circular DNA by streptavidin-coated magnetic beads and circligase, in order to search for the truth solutions. This greatly reduces the quantity of time and space consumed in calculation, and its time and space complexity both are O(n + m). Compared with the brute force method, using this algorithm searching process at most needs in n 1 test tubes for an MCP with n vertices, while brute force method requires 2(n) test tubes. Furthermore, the constructed unenumerable initial solution space greatly improved the processing ability of the DNA computer. This novel model indicates that it may be a powerful DNA-based computer for solving some NP-complete problems.

引用

页码：1409 / 1416

页数：8

共 13 条

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

ADLEMAN, LM .

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

[2]

BONDY JA, 1976, GRAPH THEORY APPL, P109

[3] Arithmetic computation in the tile assembly model: Addition and multiplication [J].

Brun, Yuriy .

THEORETICAL COMPUTER SCIENCE, 2007, 378 (01) :17-31

[4] Circuits and programmable self-assembling DNA structures [J].

Carbone, A ;

Seeman, NC .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2002, 99 (20) :12577-12582

[5] Molecular computation: RNA solutions to chess problems [J].

Faulhammer, D ;

Cukras, AR ;

Lipton, RJ ;

Landweber, LF .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2000, 97 (04) :1385-1389

[6] Computing with DNA by operating on plasmids [J].

Head, T ;

Rozenberg, G ;

Bladergroen, RS ;

Breek, CKD ;

Lommerse, PHM ;

Spaink, HP .

BIOSYSTEMS, 2000, 57 (02) :87-93

[7]

Karp R.M., 1972, PLENUM PRESS SURV ST, P85, DOI 10.1007/978-1-4684-2001-2_9

[8]

Kasuga T, 2001, Methods Mol Biol, V163, P135

[9] DNA SOLUTION OF HARD COMPUTATIONAL PROBLEMS [J].

LIPTON, RJ .

SCIENCE, 1995, 268 (5210) :542-545

[10] Logical computation using algorithmic self-assembly of DNA triple-crossover molecules [J].

Mao, CD ;

LaBean, TH ;

Reif, JH ;

Seeman, NC .

NATURE, 2000, 407 (6803) :493-496

← 1 2 →