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

作     者：杨新木 杨静 殷志祥 唐震 崔建中 Yang Xinmu;Yang Jing;Yin Zhixiang;Tang Zhen;Cui Jianzhong

作者机构：安徽理工大学数学与大数据学院安徽淮南232001 安徽理工大学电气与信息工程学院安徽淮南232001 香港大学教育学院香港999077 上海工程技术大学数理与统计学院上海201620 淮南联合大学计算机系安徽淮南232001 

出 版 物：《计算机应用研究》 (Application Research of Computers)

年 卷 期：2021年第38卷第3期

页      面：777-781页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

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

主　　题：0-1背包问题 DNA折纸术 DNA计算 Visual DSD软件 

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