Solving River Crossing Puzzle in the DNA Tile Self-Assembly Model

被引：0
|
作者：
Wang, Yanfeng [1 ,2 ]
Zheng, Yan [2 ]
Zhang, Xuncai [1 ,2 ]
Cui, Guangzhao [1 ,2 ]
机构：
[1] Zhengzhou Univ Light Ind, Res & Dev Ctr Biol Informat Technol, Zhengzhou 450002, Peoples R China
[2] Zhengzhou Univ Light Ind, Coll Elect & Elect Engn, Zhengzhou 450002, Peoples R China
来源：
JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE | 2011年 / 8卷 / 04期
基金：
美国国家科学基金会;
关键词：
DNA Self-Assembly; Tile Assembly Model; River Crossing Puzzle; Nondeterministic System; COMPUTATION;
D O I：
10.1166/jctn.2011.1725
中图分类号：
O6 [化学];
学科分类号：
0703 ;
摘要：
DNA computation potentially provides a degree of parallelism far beyond that of conventional silicon-based computers. The tile assembly model of DNA molecules is a highly distributed parallel model of nature's self-assembly. Here we present a method for solving river crossing puzzle by DNA tile self-assembly. The computation is nondeterministic and each parallel assembly executes in time linear in the input. The system requires only a constant number of different tile types: 58. In addition, we also describe mechanisms for finding the successful solutions among the many parallel assemblies and explore bounds on the probability of such a nondeterministic system succeeding.
引用
收藏
页码：579 / 585
页数：7
相关论文
共 50 条
  • [21] Integrating DNA strand-displacement circuitry with DNA tile self-assembly
    David Yu Zhang
    Rizal F. Hariadi
    Harry M.T. Choi
    Erik Winfree
    Nature Communications, 4
  • [22] Integrating DNA strand-displacement circuitry with DNA tile self-assembly
    Zhang, David Yu
    Hariadi, Rizal F.
    Choi, Harry M. T.
    Winfree, Erik
    NATURE COMMUNICATIONS, 2013, 4
  • [23] An algorithm for solving maximum clique problem based on self-assembly model of DNA
    Zhou, Y.-T. (yantao_z@hnu.edu.cn), 1600, Hunan University (39):
  • [24] Distributed agreement in tile self-assembly
    Aaron Sterling
    Natural Computing, 2011, 10 : 337 - 355
  • [25] Verification in staged tile self-assembly
    Schweller, Robert
    Winslow, Andrew
    Wylie, Tim
    NATURAL COMPUTING, 2019, 18 (01) : 107 - 117
  • [26] Smart Tile Self-Assembly and Replication
    Kari, Lila
    Simjour, Amirhossein
    FUNDAMENTA INFORMATICAE, 2017, 154 (1-4) : 239 - 260
  • [27] Distributed agreement in tile self-assembly
    Sterling, Aaron
    NATURAL COMPUTING, 2011, 10 (01) : 337 - 355
  • [28] Verification in Staged Tile Self-Assembly
    Schweller, Robert
    Winslow, Andrew
    Wylie, Tim
    UNCONVENTIONAL COMPUTATION AND NATURAL COMPUTATION, UCNC 2017, 2017, 10240 : 98 - 112
  • [29] 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
  • [30] 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
12345