背包问题的三链DNA计算模型  

Knapsack problem based on three-stranded DNA structure model

作　　者：杨静[1] 殷志祥[1] 崔建中[2] 黄凯峰[3] 

机构地区：[1]安徽理工大学理学院,安徽淮南232001 [2]淮南联合大学,安徽淮南232001 [3]淮南职业技术学院,安徽淮南232001

出　　处：《合肥工业大学学报（自然科学版）》2014年第10期1194-1197,1258,共5页Journal of Hefei University of Technology：Natural Science

基　　金：国家自然科学基金资助项目(61170172)

摘　　要：背包问题是组合优化中很重要的NP问题。因为三链DNA的特殊结构在参与反应时可以减少计算模型的错解率,且在生化反应中利用磁珠分离法对解进行分离较方便准确,文章利用三链模型求解0-1背包问题和完全背包问题。首先将背包问题的约束条件进行分解,再将物品质量编码为DNA片段,链接反应后,利用凝胶电泳技术和三链模型检测所包含的物品组合,得到满足约束条件的物品组合,再利用此方法检测价值最大的组合,即问题的解。其他的背包问题也可用此方法来解决。The knapsack problem is an important NP problem in combinatorial optimization .In this pa-per ,three-chain model is used to solve 0-1 knapsack problem and complete knapsack problem because the special three-stranded DNA structure makes it possible to reduce the error rate of the model solu-tion w hen participating in the reaction ,and the use of magnetic bead separation of biochemical reac-tions for solution separation is also relatively easy and accurate .First ,the constraint conditions of knapsack problem are decomposed .Then the weight of items is coded as DNA fragments .After the link reaction ,items that are included in the portfolio are checked by using gel electrophoresis technol-ogy and three-chain model ,and these item combinations meet the constraint conditions .This method is reused to detect the combination with the maximum value ,which is the problem solution .This method can also be used to solve other knapsack problems .

关 键 词：0-1背包问题 完全背包问题 三链DNA DNA计算 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]