International Journal of Image, Graphics and Signal Processing (IJIGSP)
IJIGSP Vol. 3, No. 3, 8 Apr. 2011
Cover page and Table of Contents: PDF (size: 840KB)
DNA 3D Self-assembly Algorithmic Model to Solve Maximum Clique Problem
Full Text (PDF, 840KB), PP.41-48
Views: 0 Downloads: 0
Author(s)
Jingjing Ma
1,*
Li Jia
1
Yafei Dong
1
Index Terms
DNA self-assembly, DNA computing, Maximum Clique Problem，3D
Abstract
Self-assembly reveals the essence of DNA computing, DNA self-assembly is thought to be the best way to make DNA computing transform into computer chip. This paper introduce a method of DNA 3D self-assembly algorithm to solve the Maximum Clique Problem. Firstly, we introduce a non-deterministic algorithm. Then, according to the algorithm we design the types of DNA tiles which the computation needs. Lastly, we demonstrate the self-assembly process and the experimental methods which could get the final result. The computation time is linear, and the number of the distinctive tile types is constant.
Cite This Paper
Jingjing Ma,Li Jia,Yafei Dong,"DNA 3D Self-assembly Algorithmic Model to Solve Maximum Clique Problem", IJIGSP, vol.3, no.3, pp.41-48, 2011. DOI: 10.5815/ijigsp.2011.03.06
Reference
[1]Takahashi K, et al. "Photo-and Thermoregulation of DNA Nanomachines”. In 11th Int. Mtg on DNA computing, 147-156, 2005.
[2]Erik winfree. “On the computational power of DNA annealing and ligation”. In Lipton and Baum 1996, pages 199-221
[3]Adleman LM. “Molecular computation of solutions to combinatorial problems”. Science 1994;266:1021–4.
[4]Wang H. “Proving theorems by pattern recognition I”. Bell Syst Tech J 1961;40:1–42.
[5]Wang, H. “Dominoes and the AEA case of the decision problem”. In Mathematica Theory of Automata (ed. J. Fox). Polytechnic Press, New York. 1963.
[6]Paul Rothemund, “Scaffolded DNA origami: From generalized multicrossovers to polygonal networks”. Nanotechnology: Science and Computation 2006 pp3–21.
[7]Leonard M. Adleman. “Towards a mathematical theory of self-assembly”. Technical Report, Department of Computer Science, University of Southern California, 2000.
[8]Leonard M．Adleman，et al. “Linear Self-Assemblies：Equilibria，Entropy and Convergence Rates”，2000.
[9]Paul Rothemund and ErikWinfree. “The program-size complexity of self-assembled squares”. STOC 2000.
[10]Erik Winfree, Xiaoping Yang, and Nadrian C. Seeman. Universal computation via self-assembly of DNA: Some theory and experiments. In Landweber and Lipton.
[11]M. Kao and V. Ramachandran “DNA Self-Assembly For Constructing 3D Boxes” Lecture Notes in Computer Science, Springer Berlin, Heidelberg, 2001, pp. 429-441.
[12]Essam Al-Daoud, Belal Zaqaibeh and Feras Al-Hanandeh “3D DNA Nanostructures for Vector Multiplication”, American Journal of Scientific Research ISSN 1450-223X Issue 1,2009.
[13]Lin Minqi, Xu Jin, et al “3D DNA Self-Assembly Model for Graph Vertex Coloring” Journal of Computational and Theoretical Nanoscience Vol.7 No.1246-253,2010
[14]Guangzhao Cui, et al. “ Application of DNA Self-assembly on Maximum Clique Problem” Advances in Soft Computing,2009,Volume 116/359-368,2009.