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 条
  • [1] Application of DNA Self-assembly for Maximum Matching Problem
    Zhang, Hui
    Qiang, Xiaoli
    Zhang, Kai
    BIO-INSPIRED COMPUTING - THEORIES AND APPLICATIONS, BIC-TA 2015, 2015, 562 : 621 - 630
  • [2] Application of DNA Self-assembly on Maximum Clique Problem
    Cui, Guangzhao
    Li, Cuiling
    Li, Haobin
    Zhang, Xuncai
    Li, Xiaoguan
    ADVANCES IN COMPUTATIONAL INTELLIGENCE, 2009, 61 : 359 - +
  • [3] The Maximum Matching Problem Based on Self-Assembly Model of Molecular Beacon
    Yang, Jing
    Yin, Zhixiang
    Huang, Kaifeng
    Cui, Jianzhong
    NANOSCIENCE AND NANOTECHNOLOGY LETTERS, 2018, 10 (02) : 213 - 218
  • [4] Application of DNA Self-Assembly on Graph Coloring Problem
    Zhang, Xuncai
    Niu, Ying
    Cui, Guangzhao
    Xu, Jin
    JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 2009, 6 (05) : 1067 - 1074
  • [5] 3D DNA Self-Assembly for the Maximum Clique Problem
    Zhang, Xuncai
    Fan, Ruili
    Wang, Yanfeng
    Cui, Guangzhao
    PROCEEDINGS OF THE 10TH WORLD CONGRESS ON INTELLIGENT CONTROL AND AUTOMATION (WCICA 2012), 2012, : 438 - 443
  • [6] 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):
  • [7] Application of DNA Nanoparticle Conjugation on the Maximum Matching Problem
    Ma Jingjing
    Xu Jin
    JOURNAL OF ELECTRONICS & INFORMATION TECHNOLOGY, 2021, 43 (10) : 2952 - 2957
  • [8] Application of DNA Computing by Self-assembly on 0-1 Knapsack Problem
    Cui, Guangzhao
    Li, Cuiling
    Zhang, Xuncai
    Wang, Yanfeng
    Qi, Xinbo
    Li, Xiaoguang
    Li, Haobin
    ADVANCES IN NEURAL NETWORKS - ISNN 2009, PT 3, PROCEEDINGS, 2009, 5553 : 684 - +
  • [9] Application of 3D DNA Self-Assembly for Graph Coloring Problem
    Zhang, Xuncai
    Lin, Minqi
    Niu, Ying
    JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 2011, 8 (10) : 2042 - 2049
  • [10] Application of DNA Self-Assembly on 0-1 Integer Programming Problem
    Zhang, Xuncai
    Niu, Ying
    Cui, Guangzhao
    Xu, Jin
    JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 2010, 7 (01) : 165 - 172
12345