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
相关论文
共 50 条
  • [1] Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly
    Goos, Mika
    Orponen, Pekka
    DNA COMPUTING AND MOLECULAR PROGRAMMING, 2011, 6518 : 71 - 82
  • [2] Synthesizing Small and Reliable Tile Sets for Patterned DNA Self-assembly
    Lempiainen, Tuomo
    Czeizler, Eugen
    Orponen, Pekka
    DNA COMPUTING AND MOLECULAR PROGRAMMING, 2011, 6937 : 145 - 159
  • [3] Synthesis of tile sets for DNA self-assembly
    Ma, Xiaojun
    Lombardi, Fabrizio
    IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2008, 27 (05) : 963 - 967
  • [4] Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
    Czeizler, Eugen
    Popa, Alexandru
    THEORETICAL COMPUTER SCIENCE, 2013, 499 : 23 - 37
  • [5] Errors in DNA Self-Assembly By Synthesized Tile Sets
    Ma, X.
    Hashempour, M.
    Kim, Y. B.
    Lombardi, F.
    IEEE INTERNATIONAL SYMPOSIUM ON DEFECT AND FAULT TOLERANCE VLSI SYSTEMS, PROCEEDINGS, 2009, : 112 - 120
  • [6] A Graph Model for Tile Sets in DNA Self-Assembly
    Aran, Zahra Mashreghian
    Hashempour, Masoud
    Lorubardi, Fabrizio
    IEEE INTERNATIONAL WORKSHOP ON DESIGN AND TEST OF NANO DEVICES, CIRCUITS AND SYSTEMS, PROCEEDINGS, 2008, : 77 - 80
  • [7] Healing assessment of tile sets for error tolerance in DNA self-assembly
    Hashempour, M.
    Arani, Z. Mashreghian
    Lombardi, F.
    IET NANOBIOTECHNOLOGY, 2008, 2 (04) : 81 - 92
  • [8] Combinatorial Optimization Problem in Designing DNA Self-Assembly Tile Sets
    Ma, X.
    Lombardi, F.
    IEEE INTERNATIONAL WORKSHOP ON DESIGN AND TEST OF NANO DEVICES, CIRCUITS AND SYSTEMS, PROCEEDINGS, 2008, : 73 - 76
  • [9] The Complexity of Fixed-Height Patterned Tile Self-Assembly
    Seki, Shinnosuke
    Winslow, Andrew
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2017, 28 (05) : 465 - 482
  • [10] The Complexity of Fixed-Height Patterned Tile Self-assembly
    Seki, Shinnosuke
    Winslow, Andrew
    IMPLEMENTATION AND APPLICATION OF AUTOMATA, 2016, 9705 : 248 - 259
12345