Application of DNA Self-Assembly on 0-1 Integer Programming Problem

被引：5

作者：

Zhang, Xuncai ^{[1
,2
]}

Niu, Ying ^{[1
]}

Cui, Guangzhao ^{[1
]}

Xu, Jin ^{[2
]}

机构：

[1] Zhengzhou Univ Light Ind, Coll Elect & Elect Engn, Zhengzhou 450002, Peoples R China

[2] Huazhong Univ Sci & Technol, Dept Control Sci & Engn, Wuhan 430074, Peoples R China

来源：

JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE | 2010年 / 7卷 / 01期

基金：

中国国家自然科学基金;

关键词：

Self-Assembly; 0-1 Integer Programming Problem; DNA Tile; Parallel Computing; DNA Computing; COMPUTATION;

D O I：

10.1166/jctn.2010.1341

中图分类号：

O6 [化学];

学科分类号：

0703 ;

摘要：

Self-assembly of DNA is an efficient method of executing parallel DNA computing where information is encoded in DNA tiles and a large number of tiles can be self-assembled via sticky end associations We investigate how basic ideas on tiling can be applied to solving 0-1 integer programming problem. It suggests that these procedures can be realized on the molecular scale through the medium of self-assembled DNA tiles. By creating billions of billions of copies of the participating DNA tiles, the algorithm will run in parallel on all possible solutions. The potential of DNA computing by self-assembly for the 0-1 integer programming problem is promising given the operational time complexity of O(m * n). This work shows further evidence for the ability of DNA computing to solve NP-complete problems

引用

页码：165 / 172

页数：8

共 50 条

[21] DNA computation model to solve 0-1 programming problem
Zhang, FY
Yin, ZX
Liu, B
Xu, J
BIOSYSTEMS, 2004, 74 (1-3) : 9 - 14
[22] EQUIVALENCE OF THE 0-1 INTEGER PROGRAMMING PROBLEM TO DISCRETE GENERALIZED AND PURE NETWORKS
GLOVER, F
MULVEY, JM
OPERATIONS RESEARCH, 1980, 28 (03) : 829 - 836
[23] An improved integer linear programming formulation for the closest 0-1 string problem
Arbib, Claudio
Servilio, Mara
Ventura, Paolo
COMPUTERS & OPERATIONS RESEARCH, 2017, 80 : 94 - 100
[24] The Combinatorial Tree Method of Solving Nonlinear 0-1 Integer Programming Problem
Song, Laizhong
Zhang, Xianbo
Yi, Miansheng
NFD 2010: INTERNATIONAL CONFERENCE ON NETWORK AND FINANCE DEVELOPMENT, 2010, : 159 - 164
[25] DNA computation for a category-of 0-1 programming problem
Guo, Ping
Yu, HaiFeng
2008 PROCEEDINGS OF INFORMATION TECHNOLOGY AND ENVIRONMENTAL SYSTEM SCIENCES: ITESS 2008, VOL 4, 2008, : 40 - 43
[26] DNA computation model to solve 0-1 programming problem
Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China
不详
Jisuanji Xuebao, 2008, 12 (2155-2159):
[27] Application of DNA chip on 0-1 planning problem
Zhang, FY
Yin, ZX
Xu, J
PROGRESS IN BIOCHEMISTRY AND BIOPHYSICS, 2003, 30 (03) : 412 - 415
[28] FURTHER COMMENTS ON APPLICATION OF 0-1 INTEGER PROGRAMMING TO MULTITARGET TRACKING PROBLEMS
LEHTOMAKI, NA
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1980, 25 (04) : 856 - 856
[29] 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
[30] Using a mixed integer programming tool for solving the 0-1 quadratic knapsack problem
Billionnet, A
Soutif, E
INFORMS JOURNAL ON COMPUTING, 2004, 16 (02) : 188 - 197

← 1 2 3 4 5 →