计算机应用研究

作者：杨新木,杨静,殷志祥,唐震,崔建中,

单位：1.安徽理工大学a.数学与大数据学院;b.电气与信息工程学院,安徽淮南232001；2.香港大学教育学院,香港999077；3.上海工程技术大学数理与统计学院,上海201620；4.淮南联合大学计算机系,安徽淮南232001；

关键词：0-1背包问题,DNA折纸术,DNA计算,VisualDSD软件,

基金：国家自然科学基金资助项目(61702008,61672001)；安徽省博士后基金资助项目(2019B331)；安徽省自然科学基金资助项目(1808085MF193)；2019年高校优秀青年骨干人才国外访问研修项目(gxgwfx2019015)；安徽高校自然科学研究项目(KJ2019A0538)；；

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

来源：2021年第3期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2021年第3期