背包问题DNA算法的反应设计及其生物实现(英文)  

DNA Ligation Design and Biological Realization of Knapsack Problem

作　　者：朱莹[1] 任立红[1] 丁永生[1,2] Kongsuwan Kritaya 

机构地区：[1]东华大学信息科学与技术学院,上海201620 [2]东华大学数字化纺织服装技术教育部工程研究中心,上海201620 [3]澳大利亚联邦科工组织畜牧业分部昆士兰生物科学研究基地

出　　处：《计算机学报》2008年第12期2207-2214,共8页Chinese Journal of Computers

基　　金：国家自然科学基金(60775052,70701009);上海市科学技术委员会重点基础研究项目(08JC1400100);上海市人才发展资金(001);上海市领军人才后备人选专项资金资助

摘　　要：有关背包问题的DNA算法近年来得到重视,文中实现了求解背包问题的并行搜索解的实验,通过最优的方法完成有限容量背包的物品选择.展示了面向反应的DNA片段设计,计算过程为溶液DNA高效连接反应,反应结果分别用定量(PCR)和定性(测序)两种方法检测.文中的方法适用于多重约束条件的优化问题.More attention has been paid to DNA computing for Knapsack Problem （KP）. The authors realized the biological experiment of parallel searching to solve KP, and used the most optimized method to select items within a limited knapsack. The DNA fragments designing is based on reactions and the computational procedure is high-efficiency DNA ligation. Two methods were used to detect the results. They are PCR （quantitative analysis） and sequencing （qualitative analysis）. It is suitable to the optimization of multiple restriction conditions.

关 键 词：背包问题 DNA计算 引物设计 高效连接 克隆测序 

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