|
|||||
|
|
| 收缩背包问题的DNA算法 | |
| 引用本文： | 刘毅,宋玉阶.收缩背包问题的DNA算法[J].计算机工程与科学,2007,29(8):55-57. |
| 作者姓名： | 刘毅 宋玉阶 |
| 作者单位： | 1. 武汉科技大学信息科学与工程学院,湖北,武汉,430081;武汉科技大学城市学院,湖北,武汉,430083 2. 武汉科技大学信息科学与工程学院,湖北,武汉,430081 |
| 摘 要： | 收缩背包问题是标准背包问题的一个扩展，其中背包的容量为所装物品数量的非增函数。本文提出了基于分子生物技术的求解收缩背包问题的DNA算法，首先将其约束条件进行分解；然后设计一系列与物品重量相对应的寡聚核苷酸片断及其链接模板，在链接酶的作用下将它们进行链接反应，生成代表任意物品组合的DNA链；再通过基本的生物操 作筛选出可行解；最后比较各个可行解对应的目标函数值，进而得到最优解。 |
| 关 键 词： | DNA计算 收缩背包问题 链接反应 凝胶电泳 DNA探针 放射自显影 |
| 文章编号： | 1007-130X（2007）08-0055-03 |
| 修稿时间： | 2006-08-292007-03-21 |
Collapsing Knapsack Problem Based on DNA Computing |
|
| LIU Yi,SONG Yu-jie.Collapsing Knapsack Problem Based on DNA Computing[J].Computer Engineering & Science,2007,29(8):55-57. | |
| Authors: | LIU Yi SONG Yu-jie |
| Affiliation: | School of Information Science and Engineering, Wuhan University of Science and Technology, Wuhan 430081, China |
| Abstract: | The collapsing knapsack problem （CKP） is the transformation of the standard knapsack problem （SKP）. The capacity of its knapsack is the non-increa sing function of the number of items loaded in it. A novel algorithm based on DNA computing is proposed, which solves the collapsing knapsack problem. F irstly, we partition the constraint of CKP into several different constraints. Secondly, we design some oligonucleotides corresponding to the weight of the items and some ligation splints which are mixed together in a single ligation reaction to produce the DNA links representing all random combinations of the items. Thirdly, we perform a series of biochemical experiments to obtain the feasible solutions. Finally, we get the optimal solutions to the given problem by comparing the target-function＇s values of those feasible solutions. |
| Keywords: | DNA computing collapsing knapsack problem ligature gel electrophoresis DNA probe autoradiography |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《计算机工程与科学》浏览原始摘要信息 | |
| 点击此处可从《计算机工程与科学》下载全文 | |
