基于生物芯片的背包问题DNA算法  

Knapsack Problem with DNA Algorithm Based on Biochips

作　　者：朱莹[1] 丁永生[1] 李汪根[1] 

机构地区：[1]东华大学信息科学与技术学院,上海201620

出　　处：《计算机科学》2008年第6期243-245,共3页Computer Science

基　　金：国家自然科学基金重点项目(60534020);教育部新世纪优秀人才支持计划(NCET-04-415);教育部科技创新工程重大项目培育资金项目(706024);上海市国际科技合作基金项目(061307041)

摘　　要：通过生物芯片上的DNA算法求解背包问题。先将给定问题的约束条件进行分解,然后将物品重量映射为DNA序列,再依次在设计好的生物芯片上进行链接反应、凝胶电泳、探针检测和放射自显影,最后得到问题的解。本文的工作是在生物芯片上实现DNA算法,求解优化问题的一次有益尝试。This paper focuses on the lab-on-a-chip DNA computation to solve the Knapsack Problem （KP）. Firstly,we partition the constraint of KP into several different constraints. Secondly, we design some oligonucleotides corresponding to the weight of the items and other ligation splints, with which the combinations of the items can happen randomly. Thirdly, we design a biochip, on which there happens the ligation,Gel Electrophoresis （GE）, probe detection and auto- radiograph. Finally, we get the optimal solutions to the given problem. We take the initiative work in realizing DNA algorithm for optimal research on biochips.

关 键 词：DNA计算 生物芯片 背包问题 链接反应 凝胶电泳 DNA探针 放射自显影 

分 类 号：O157.5[理学—数学] Q503[理学—基础数学]