In this paper, the sticker based DNA computing was used for solving the independent set problem. At first, solution space was constructed by using appropriate DNA memory complexes. We defined a new operation called “divide” and applied it in construction of solution space. Then, by application of a sticker based parallel algorithm using biological operations, independent set problem was resolved in polynomial time.

Roweis, S., et al. (1999) A sticker based model for DNA computation. In: Landweber, L. and Baum, E., Eds., The 2nd Annual Workshop on DNA Computing, Princeton University, Series in Discrete Mathematics and Theoretical Computer Science, DIMACS, American Mathematical Society, 1-29.

Adleman, L.M. (1996) On constructing a molecular computer. In: Lipton, R.J. and Baum E.B., Eds., DNA Based Computers, American Mathematical Society, 1-22.

Chang, W.-L., Guo, M. (2002) Solving the dominating-set problem in Adleman—Lipton’s model. The 3rd International Conference on Parallel and Distributed Computing, Applications and Technologies, Japan, 2-4 July 2003, 167-172.

Chang, W.-L. and Guo, M. (2002) Solving the clique problem and the vertex cover problem in Adleman— Lipton’s model. IASTED International Conference, Networks, Parallel and Distributed Processing, and Applications, Japan, 2-4 July 2003, 431-436.

Chang, W.-L. and Guo, M. (2002) Solving NP-complete problem in the Adleman—Lipton model. The Proceedings of 2002 International Conference on Computer and Information Technology, Japan, 157-162.

Perez-Jimenez, M.J. and Sancho-Caparrini, F. (2001) Solving knapsack problems in a sticker based model. Series in Discrete Mathematics and Theoretical Computer Science, Seventh Annual Workshop on DNA Computing, Princeton University, Series in Discrete Mathematics and Theoretical Computer Science, DIMACS, American Mathematical Society.

Adleman, L., Rothemund, P., Roweis, S. and Winfree E. (1999) On applying molecular computation to the data encryption standard. The 2nd Annual Workshop on DNA Computing, Princeton University, Series in Discrete Mathematics and Theoretical Computer Science, DIMACS, American Mathematical Society, 31-44.

Quyang, Q., Kaplan, P.D., Liu, S. and Libchaber, A. (1997) DNA solution of the maximal clique problem. Science, 278, 446-449. doi:10.1126/science.278.5337.446

Amos, M., Gibbons, A. and Hodgson, D. (1996) Error-resistant implementation of DNA computations. Proceedings of the 2nd DIMACS Workshop on DNA Based Computers, 87-101.

Hagiya, M., Arita, M., Kiga, D., Sakamoto, K. and Yokoyama, S. (1999) Towards parallel evaluation and learning of boolean μ-formulas with molecules. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, Proceedings of 3rd Annual Meeting on DNA Based Computers, 48, 105-114.

Winfree, E. (1998) Simulations of computing by selfassembly. In: Winfree, E. and Gifford, D.K., Eds., 4th International Meeting on DNA Based Computers, Massachusetts Institute of Technology, Cambridge, 213-239.

Winfree, E., Liu, F.L., Wenzler, L.A. and Seeman, N.C. (1998) Design and self-assembly of two-dimensional DNA crystals. Nature, 394, 539-544. doi:10.1038/28998

Winfree, E., Yang, X. and Seeman, N.C. (1996) Universal computation via self-assembly of DNA: Some theory and experiments. Proceedings of the 2nd DIMACS Workshop on DNA Based Computers, 44, 191-213.

Liu, Q., et al. (1996) A surface-based approach to DNA computation, Proceedings of the 2nd Annual Meeting on DNA Based Computers, Princeton University, Princeton, 10-12 June 1996.

Schmidt, K., Henkel, C., Rozenberg, G. and Spaink, H. (2001) Experimental aspects of DNA computing by blocking: Use of fluorescence techniques for detection. In: Kraayenhof, R., Visser, A.J.W.G. and Gerritsen, H.C., Eds., Fluorescence Spectroscopy, Imaging and Probes. Springer-Verlag, Berlin.