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

来源：计算机工程与应用杂志2019年第16期北京时间：

作者：唐震，殷志祥，崔建中，杨静，孙侠

单位：1.安徽理工大学 数学与大数据学院，安徽 淮南 232001；2.安徽理工大学 电气与信息工程学院，安徽 淮南 232001

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

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