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

Dynamic DNA Origami Computing Model for Simple 0-1 Programming Problem

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 origami is a new method of DNA self-assembly.A dynamic origami composed of DNA origami card slot,two-state DNA machine and DNA walker is applied to solve the 0-1 programming problem.The DNA origami card slot is formed by folding an M13 scaffold chain and 202 staple chains.The two-state DNA machine can be divided into two cases:unmodified and modified gold nanoparticles,and the value of the constraint variable corresponding to the 0-1 programming problem is 0 or 1.DNA origami card slots and two-state DNA machine are assembled into origami substrate.DNA walker is a DNA origami with sticky ends folded from seven single strands.Driven by the chain,the DNA walker rotates clockwise on the origami substrate,rotating 120 degrees per step.The DNA walker receives the modified gold nanoparticles by chain replacement with the two-state DNA machine on the origami substrate every two steps.When the whole dynamic walking process is over,the size and number of gold nanoparticles received by DNA walker under TEM can be used to determine whether the value of the constrained variables are feasible or not.The computational model adopts mod-ular structure.DNA origami card slot,two-state DNA machine,DNA walker and other origami are designed separately,and the model is read by TEM,so the feasibility of the model implementation is improved.