摘要
有关背包问题的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.
出处
《计算机学报》
EI
CSCD
北大核心
2008年第12期2207-2214,共8页
Chinese Journal of Computers
基金
国家自然科学基金(60775052,70701009)
上海市科学技术委员会重点基础研究项目(08JC1400100)
上海市人才发展资金(001)
上海市领军人才后备人选专项资金资助
关键词
背包问题
DNA计算
引物设计
高效连接
克隆测序
knapsack problem
DNA computing
primers design
high-efficiency ligation
clone sequencing
