Abstract
The minimum spanning tree (MST) problem has been widely studied for its wide applicationsin recent years. Because of its outstanding advantages, DNA self-assembly computing has been used to solve MST problem. A new paradigm, called a three dimensional (3D) DNA self-assembly model, is proposed for this type of problem in this paper. The results show that it is efficient in solving MST problem and the algorithm has a high-efficiency.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Păun, G.: Membrane computing: an introduction, Springer-verlan (2002)
Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 266, 1021–1024 (1994)
Song, T., Pan, L., Wang, J., Ibrahim, V., Subramanian, K.G., Rosni, A.: Normal Forms of Spiking Neural P Systems with Anti-Spikes. IEEE Trans. on Nanobioscience 11(4), 352–359 (2012)
Song, T., Zheng, H., He, J.: Solving Vertex Cover Problem by Tissue P Systems with Cell Division. Appl. Math. Inf. Sci. 8(1), 333–337 (2014)
Martın-Vide, C., Păun, G., Pazos, J., Rodrıguez-Patón, A.: Tissue P Systems, Theore. Comput. Sci. 296(2), 295–326 (2003)
Wang, H.: Proving theorems by pattern recognition. Bell Systs. Tech. J. 40, 1–41 (1961)
Winfree, E.: Algorithmic self-assembly of DNA. California Institute of Technology, California (1998)
Zhang, X., Niu, Y., Cui, G., Xu, J.: Application of DNA Self-Assembly on Graph Coloring Problem. J. Comput. Theor. Nanosci. 6, 1–8 (2009)
Zhang, X., Niu, Y., Cui, G., Xu, J.: Application of DNA Self-Assembly on 0-1 Integer Programming Problem. J. Comput. Theor. Nanosci. 7, 1–8 (2010)
Wang, Y., Hu, P., Cui, G.: DNA Self-Assembly for Graph Vertex 3-Coloring Problem. J. Comput. Theor. Nanosci. 7, 29–38 (2010)
Wang, Y., Bai, X., Wei, D., Cui, G.: DNA Self-Assembly for Maximum Weighted Independent Set Problem. Advanced Science Letters 5, 1–6 (2012)
Song, T., Pan, L., Păun, G.: Asynchronous Spiking Neural P Systems with Local Synchronization. Information Sciences 219, 197–207 (2013)
Crocker, J.: Golden Handshake. Nature 451, 528–529 (2008)
Song, T., Wang, X., Zhang, Z., Hong, L.: Detecting Motifs in DNA Sequences by Branching from Neighbors of Qualified Potential Motifs. J. Comput. Theor. Nanosci. 10, 2201–2206 (2013)
Jonoska, N., Karl, S., Saito, M.: Three Dimensional DNA Structures in Computing. BioSystems 52, 143–153 (1999)
Zhang, X., Song, W., Fan, R., Cui, G.: Three Dimensional DNA Self-Assembly Model for the Minimum Vertex Cover Problem. In: Procecedings of the 4th International Symposium on Computational Intelligence and Design (2011)
Lin, M.Q., Xu, J.: 3D DNA Self-Assembly Model for Graph Vertex Coloring. J. Comput. Theor. Nanosci. 7, 1246–1253 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, Z., Bian, L., Wang, Y., Cui, G. (2014). A 3D DNA Self-assembly Model and Algorithm for Minimum Spanning Tree Problem. In: Pan, L., Păun, G., Pérez-Jiménez, M.J., Song, T. (eds) Bio-Inspired Computing - Theories and Applications. Communications in Computer and Information Science, vol 472. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45049-9_74
Download citation
DOI: https://doi.org/10.1007/978-3-662-45049-9_74
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-45048-2
Online ISBN: 978-3-662-45049-9
eBook Packages: Computer ScienceComputer Science (R0)