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 条
  • [1] Precise Simulation Model for DNA Tile Self-Assembly
    Fujibayashi, Kenichi
    Murata, Satoshi
    IEEE TRANSACTIONS ON NANOTECHNOLOGY, 2009, 8 (03) : 361 - 368
  • [2] 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
  • [3] Solving the Assignment Problem by Algorithmic Tile Self-Assembly
    Cheng, Zhen
    Xiao, Jianhua
    NANOSCIENCE AND NANOTECHNOLOGY LETTERS, 2012, 4 (12) : 1132 - 1139
  • [4] A microfluidic device for DNA tile self-assembly
    Somei, Koutaro
    Kaneda, Shohei
    Fujii, Teruo
    Murata, Satoshi
    DNA COMPUTING, 2006, 3892 : 325 - 335
  • [5] Physical principles for DNA tile self-assembly
    Evans, Constantine G.
    Winfree, Erik
    CHEMICAL SOCIETY REVIEWS, 2017, 46 (12) : 3808 - 3829
  • [6] 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
  • [7] Algorithm of Solving the Subset-Product Problem Based on DNA Tile Self-Assembly
    Cheng, Zhen
    Xu, Jin
    Huang, Yufang
    Zhang, Xuncai
    Zhou, Kang
    JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 2009, 6 (05) : 1161 - 1169
  • [8] Self-assembly of Patterns in the Abstract Tile Assembly Model
    Drake, Phillip
    Patitz, Matthew J.
    Summers, Scott M.
    Tracy, Tyler
    UNCONVENTIONAL COMPUTATION AND NATURAL COMPUTATION, UCNC 2024, 2024, 14776 : 89 - 103
  • [9] Algorithmic Tile Self-Assembly for Solving the Maximal Matching Problem
    Cheng, Zhen
    Huang, Yufang
    Xiao, Jianhua
    Advances in Intelligent Systems and Computing, 2013, 212 : 845 - 854
  • [10] One dimensional boundaries for DNA tile self-assembly
    Schulman, R
    Lee, S
    Papadakis, N
    Winfree, E
    DNA COMPUTING, 2004, 2943 : 108 - 125
12345