Application of DNA self-assembly for maximum matching problem

被引：0
|
作者：
Kou Z. [1 ]
Zhang H. [2 ]
Qiang X. [2 ]
Lan W. [2 ]
Zhang K. [3 ]
机构：
[1] Institute of Biomedical and Pharmaceutical Sciences, Hubei University of Technology, Wuhan, Hubei
[2] College of Computer Science, South-Central University for Nationalities, Wuhan, Hubei
[3] School of Computer Science, Wuhan University of Science and Technology, Wuhan, Hubei
来源：
Qiang, Xiaoli | 2016年 / American Scientific Publishers卷 / 13期
关键词：
DNA tile; Maximum matching problem; Self-assembly model;
D O I：
10.1166/jctn.2016.5184
中图分类号：
学科分类号：
摘要：
DNA tile self-assembly have been demonstrated to be used to solve graph theory or combinatorial optimization problem because of its high-density storage and huge-scale parallel computing ability. In this paper, tile self-assembly have been shown to be used for solving the maximum matching problem by mainly constructing four sub-systems which are seed configuration system, nondeterministic guess system, verification system and output system. These systems can be used to probabilistically get the feasible solution of the problem. The model can successfully perform the maximum matching problem in polynomial time with distinct tile types, parallel and at very low cost. Copyright © 2016 American Scientific Publishers. All rights reserved.
引用
收藏
页码：3562 / 3567
页数：5
相关论文
共 50 条
  • [21] Algorithmic self-assembly of DNA
    Winfree, Erik
    2006 INTERNATIONAL CONFERENCE ON MICROTECHNOLOGIES IN MEDICINE AND BIOLOGY, 2006, : 9 - 9
  • [22] Algorithmic DNA self-assembly
    Kao, Ming-Yang
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS, 2006, 4041 : 10 - 10
  • [23] Molecular Computations of the Maximal Clique Problem Using DNA Self-assembly
    Jing, Yang
    Cheng, Zhang
    Jin, Xu
    2009 FOURTH INTERNATIONAL CONFERENCE ON BIO-INSPIRED COMPUTING: THEORIES AND APPLICATIONS, PROCEEDINGS, 2009, : 230 - 234
  • [24] 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
  • [25] DNA Self-Assembly for Graph Vertex 3-Coloring Problem
    Wang, Yanfeng
    Hu, Peipei
    Shi, Xiaolong
    Cui, Guangzhao
    JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 2012, 9 (12) : 2086 - 2092
  • [26] COMPETITIVE-BINDING OF HISTONES TO DNA AND THE PROBLEM OF CHROMATIN SELF-ASSEMBLY
    PAPONOV, VD
    BIOCHEMISTRY-MOSCOW, 1980, 45 (09) : 1163 - 1170
  • [27] Implementation of the Multidimensional Knapsack Problem Using Self-Assembly of DNA Tiles
    Cheng, Zhen
    Chen, Zhihua
    Huang, Yufang
    Xu, Jin
    JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 2010, 7 (10) : 2122 - 2132
  • [28] Nanocapsules of Magnetic Au Self-Assembly for DNA Migration and Secondary Self-Assembly
    Wang, Ling
    Wang, Yitong
    Dong, Shuli
    Deng, Yongming
    Hao, Jingcheng
    ACS APPLIED MATERIALS & INTERFACES, 2018, 10 (06) : 5348 - 5357
  • [29] Self-Assembly for Maximum Yields Under Constraints
    Fox, Michael J.
    Shamma, Jeff S.
    2011 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS, 2011,
  • [30] Efficient tile assembly model for maximum matching problem
    Zhou, Xu
    Zhou, Yan-Tao
    Li, Ken-Li
    Pan, Guo
    Hunan Daxue Xuebao/Journal of Hunan University Natural Sciences, 2015, 42 (02): : 114 - 120
12345