DNA Tile Assembly for Degree-Constrained Minimum Spanning Tree
DNA Tile Assembly for Degree-Constrained Minimum Spanning Tree
复制标题
用于度约束最小生成树的 DNA 瓦片组装
DOI：
10.1166/jbns.2011.1050
复制
发表时间：
2011-06
期刊：
影响因子：
--
通讯作者：
Cui, Guangzhao
中科院分区：
文献类型：
--
作者：
Wang, Yanfeng;Lu, Weili;Bai, Xuewen;Wei, Donghui;Cui, Guangzhao
研究结果表明，利用DNA瓦片自组装模型可以合理地解决NP完全问题，该模型将信息编码在DNA瓦片中，DNA瓦片可以通过粘端关联进行自组装。本文利用DNA自组装模型求解了度为2的度约束最小生成树问题。该模型主要由两部分组成：非确定性搜索系统和加法器系统。在不确定搜索系统中，根据给定图的邻接矩阵搜索生成树的所有边。在加法器系统中，将各边的权值相加，通过比较权值的大小，得到满足度约束的最优生成树。最后，对著名旅行商问题提出了一个推广。结果表明，该方案是可行的，其运算时间复杂度为O（n）。所有这些都证明了DNA瓦片自组装解决NP完全问题的可行性。
Research results show that the reasonable solution for NP-complete problem could be achieved using DNA tile self-assembly model, in which the information is encoded in DNA tiles, which can be self-assembled via sticky-end associations. In this paper, we use the DNA self-assembly model to solve degree-constrained minimum spanning tree problem whose degree is 2. This model is mainly composed of two units: the nondeterministic search system and the adder system. In the nondeterministic search system, all the edges of a spanning tree are searched according to the adjacency matrix of the given graph. In the adder system, the weights of edges are added up, thus the optimal spanning tree which meets the constraint of degree will be gained by comparing the values of weights. Finally, we put forward a promotion for solving the well-known traveling salesman problem. Results shows that the solution is feasible with the operational time complexity of O(n). All of these demonstrate the feasibility of DNA tiles self-assembly for NP-complete problems.