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
相关论文
共 27 条
  • [1] ADLEMAN AGM, 2001, LINEAR SELF ASSEMBLI
  • [2] Adleman L, 2002, ANN IEEE SYMP FOUND, P530, DOI 10.1109/SFCS.2002.1181977
  • [3] ADLEMAN L, 1922, MATH THEORY SELF ASS
  • [4] MOLECULAR COMPUTATION OF SOLUTIONS TO COMBINATORIAL PROBLEMS
    ADLEMAN, LM
    [J]. SCIENCE, 1994, 266 (5187) : 1021 - 1024
  • [5] [Anonymous], 1986, TILINGS PATTERNS
  • [6] Two computational primitives for algorithmic self-assembly: Copying and counting
    Barish, RD
    Rothemund, PWK
    Winfree, E
    [J]. NANO LETTERS, 2005, 5 (12) : 2586 - 2592
  • [7] Bellman R., 1962, MATH MAG, V35, P27, DOI 10.2307/2689096
  • [8] BORNDORFER MGR, 1998, CHARLEMAGNE HIS HERI, V2
  • [9] BRUN NMY, 2007, P SOFTW ENG AD SELF, P2
  • [10] BRUN Y, 2008, THEORETIAL COMPUTER, V359, P3
123