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

Knapsack Problem with DNA Algorithm Based on Biochips

通过生物芯片上的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.