Computer Engineering and Applications ›› 2019, Vol. 55 ›› Issue (16): 49-54.DOI: 10.3778/j.issn.1002-8331.1806-0318

Previous Articles     Next Articles

DNA Origami for an Application of Special Integer Programming Problem

TANG Zhen, YIN Zhixiang, CUI Jianzhong, YANG Jing, SUN Xia   

  1. 1.School of Mathematics and Big Data, Anhui University of Science and Technology, Huainan, Anhui 232001, China
    2.School of Electronic and Information Engineering, Anhui University of Science and Technology, Huainan, Anhui 232001, China
  • Online:2019-08-15 Published:2019-08-13

DNA折纸术在一类特殊的整数规划问题中的应用

唐震,殷志祥,崔建中,杨静,孙侠   

  1. 1.安徽理工大学 数学与大数据学院,安徽 淮南 232001
    2.安徽理工大学 电气与信息工程学院,安徽 淮南 232001

Abstract: A design based on DNA origami is proposed to solve a special integer programming problem. For this kind of integer programming problem, design all possible values of the variables for a long DNA strand(scaffold). Hairpin structures are formed by adding the corresponding staples, then, the hairpin structures are used to map out the problem solution. When the integer programming problem has[n]variables, its solution can be mapped onto[n]hairpin structures (the length of the scaffold is [l+nt]). For non-solutions, by adding staples to increase the hairpin structures of scaffold, thus the scaffold will lengthen(over [l+nt]). These non-solutions are eliminated by gel electrophoresis and the feasible solutions are retained.

Key words: DNA origami, DNA self-assembly, integer programming

摘要: 基于DNA折纸术设计并找出一类特殊的整数规划问题的最优解。将这类整数规划问题中的[n]个变量及对应的所有可能值设计成一条长链(脚手架链),通过添加相应的订书钉链形成发夹结构来映射出问题的解。当整数规划问题中有[n]个变量时,它的解可以映射成[n]个发夹结构(长链的长度为[l+nt])。同时对于非解,通过添加订书钉链的方法来增加长链的发夹结构,从而使得长链的长度变长(超过[l+nt]),再通过凝胶电泳来排除这些非解,最后保留可行解。

关键词: DNA折纸术, DNA自组装, 整数规划