Solving the independent set problem by sticker based DNA computers

Hassan Taghipour, Ahad Taghipour, Mahdi Rezaei, Heydar Ali Esmaili

Department of Computer Engineering, Faculty of Engineering, Isfahan University, Isfahan, Iran.
Department of Pathology, Tabriz University of Medical Sciences, Tabriz, Iran.
Department of Theoretical Physics and Astrophysics, Tabriz University, Tabriz, Iran.

DOI: 10.4236/ajmb.2012.22017                

Abstract

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.

Keywords

Parallel Computing; Sticker Based DNA Computers; Independent Set Problem; NP-Complete Problem

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Adleman, L.M. (1994) Molecular computation of solutions to combinatorial problems. Science, 266, 1021-1024. doi:10.1126/science.7973651
[2]	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.
[3]	Lipton, R.J. (1995) DNA solution of hard computational problems. Science, 268, 542-545. doi:10.1126/science.7725098
[4]	Adleman, L.M. (1995) On constructing a molecular computer. University of Southern California, Los Angeles, 1995.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	Boneh, D., Dunworth, C. and Lipton, R. (1996) Breaking DES using a molecular computer. Technical Reports, TR-489-95, Princeton University, Princeton.
[12]	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
[13]	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.
[14]	Amos, M., Gibbons, A. and Hodgson, D. (1996) A new model of DNA computation. 12th British Colloquium on Theoretical Computer Science.
[15]	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.
[16]	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.
[17]	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
[18]	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.
[19]	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.
[20]	Rozenberg, G. and Spaink, H. (2003) DNA computing by blocking. Theoretical Computer Science, 292, 653-665. doi:10.1016/S0304-3975(01)00194-3
[21]	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.
[22]	Garey, M.R. and Johnson, D.S. (1979) Computer and intractability: A Guide to the theory of NP-completeness. Freeman, San Francisco.