DNA 3D Self-assembly Algorithmic Model to Solve Maximum Clique Problem
Автор: Jingjing Ma, Li Jia, Yafei Dong
Журнал: International Journal of Image, Graphics and Signal Processing(IJIGSP) @ijigsp
Статья в выпуске: 3 vol.3, 2011 года.
Бесплатный доступ
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.
DNA self-assembly, DNA computing, Maximum Clique Problem, 3D
Короткий адрес: https://sciup.org/15012140
IDR: 15012140
Список литературы DNA 3D Self-assembly Algorithmic Model to Solve Maximum Clique Problem
- Takahashi K, et al. "Photo-and Thermoregulation of DNA Nanomachines”. In 11th Int. Mtg on DNA computing, 147-156, 2005.
- Erik winfree. “On the computational power of DNA annealing and ligation”. In Lipton and Baum 1996, pages 199-221
- Adleman LM. “Molecular computation of solutions to combinatorial problems”. Science 1994;266:1021–4.
- Wang H. “Proving theorems by pattern recognition I”. Bell Syst Tech J 1961;40:1–42.
- Wang, H. “Dominoes and the AEA case of the decision problem”. In Mathematica Theory of Automata (ed. J. Fox). Polytechnic Press, New York. 1963.
- Paul Rothemund, “Scaffolded DNA origami: From generalized multicrossovers to polygonal networks”. Nanotechnology: Science and Computation 2006 pp3–21.
- Leonard M. Adleman. “Towards a mathematical theory of self-assembly”. Technical Report, Department of Computer Science, University of Southern California, 2000.
- Leonard M．Adleman，et al. “Linear Self-Assemblies：Equilibria，Entropy and Convergence Rates”，2000.
- Paul Rothemund and ErikWinfree. “The program-size complexity of self-assembled squares”. STOC 2000.
- Erik Winfree, Xiaoping Yang, and Nadrian C. Seeman. Universal computation via self-assembly of DNA: Some theory and experiments. In Landweber and Lipton.
- M. Kao and V. Ramachandran “DNA Self-Assembly For Constructing 3D Boxes” Lecture Notes in Computer Science, Springer Berlin, Heidelberg, 2001, pp. 429-441.
- 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.
- 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
- Guangzhao Cui, et al. “ Application of DNA Self-assembly on Maximum Clique Problem” Advances in Soft Computing,2009,Volume 116/359-368,2009.
