Application of DNA Self-assembly on Maximum Clique Problem

被引：0

作者：

Cui, Guangzhao ^{[1
]}

Li, Cuiling ^{[1
]}

Li, Haobin ^{[1
]}

Zhang, Xuncai ^{[2
]}

Li, Xiaoguan ^{[1
]}

机构：

[1] Henan Key Lab Informat Based Elect Appliances, Zhengzhou 450002, Peoples R China

[2] Huazhong Univ Sci & Technol, Dept Control Sci & Engn, Wuhan 430074, Peoples R China

来源：

ADVANCES IN COMPUTATIONAL INTELLIGENCE | 2009年 / 61卷

基金：

中国国家自然科学基金;

关键词：

Self-Assembly; MCP; Tiling; Nondeterministic; DNA Computing; CROSSOVER MOLECULES; COMPUTATION; MODEL;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Computation by self-assembly of DNA is an efficient method of executing parallel DNA computing, in which information is encoded in DNA tiles and a large number of tiles can be self-assembled via sticky end associations. Here, we investigate how basic ideas on tiling can be applied to solve maximum clique problem (MCP). We Suggest that these procedures can be realized on the molecular scale through the medium of self-assembled DNA tiles. By creating billions of copies of the participating DNA tiles. the algorithmic will run in parallel on all possible cliques. The potential of DNA computing by self-assembly for this problem is promising given the operational time complexity of Theta(n). This work shows further evidence for the ability of DNA computing to solve NP-Complete problems.

引用

页码：359 / +

页数：3

共 22 条

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

ADLEMAN, LM .

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

[2]

[Anonymous], 1998, Algorithmic self-assembly of DNA

[3] Two computational primitives for algorithmic self-assembly: Copying and counting [J].

Barish, RD ;

Rothemund, PWK ;

Winfree, E .

NANO LETTERS, 2005, 5 (12) :2586-2592

[4] Solving NP-complete problems in the tile assembly model [J].

Brun, Yuriy .

THEORETICAL COMPUTER SCIENCE, 2008, 395 (01) :31-46

[5] Nondeterministic polynomial time factoring in the tile assembly model [J].

Brun, Yuriy .

THEORETICAL COMPUTER SCIENCE, 2008, 395 (01) :3-23

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

Brun, Yuriy .

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

[7]

Carbone A, 2004, LECT NOTES COMPUT SC, V2950, P61

[8]

COOK M, 2004, P 10 INT M DNA BAS C, P91

[9] Antiparallel DNA double crossover molecules as components for nanoconstruction [J].

Li, XJ ;

Yang, XP ;

Qi, J ;

Seeman, NC .

JOURNAL OF THE AMERICAN CHEMICAL SOCIETY, 1996, 118 (26) :6131-6140

[10] DNA nanotubes self-assembled from triple-crossover tiles as templates for conductive nanowires [J].

Liu, D ;

Park, SH ;

Reif, JH ;

LaBean, TH .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2004, 101 (03) :717-722

← 1 2 3 →