自從實驗證明DNA運算的可行性，它已經被廣泛應用在決策與組合性最佳化問題。證明圖形同構問題是否屬於NP問題被認為是棘手的事，儘管可能不是屬於NP-Complete問題。在這篇論文中，我們利用這個運算模型有效率解決圖形同構問題來展示DNA運算的強大。使用stickers產生解法空間以及線性的基本生物運算，我們可以得到DNA演算法來解決這個問題。

Since the experimental demonstration of its feasibility, DNA-based computing has been applied to a number of decision or combinatorial optimization problems. The graph isomorphism problem belongs to the class of NP problems, and has been conjectured intractable, although probably not NP-complete. In this paper, we demonstrate the power of DNA-based computing by showing the graph isomorphism problem can be efficiently solved under this computation model. By generating the solution space using stickers, we present DNA-based algorithms to solve the problem using polynomial number of basic biological operations.

[1] L. M. Adleman, "Molecular computation of solutions to combinatorial problems," Science,
266:1021-1024, 1994.
[2] R. S. Braich, C. Johnson, P. W. K. Rothemund, D. Hwang, N. Chelyapov, M. Leonard,
and L. M. Adleman, "Solution of a satis¯ability problem on a gel-based DNA computer,"
in Proceedings of the Sixth International Conference on DNA Computation (DNA 2000),
Lecture Notes in Computer Science 2054, pp. 27-42, 2001.
[3] Weng-Long Chang and Minyi Guo, "Solving the dominating-set problem in Adleman-
Lipton's model," in Proceedings of the Third International Conference on Parallel and
Distributed Computing, Applications and Technologies, pp. 167-172, 2002.
[4] Weng-Long Chang and Minyi Guo, "Solving the clique problem and the vertex cover prob-
lem in Adleman-Lipton's model," in Proceedings of IASTED International Conference,
Networks, Parallel and Distributed Processing, and Applications, pp. 431-436, 2002.
[5] Weng-Long Chang and Minyi Guo, "Solving NP-complete problem in the Adleman-Lipton
model," in Proceedings of 2002 International Conference on Computer and Information
Technology, pp. 157-162, 2002.
[6] Weng-Long Chang and Minyi Guo, "Resolving the 3-dimensional matching problem and the
set-packing problem in Adleman-Liptons model," in Proceedings of IASTED International
Conference, Networks, Parallel and Distributed Processing, and Applications, pp. 455-460,
2002.
[7] Weng-Long Chang and Minyi Guo, "Solving the set cover problem and the problem of
exact 3 cover by 3-sets in the Adleman-Lipton model," Biosystems, 72(3):263-275, 2003.
[8] Weng-Long Chang, Minyi Guo, and Michael (Shan-Hui) Ho, "Solving the set-splitting prob-
lem in sticker-based model and the AdlemanVLipton model," Future Generation Computer
Systems, 20(5):875-885, 2004.
[9] Weng-Long Chang, Minyi Guo, and Michael (Shan-Hui) Ho, "Molecular solutions for the
subset-sum problem on DNA-based supercomputing," Biosystems, 73(2):117-130, 2004.
[10] Weng-Long Chang, Minyi Guo, and Michael (Shan-Hui) Ho, "Fast parallel molecular algo-
rithms for DNA-based computation: factoring integers," IEEE Transactions on Nanobio-
science, 4(2): 149-163, 2005.
[11] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms
(Second Eition), MIT Press, Cambridge, 2001.
[12] D. Faullhammer, A. R. Cukras, R. J. Lipton, and L. F. Landweber, "Molecular compu-
tation: RNA solutions to chess problems," in Proceedings of National Academica Science
U.S.A. 97, pp. 1385-1389, 2000.
[13] R. P. Feynman, In Minaturization, D. H. Gilbert, Ed. New York: Reinhold, 1961, pp.
282-296.
[14] S. D. Gillmor, P. P. Rugheimer, and M. G. Lagally, "Computing with DNA on surfaces,"
Surface Science, 500:699-721, 2002.
[15] F. Guarnieri, M. Fliss, and C. Bancroft, "Making DNA add," Science, 273:220-223, 1996.
[16] Minyi Guo, Michael (Shan-Hui) Ho, and Weng-Long Chang, "Fast parallel molecular so-
lution to the dominating-set problem on massively parallel bio-computing," Parallel Com-
puting, 30: 1109-1125, 2004.
[17] Minyi Guo, Weng-Long Chang, Machael (Shan-Hui) Ho, Jian Lu, and Jiannong Cao, "Is
optimal solution of every NP-complete or NP-hard problem determined from its character-
istic for DNA-based computing," Biosystems, 80(1): 71-82, 2005.
[18] R. J. Lipton, "DNA solution of hard computational problems," Science, 268:542-545, 1995.
[19] Q. Liu, L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn, and L. M. Smith, "DNA
computing on surfaces," Nature, 403:175-179, 2000.
[20] A. Narayanan and S. Zorbala, "DNA algorithms for computing shortest paths," In: Koza,
J.R., et al. (Eds.), Proceedings of the Third Annual Conference on Genetic Programming,
pp. 718-724, 1998.
[21] Q. Ouyang, P. D. Kaplan, S. Liu, and A. Libchaber, "DNA solution of the maximal clique
problem," Science, 278:446-449, 1997.
[22] G. P·aun, G. Rozenberg, and A. Salomaa, DNA Computing: New Computing Paradigms,
Springer-Verlag, Berlin, pp. 117-149, 1998.
[23] C. H. Papadimitrious, Computational Complexity, Addison-Wesley, Reading, 1994.
[24] S. Roweis, E. Winfree, R. Burgoyne, N. V. Chelyapov, M. F. Goodman, P. W. K. Rothe-
mund, and L. M. Adleman, "A sticker based model for DNA computation," in Proceedings
of the Second Annual Worksop on DNA Computing, DIMACS: Series in Discrete Mathe-
matics and Theoretical Computer Science, American Mathematical Society, pp. 1-29.
[25] K. Sakamoto, H. Gouzu, K. Komiya, D. Kiga, S. Yokoyama, T. Yokomori, and M. Hagiya,
"Molecular computation by DNA hairpin formation," Science, 288:1223-1226, 2000.
[26] R. R. Sinden, DNA Structure and Function, Academic Press., 1994.