DNA折纸术在0-1背包问题中的应用

摘要

DNA折纸术因其反应的可编程性、纳米可寻址性等优点被广泛地应用于DNA计算中.利用DNA折纸术和杂交链式反应构建0-1背包问题的计算模型.以四个变量的0-1背包问题为例,首先将九种发夹结构和一种分子信标锚定在DNA折纸基底上并加入足量的辅助链;其次通过加入不同的引发链可以触发不同路径上的杂交链式反应,并得到问题的所有可能解;最后,通过荧光信号的数量确定可行解,从而找到问题的最优解.该模型不受权重过大或过小的影响,在折纸基底上可等比例的缩放权重.用Visual DSD软件对该模型进行仿真,模型显示出良好的可行性.