The Application of DNA Molecule Algorithm on the Graph's Connectivity Problem

被引：0

作者：

Wang, Yanchai ^{[1
]}

Liu, Fangfang ^{[2
]}

Song, Ming ^{[2
]}

Dong, Yafei ^{[1
,2
]}

机构：

[1] Shaanxi Normal Univ, Dept Comp Sci, Xian 710062, Peoples R China

[2] Shaanxi Normal Univ, Dept Life Sci, Xian 710062, Peoples R China

来源：

JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE | 2015年 / 12卷 / 09期

基金：

中国国家自然科学基金;

关键词：

DNA Computing; DNA Molecule; Graph's Connectivity; COMPUTING MODEL; COMPUTATION;

D O I：

10.1166/jctn.2015.3997

中图分类号：

O6 [化学];

学科分类号：

0703 ;

摘要：

A DNA computing algorithm is proposed in this paper which uses DNA molecule algorithm to solve an NP-complete problem in the Graph theory, algorithm model of the connectivity problem are also established. According to the algorithm we need to design the special DNA molecule which will assemble based on a specific graph, then a series of experiments are performed to get the final answer. This biochemical algorithm could reduce the complexity of the connectivity problem. The biochemical experimental technologies are mature and available, which will provide a practical way to validate the practicability and effect of DNA molecule algorithm model.

引用

页码：2117 / 2120

页数：4

共 50 条

[41] Application of DNA Self-assembly for Maximum Matching Problem [J].

Zhang, Hui ;

Qiang, Xiaoli ;

Zhang, Kai .

BIO-INSPIRED COMPUTING - THEORIES AND APPLICATIONS, BIC-TA 2015, 2015, 562 :621-630

[42] Application of DNA chip on 0-1 planning problem [J].

Zhang, FY ;

Yin, ZX ;

Xu, J .

PROGRESS IN BIOCHEMISTRY AND BIOPHYSICS, 2003, 30 (03) :412-415

[43] A surface-based DNA algorithm for the minimal vertex cover problem [J].

PAN Linqiang XU Jin and LIU YachunDepartment of Control Science and Engineering Huazhong University of Science and Technology Wuhan China ;

Department of Mathematics and Physics Institute of Engineering and Technology Nanhua University Hengyang China .

Progress in Natural Science, 2003, (01) :80-82

[44] Closed circle DNA algorithm of maximum weighted independent set problem [J].

Li, Qingyan ;

Yin, Zhixiang ;

Chen, Min .

Advances in Intelligent Systems and Computing, 2013, 212 :113-121

[45] A surface-based DNA algorithm for the minimal vertex cover problem [J].

Pan, LQ ;

Xu, J ;

Liu, YC .

PROGRESS IN NATURAL SCIENCE-MATERIALS INTERNATIONAL, 2003, 13 (01) :78-80

[46] A surface-based DNA algorithm for the solving binary knapsack problem [J].

Darehmiraki, Majid ;

Nehi, Hasan Mishmast .

APPLIED MATHEMATICS AND COMPUTATION, 2007, 188 (02) :1991-1994

[47] The improvement on algorithm of DNA computing on 0-1 planning problem [J].

Zhou, Kang ;

Tong, Xiao-Jun ;

Xu, Jin .

PROCEEDINGS OF 2006 INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND CYBERNETICS, VOLS 1-7, 2006, :4282-+

[48] DNA-based algorithm for 0-1 planning problem [J].

Wang, L ;

Chen, ZP ;

Jiang, XH .

COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2005, VOL 4, PROCEEDINGS, 2005, 3483 :733-742

[49] The DNA self-assembly computing model for solving perfect matching problem of bipartite graph [J].

Lan W. ;

Xing Z. ;

Huang J. ;

Qiang X. .

Jisuanji Yanjiu yu Fazhan/Computer Research and Development, 2016, 53 (11) :2583-2593

[50] Application of quantum approximate optimization algorithm to job shop scheduling problem [J].

Kurowski, Krzysztof ;

Pecyna, Tomasz ;

Slysz, Mateusz ;

Rozycki, Rafal ;

Waligora, Grzegorz ;

Weglarz, Jan .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2023, 310 (02) :518-528

← 1 2 3 4 5 →