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

doi:10.3778/j.issn.1002-8331.1812-0293

计算机工程与应用 ›› 2020, Vol. 56 ›› Issue (4): 168-174.DOI: 10.3778/j.issn.1002-8331.1812-0293

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

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

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

出版日期:2020-02-15 发布日期:2020-03-06

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

SI Yanfang, YIN Zhixiang, CUI Jianzhong, YANG Jing, TANG Zhen

1.School of Mathematics and Big Data, Anhui University of Science and Technology, Huainan, Anhui 232001, China
2.School of Electrical and Information Engineering, Anhui University of Science and Technology, Huainan, Anhui 232001, China
3.Department of Computer Science, Huainan University, Huainan, Anhui 232001, China

Online:2020-02-15 Published:2020-03-06

摘要/Abstract

摘要：

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行走机器人

Abstract:

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 modular 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.

Key words: DNA origami, 0-1 programming problem, DNA nanotechnology, gold nanoparticles, DNA walker

斯燕方，殷志祥，崔建中，杨静，唐震. 简单0-1规划问题的动态DNA折纸计算模型[J]. 计算机工程与应用, 2020, 56(4): 168-174.

SI Yanfang, YIN Zhixiang, CUI Jianzhong, YANG Jing, TANG Zhen. Dynamic DNA Origami Computing Model for Simple 0-1 Programming Problem[J]. Computer Engineering and Applications, 2020, 56(4): 168-174.

[1]	唐震，殷志祥，崔建中，杨静，孙侠. DNA折纸术在一类特殊的整数规划问题中的应用[J]. 计算机工程与应用, 2019, 55(16): 49-54.
[2]	肖华勇，马丽娜，程海礁. 老板数独的方程求解算法研究[J]. 计算机工程与应用, 2014, 50(9): 41-44.
[3]	王继强. 集合覆盖问题的模型与算法[J]. 计算机工程与应用, 2013, 49(17): 15-17.
[4]	陈露晨. 基于0-1规划的快速图像阈值分割算法[J]. 计算机工程与应用, 2012, 48(10): 197-199.
[5]	杨昆¹，徐静²，张彦斌¹. 基因选择的0-1规划模型和算法[J]. 计算机工程与应用, 2010, 46(20): 184-187.
[6]	万里平,蔡美玲,高春鸣. 基于服务联盟的Web服务组合模型及方法[J]. 计算机工程与应用, 2007, 43(31): 137-140.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics