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 条

[21] Molecular self-assembly
Rouvray, D
CHEMISTRY IN BRITAIN, 2000, 36 (07) : 26 - 29
[22] DNA Self-assembly Model for Matrix Addition Problem
Yin, Zhixiang
Song, Bosheng
JOURNAL OF COMPUTERS, 2011, 6 (04) : 698 - 704
[23] Implementation of Minimum Vertex Cover Problem Based on Tile Self-Assembly Model
Cheng, Zhen
Huang, Yufang
JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 2013, 10 (09) : 2123 - 2130
[24] Molecular Model for the Self-Assembly of the Cyclic Lipodepsipeptide Pseudodesmin A
Crowet, Jean-Marc
Sinnaeve, Davy
Feher, Krisztina
Laurin, Yoann
Deleu, Magali
Martins, Jose C.
Lins, Laurence
JOURNAL OF PHYSICAL CHEMISTRY B, 2019, 123 (42): : 8916 - 8922
[25] MODEL SELF-ASSEMBLY
不详
CHEMICAL & ENGINEERING NEWS, 2010, 88 (50) : 30 - 30
[26] Computing by molecular self-assembly
Jonoska, Natasa
Seeman, Nadrian C.
INTERFACE FOCUS, 2012, 2 (04) : 504 - 511
[27] The self-assembly of metal-based molecular hexagons
Loeb, SJ
Hall, JR
Deslippe, CN
ABSTRACTS OF PAPERS OF THE AMERICAN CHEMICAL SOCIETY, 1996, 212 : 160 - INOR
[28] Molecular Self-Assembly of the α-Carboxysome
Oltrogge, Luke M.
Chaijarasphong, Thawatchai
Savage, David F.
BIOPHYSICAL JOURNAL, 2018, 114 (03) : 63A - 63A
[29] MOLECULAR SELF-ASSEMBLY PROCESSES
STODDART, JF
CIBA FOUNDATION SYMPOSIA, 1991, 158 : 5 - 22
[30] MOLECULAR RECOGNITION AND SELF-ASSEMBLY
STODDART, JF
ANALES DE QUIMICA, 1993, 89 (01): : 51 - 56

← 1 2 3 4 5 →