Application of DNA Self-assembly for Maximum Matching Problem

被引：0

作者：

Zhang, Hui ^{[1
]}

Qiang, Xiaoli ^{[1
]}

Zhang, Kai ^{[2
]}

机构：

[1] South Cent Univ Nationalities, Coll Comp Sci, Wuhan 430074, Hubei, Peoples R China

[2] Wuhan Univ Sci & Technol, Sch Comp Sci, Wuhan 430081, Hubei, Peoples R China

来源：

BIO-INSPIRED COMPUTING - THEORIES AND APPLICATIONS, BIC-TA 2015 | 2015年 / 562卷

关键词：

DNA tile; Self-assembly model; Maximum matching problem; NEURAL P SYSTEMS; SYNAPSES WORKING; COMPUTATION; STRATEGY; RULES; MODEL;

D O I：

10.1007/978-3-662-49014-3_55

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

DNA tile self-assembly have been demonstrated to be used to solve graph theory or combinatorial optimization problem because of its high-density storage and huge-scale parallel computing ability. In this paper, tile self-assembly have been shown to be used for solving the maximum matching problem by mainly constructing four sub-systems which are seed configuration system, nondeterministic guess system, verification system and output system. These systems can be used to probabilistically get the feasible solution of the problem. The model can successfully perform the maximum matching problem in polynomial time with distinct tile types, parallel and at very low cost.

引用

页码：621 / 630

页数：10

共 26 条

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

ADLEMAN, LM .

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

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

Barish, RD ;

Rothemund, PWK ;

Winfree, E .

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

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

Brun, Yuriy .

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

[4]

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

[5] 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

[6]

Gehani A, 1999, 5 DIMACS WORKSH DNA

[7] 3D DNA Self-Assembly Model for Graph Vertex Coloring [J].

Lin, Minqi ;

Xu, Jin ;

Zhang, Dafang ;

Chen, Zhihua ;

Zhang, Xuncai ;

Cheng, Zhen ;

Huang, Yufang ;

Li, Yanbiao .

JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 2010, 7 (01) :246-253

[8]

Liu Wen-bin, 2003, Acta Electronica Sinica, V31, P1496

[9] Designed two-dimensional DNA Holliday junction arrays visualized by atomic force microscopy [J].

Mao, CD ;

Sun, WQ ;

Seeman, NC .

JOURNAL OF THE AMERICAN CHEMICAL SOCIETY, 1999, 121 (23) :5437-5443

[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 3 →