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

doi:10.3778/j.issn.1002-8331.1806-0318

计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (16): 49-54.DOI: 10.3778/j.issn.1002-8331.1806-0318

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

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

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

出版日期:2019-08-15 发布日期:2019-08-13

DNA Origami for an Application of Special Integer Programming Problem

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

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

摘要/Abstract

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

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

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折纸术在一类特殊的整数规划问题中的应用[J]. 计算机工程与应用, 2019, 55(16): 49-54.

TANG Zhen, YIN Zhixiang, CUI Jianzhong, YANG Jing, SUN Xia. DNA Origami for an Application of Special Integer Programming Problem[J]. Computer Engineering and Applications, 2019, 55(16): 49-54.

[1]	杨雅洁，苌道方，余芳. 考虑AGV避碰的自动化码头多资源协同调度[J]. 计算机工程与应用, 2020, 56(6): 246-253.
[2]	斯燕方，殷志祥，崔建中，杨静，唐震. 简单0-1规划问题的动态DNA折纸计算模型[J]. 计算机工程与应用, 2020, 56(4): 168-174.
[3]	王雪琴1，蒋建国1，2，齐美彬1，2. 全局分层关联网络流在多目标跟踪中的应用[J]. 计算机工程与应用, 2018, 54(14): 180-185.
[4]	张亚琦，杨斌，胡志华，田茂金. 自动化码头AGV充电与作业的集成调度研究[J]. 计算机工程与应用, 2017, 53(18): 257-262.
[5]	刘潇1，常建平2. MIP-BSM：基于基站移动的最大化网络寿命方案[J]. 计算机工程与应用, 2016, 52(13): 147-151.
[6]	阳成虎，林志云，林梦男. 双渠道下服装生产-分销网络优化模型研究[J]. 计算机工程与应用, 2015, 51(19): 219-225.
[7]	范志强. 带作业范围约束的岸桥调度模型及其算法设计[J]. 计算机工程与应用, 2015, 51(17): 259-264.
[8]	范志强. 考虑复杂需求特性的多级煤炭供应链网络优化[J]. 计算机工程与应用, 2014, 50(5): 21-28.
[9]	黄帅，马良. 改进和声搜索算法求解一般整数规划问题[J]. 计算机工程与应用, 2014, 50(3): 250-252.
[10]	邓立军，刘剑. 基于分层法的通风网络图绘制算法研究[J]. 计算机工程与应用, 2014, 50(15): 1-6.
[11]	魏平，熊伟清. 求解强异类集装箱装载问题的混合蚁群算法[J]. 计算机工程与应用, 2013, 49(7): 252-257.
[12]	魏林1，付华2，尹玉萍2. 和声蚁群耦合算法求解整数规划的应用研究[J]. 计算机工程与应用, 2013, 49(20): 5-8.
[13]	李奔驰1，2，党创寅2，郑津津1. 分布式整数规划及其在航线扰动问题的应用[J]. 计算机工程与应用, 2013, 49(14): 19-24.
[14]	徐标，陈昊，安佰玲. 基于EPFF算法的下料问题模型[J]. 计算机工程与应用, 2013, 49(13): 56-58.
[15]	黄俊歆1，2，王李管1，徐少游1，熊书敏1，谭正华1，陈建宏1. 一种新的露天配矿开采几何约束模型及其应用[J]. 计算机工程与应用, 2013, 49(1): 245-248.

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

DNA Origami for an Application of Special Integer Programming Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics