动态DNA折纸计算模型的可满足性问题

摘要

DNA折纸术与传统的DNA自组装技术不同,通过碱基互补配对能够可控地构造出高度复杂的纳米图案或结构.文中为了求解可满足问题设计了一种动态的折纸结构,该结构由DNA折纸卡槽、双态DNA机器、DNA行走机器人三部分组装而成.折纸卡槽由一条DNA长链和若干短链折叠而成,DNA行走机器人是由7条单链折成的三手四足DNA折纸结构,双态DNA机器分为修饰和不修饰荧光颗粒两种状态.DNA机器人的“手”通过链置换接收荧光颗粒,机器人的“脚”在链的驱动下以顺时针旋转120°在折纸卡槽和DNA双态机器组装而成的折纸基底上完成动态行走.根据可满足问题的约束变量选择性地接收荧光颗粒,每一步对应于一个变量的取值,以荧光团的个数映射问题的条件,以荧光团的颜色映射问题的解.该模型结构简单,其解易于观察,因而大大提高了模型的可行性和计算的准确性.