Computer Engineering and Applications ›› 2020, Vol. 56 ›› Issue (4): 168-174.DOI: 10.3778/j.issn.1002-8331.1812-0293

Previous Articles     Next Articles

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

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

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



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


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



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