DNA Tile Assembly for Degree-Constrained Minimum Spanning Tree
Abstract: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.
Document Type: Research Article
Publication date: 2011-06-01
More about this publication?
- Bionanoscience attempts to harness various functions of biological macromolecules and integrate them with engineering for technological applications. It is based on a bottom-up approach and encompasses structural biology, biomacromolecular engineering, material science, and engineering, extending the horizon of material science. The journal aims at publication of (i) Letters (ii) Reviews (3) Concepts (4) Rapid communications (5) Research papers (6) Book reviews (7) Conference announcements in the interface between chemistry, physics, biology, material science, and technology. The use of biological macromolecules as sensors, biomaterials, information storage devices, biomolecular arrays, molecular machines is significantly increasing. The traditional disciplines of chemistry, physics, and biology are overlapping and coalescing with nanoscale science and technology. Currently research in this area is scattered in different journals and this journal seeks to bring them under a single umbrella to ensure highest quality peer-reviewed research for rapid dissemination in areas that are in the forefront of science and technology which is witnessing phenomenal and accelerated growth.
- Editorial Board
- Information for Authors
- Subscribe to this Title
- Ingenta Connect is not responsible for the content or availability of external websites