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

DNA Origami for an Application of Special Integer Programming Problem

作　　者：唐震 殷志祥 崔建中 杨静 孙侠 TANG Zhen;YIN Zhixiang;CUI Jianzhong;YANG Jing;SUN Xia(School of Mathematics and Big Data, Anhui University of Science and Technology, Huainan, Anhui 232001, China;School of Electronic and Information Engineering,Anhui University of Science and Technology, Huainan,Anhui 232001, China)

机构地区：[1]安徽理工大学数学与大数据学院,安徽淮南232001 [2]安徽理工大学电气与信息工程学院,安徽淮南232001

出　　处：《计算机工程与应用》2019年第16期49-54,共6页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61672001,No.61702008);安徽省自然科学基金(No.1808085MF193)

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]