Search methods for tile sets in patterned DNA self-assembly

被引：12

作者：

Goos, Mika ^{[1
]}

Lempiainen, Tuomo ^{[1
]}

Czeizler, Eugen ^{[1
]}

Orponen, Pekka ^{[1
]}

机构：

[1] Aalto Univ, Helsinki Inst Informat Technol HIIT, Dept Informat & Comp Sci, Aalto, Finland

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2014年 / 80卷 / 01期

关键词：

DNA self-assembly; Tilings; Tile Assembly Model; Pattern assembly; Tile set synthesis; Reliable self-assembly; NANOSTRUCTURES; COMPUTATION; ORIGAMI; DESIGN;

D O I：

10.1016/j.jcss.2013.08.003

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The Pattern self-Assembly Tile set Synthesis (PATS) problem, which arises in the theory of structured DNA self-assembly, is to determine a set of coloured tiles that, starting from a bordering seed structure, self-assembles to a given rectangular colour pattern. The task of finding minimum-size tile sets is known to be NP-hard. We explore several complete and incomplete search techniques for finding minimal, or at least small, tile sets and also assess the reliability of the solutions obtained according to the kinetic Tile Assembly Model. (C) 2013 Elsevier Inc. All rights reserved.

引用

页码：297 / 319

页数：23

共 42 条

[1]

[Anonymous], 1986, TILINGS PATTERNS

[2] On the best search strategy in parallel branch-and-bound: Best-First Search versus Lazy Depth-First Search [J].

Clausen, J ;

Perregaard, M .

ANNALS OF OPERATIONS RESEARCH, 1999, 90 (0) :1-17

[3]

Czeizler Eugen, 2012, DNA Computing and Molecular Programming. Proceedings 18th International Conference, DNA 18, P58, DOI 10.1007/978-3-642-32208-2_5

[4]

Czeizler Eugen, 2011, P 8 ANN C FDN NAN SE, P186

[5] Self-assembly of DNA into nanoscale three-dimensional shapes [J].

Douglas, Shawn M. ;

Dietz, Hendrik ;

Liedl, Tim ;

Hoegberg, Bjoern ;

Graf, Franziska ;

Shih, William M. .

NATURE, 2009, 459 (7245) :414-418

[6] Design tools for a DNA-guided self-assembling carbon nanotube technology [J].

Dwyer, C ;

Johri, V ;

Cheung, M ;

Patwardhan, J ;

Lebeck, A ;

Sorin, D .

NANOTECHNOLOGY, 2004, 15 (09) :1240-1245

[7] Programmed-Assembly System Using DNA Jigsaw Pieces [J].

Endo, Masayuki ;

Sugita, Tsutomu ;

Katsuda, Yousuke ;

Hidaka, Kumi ;

Sugiyama, Hiroshi .

CHEMISTRY-A EUROPEAN JOURNAL, 2010, 16 (18) :5362-5368

[8] Assembly of Single-Walled Carbon Nanotubes on DNA-Origami Templates through Streptavidin-Biotin Interaction [J].

Eskelinen, Antti-Pekka ;

Kuzyk, Anton ;

Kaltiaisenaho, Toni K. ;

Timmermans, Marina Y. ;

Nasibulin, Albert G. ;

Kauppinen, Esko I. ;

Torma, Paivi .

SMALL, 2011, 7 (06) :746-750

[9] Toward reliable algorithmic self-assembly of DNA tiles: A fixed-width cellular automaton pattern [J].

Fujibayashi, Kenichi ;

Hariadi, Rizal ;

Park, Sung Ha ;

Winfree, Erik ;

Murata, Satoshi .

NANO LETTERS, 2008, 8 (07) :1791-1797

[10] Precise Simulation Model for DNA Tile Self-Assembly [J].

Fujibayashi, Kenichi ;

Murata, Satoshi .

IEEE TRANSACTIONS ON NANOTECHNOLOGY, 2009, 8 (03) :361-368

← 1 2 3 4 5 →