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

DNA visualization computational model for traveling salesman problem

基于“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.