The Maximum Matching Problem Based on Self-Assembly Model of Molecular Beacon

被引：3
|
作者：
Yang, Jing [1 ]
Yin, Zhixiang [1 ]
Huang, Kaifeng [2 ]
Cui, Jianzhong [1 ]
机构：
[1] Anhui Univ Sci & Technol, Sch Math & Big Data, Huainan 232001, Anhui, Peoples R China
[2] Huainan Normal Univ, Sch Mech & Elect Engn, Huainan 232001, Anhui, Peoples R China
来源：
NANOSCIENCE AND NANOTECHNOLOGY LETTERS | 2018年 / 10卷 / 02期
基金：
中国国家自然科学基金;
关键词：
Maximum Matching Problem; Molecular Beacon; Self-Assembly Tile; DNA Computing; Nanostructure; BREAST-CANCER CELLS; MAGNETIC NANOPARTICLES; GOLD NANOPARTICLES; COLORIMETRIC DETECTION; RAPID DETECTION; DNA SOLUTION; IN-SITU; APTAMER; SYSTEM; EFFICIENT;
D O I：
10.1166/nnl.2018.2616
中图分类号：
TB3 [工程材料学];
学科分类号：
0805 ; 080502 ;
摘要：
The maximum matching problem is a famous NP-complete problem. Some scholars also have given many algorithms using DNA computing. Its algorithm complexity is over n. Based on the special hairpin structure of the molecular beacon, this paper gives a new tile-the molecular beacon tile, and it has a simple structure, strong specificity, low rate of wrong solutions. Firstly, all combinations of arcs are set in the graph G map for binary sequences. Secondly, the self-assembled model of molecular beacon is applied to verify whether each combination is the matching of the graph G. Finally, gel electrophoresis is used to look for maximum matching in all matchings. This algorithm uses massive parallelism of the self-assembled model to reduce complexity to Theta(n).
引用
收藏
页码：213 / 218
页数：6
相关论文
共 50 条
  • [1] The Integer Linear Programming Problem Based on the Molecular Beacon Self-Assembly Model
    Yang, Jing
    Yin, Zhixiang
    Huang, Kaifeng
    Geng, Xianya
    Zhang, Qiang
    Cui, Jianzhong
    NANOSCIENCE AND NANOTECHNOLOGY LETTERS, 2018, 10 (10) : 1356 - 1363
  • [2] Application of DNA self-assembly for maximum matching problem
    Kou Z.
    Zhang H.
    Qiang X.
    Lan W.
    Zhang K.
    Qiang, Xiaoli, 2016, American Scientific Publishers (13) : 3562 - 3567
  • [3] 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
  • [4] Satisfiability problem based on self-assembly model of molecular beacons
    Yang, Jing
    Yin, Zhixiang
    Cui, Jianzhong
    Journal of Bionanoscience, 2015, 9 (03): : 197 - 202
  • [5] 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):
  • [6] Signal control by self-assembly of fluorophores in a molecular beacon-a model study
    Biner, Sarah M.
    Kummer, Dominic
    Malinovskii, Vladimir L.
    Haener, Robert
    ORGANIC & BIOMOLECULAR CHEMISTRY, 2011, 9 (08) : 2628 - 2633
  • [7] The Molecular Beacons Self-Assembly Model of the Dislocation Permutation Problem
    Yang, Jing
    Yin, Zhixiang
    Chen, Mingqiang
    Huang, Kaifeng
    JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 2015, 12 (07) : 1126 - 1131
  • [8] The Molecular Beacons Self-assembly Model of the Dislocation Permutation Problem
    Yang, Jing
    Yin, Zhixiang
    Chen, Mingqiang
    Cui, Jianzhong
    BIO-INSPIRED COMPUTING - THEORIES AND APPLICATIONS, BIC-TA 2014, 2014, 472 : 520 - 524
  • [9] 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 - +
  • [10] 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