简单0-1规划问题的动态DNA折纸计算模型

来源：计算机工程与应用杂志2020年第4期北京时间：

作者：斯燕方，殷志祥，崔建中，杨静，唐震

单位：1.安徽理工大学 数学与大数据学院，安徽 淮南 232001；2.安徽理工大学 电气与信息工程学院，安徽 淮南 232001；3.淮南联合大学 计算机系，安徽 淮南 232001

摘要：DNA折纸是一种全新的DNA自组装方法。将一个由DNA折纸卡槽、双态DNA机器、DNA行走机器人组装而成的动态折纸应用于求解0-1规划问题。其中DNA折纸卡槽由1条M13脚手架链和202条钉书钉链折叠而成。双态DNA机器分为不修饰和修饰金纳米颗粒两种情况，对应于0-1规划问题约束变量的取值为0或者1。DNA折纸卡槽和DNA双态机器组装成折纸基底。DNA行走机器人是7条单链折叠成的带有粘性末端的DNA折纸。在链的驱动下，DNA行走机器人在折纸基底上顺时针旋转行走，每步旋转120°。DNA行走机器人每走两步，与折纸基底上的DNA双态机器进行链置换，接收修饰的金纳米颗粒。当整个动态行走过程结束，根据透射电镜下DNA行走机器人接收的金纳米颗粒的大小和个数来判断约束变量的取值是否为可行解。该计算模型采用模块化结构，DNA折纸卡槽、双态DNA机器、DNA行走机器人等折纸均单独设计，且采用透射电镜读解，因而提高了模型实现的可行性。

关键词：DNA折纸术,0-1规划,DNA纳米技术,金纳米颗粒,DNA行走机器人