摘要
DNA折纸术因其反应的可编程性、纳米可寻址性等优点被广泛地应用于DNA计算中。利用DNA折纸术和杂交链式反应构建0-1背包问题的计算模型。以四个变量的0-1背包问题为例,首先将九种发夹结构和一种分子信标锚定在DNA折纸基底上并加入足量的辅助链;其次通过加入不同的引发链可以触发不同路径上的杂交链式反应,并得到问题的所有可能解;最后,通过荧光信号的数量确定可行解,从而找到问题的最优解。该模型不受权重过大或过小的影响,在折纸基底上可等比例的缩放权重。用Visual DSD软件对该模型进行仿真,模型显示出良好的可行性。
DNA origami is widely used in DNA computing by its programmability and nano-addressability.This paper used DNA origami and hybrid chain reaction to construct a model for solving the 0-1 knapsack problem.Taking the 0-1 knapsack problem with 4 variables as an example,firstly,it anchored nine hairpin structures and one molecular beacon to the DNA origami substrate and added a sufficient amount of auxiliary chains.Secondly,it added different trigger chains could trigger hybrid chain reaction on different paths so as to get all possible solutions.Finally,it used the number of fluorescent signals to find feasible and optimal solutions.The model is not affected by too large or too small weights,and can scale the weights equally on the origami substrate.The simulation is carried out by Visual DSD and the result shows that this model has good feasibility.
作者
杨新木
杨静
殷志祥
唐震
崔建中
Yang Xinmu;Yang Jing;Yin Zhixiang;Tang Zhen;Cui Jianzhong(School of Mathematics&Big Data,Anhui University of Science&Technology,Huai-nan Anhui 232001,China;School of Electrical&Information Engineering,Anhui University of Science&Technology,Huai-nan Anhui 232001,China;Faculty of Education,The University of Hong Kong,Hong Kong 999077,China;School of Mathematics,Physics&Statistics,Shanghai University of Engineering Science,Shanghai 201620,China;Dept.of Computer Science,Huainan Union University,Huainan Anhui 232001,China)
出处
《计算机应用研究》
CSCD
北大核心
2021年第3期777-781,共5页
Application Research of Computers
基金
国家自然科学基金资助项目(61702008,61672001)
安徽省博士后基金资助项目(2019B331)
安徽省自然科学基金资助项目(1808085MF193)
2019年高校优秀青年骨干人才国外访问研修项目(gxgwfx2019015)
安徽高校自然科学研究项目(KJ2019A0538)。
