旅行商问题的DNA可视化计算模型  

DNA visualization computational model for traveling salesman problem

作　　者：张彤彤 杨静 殷志祥 蒋天怿 郑雅雯 ZHANG Tongtong;YANG Jing;YIN Zhixiang;JIANG Tianyi;ZHENG Yawen(School of Mathematics and Big data,Anhui University of Science and Technology,Huainan 232001,China;School of Mathematics,Physics and Statistics,Shanghai University of Engineering Science,Shanghai 201620,China)

机构地区：[1]安徽理工大学数学与大数据学院,安徽淮南232001 [2]上海工程技术大学数理与统计学院,上海201620

出　　处：《哈尔滨商业大学学报（自然科学版）》2023年第6期694-701,共8页Journal of Harbin University of Commerce：Natural Sciences Edition

基　　金：国家自然科学基金(No.62272005),项目名称:DNA反应网络的理论研究与计算模型.

摘　　要：基于“DNA折纸术”提出一个旅行商问题的解决方案,利用“DNA折纸术”折叠出固定大小的DNA纳米结构作为DNA折纸基底,利用分子信标表示旅行商问题中的城市(即顶点)和路径,将旅行商问题的路径映射为一个有向图,选择根节点最终将问题映射为有向树,并将有向树锚定在DNA折纸基底上,利用杂交链式反应反应出经过每个点且长度最短的DNA长链,即为该问题的最优解,同时用荧光标记的分子信标个数检测其路径长度,实现求解旅行商问题的可视化.通过实例模拟和仿真实验验证方法的有效性和可行性,分析给出该DNA可视化计算模型的复杂度.This paper proposed a solution to the traveling salesman problem based on"DNA origami".Used"DNA origami"to fold out a fixed size DNA nanostructure as the DNA origami base,used molecular beacons to represent the cities(i.e.vertices)and paths in the traveling salesman problem,then map the path of the traveling salesman problem to a directed graph,selected the root node to finally map the problem to a directed tree,and anchor the directed tree on the DNA origami base,the shortest DNA long chain passing through each point was reflected by the hybrid chain reaction,which was the optimal solution of the problem.At the same time,the number of molecular beacons labeled with fluorescence was used to detect the path length,so as to realize the visualization of solving the traveling salesman problem.The effectiveness and feasibility of the method were verified by case simulation and simulation experiments.The complexity of the DNA visual computing model was given through analysis.

关 键 词：DNA折纸术 杂交链式反应 旅行商问题 分子信标 DNA计算 

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