Applying Surface-Based DNA Computing for Solving the Dominating Set Problem

Hassan Taghipour, Mahdi Rezaei, Heydar Ali Esmaili

Department of pathology, Tabriz University of medical sciences, Tabriz, Iran.
Department of Theoretical Physics and Astrophysics, Tabriz University, Tabriz, 51664, Iran.

DOI: 10.4236/ajmb.2012.23030                

Abstract

The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set problem. At first step, surface-based DNA solution space was constructed by using appropriate DNA strands. Then, by application of a DNA parallel algorithm, dominating set problem was resolved in polynomial time.

Keywords

Parallel Computing; Surface-Based DNA Computers; Dominating 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]	Liu, Q., et al. (1996) A surface-based approach to DNA computation, In: Proceedings of the Second Annual Meeting on DNA Based Computers, Princeton University.
[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. Manuscript, Department of Computer Science, University of Southern California.
[5]	Adleman, L.M. (1996) On Constructing a Molecular Computer. In DNA based computers, pp.1-22.
[6]	Chang,W.-L., Guo, M. (2002) Solving the dominating-set problem in Adleman–Lipton’s model. In: The Third International Conference on Parallel and Distributed Computing, Applications and Technologies, Japan, pp. 167–172.
[7]	Chang, W.-L., Guo, M. (2002) Solving the clique problem and the vertex cover problem in Adleman–Lipton’s model. In: IASTED International Conference, Networks, Parallel and Distributed Processing, and Applications, Japan, pp. 431–436.
[8]	Chang, W.-L., Guo, M. (2002) Solving NP-complete problem in the Adleman–Lipton model. In: The Proceedings of 2002 International Conference on Computer and Information Technology, Japan, pp. 157–162.
[9]	Roweis, S., et al. (1999) A sticker based model for DNA computation. In: Landweber, L., Baum, E. (Eds.), Second Annual Workshop on DNA Computing, Princeton University. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, pp. 1–29.
[10]	Perez-Jimenez, M.J., Sancho-Caparrini, F. (2001) Solving knapsack problems in a sticker based model. In: Seventh Annual Workshop on DNA Computing. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society.
[11]	Adleman, L., Rothemund, p., Roweis, S., Winfree, E. (1999) On Applying Molecular Computation to the Data Encryption Standard. The 2nd annual workshop on DNA Computing, Princeton University, DIMACS: series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, pp. 31-44.
[12]	Boneh, D., Dunworth, C., Lipton, R. (1996) Breaking DES Using a Molecular Computer. Princeton CS Tech-Report CS-TR-489-95.
[13]	Taghipour, H., Taghipour, A., Rezaei, M. and Esmaili, H. (2012) Solving the independent set problem by sticker based DNA computers. American Journal of Molecular Biology, 2, 153-158. doi:10.4236/ajmb.2012.22017
[14]	Quyang, Q., Kaplan, P. D., Liu, S., Libchaber, A. (1997) DNA solution of the maximal clique problem. Science 278, 446-449. doi:10.1126/science.278.5337.446
[15]	Amos, M., Gibbons, A., Hodgson, D. (1996) Error-resistant implementation of DNA computations. Proceedings of the 2nd DIMACS Workshop on DNA Based Computers.
[16]	Amos, M., Gibbons, A., Hodgson, D. (1996) A new model of DNA computation. 12th British Colloquium on Theoretical Computer Science.
[17]	Hagiya, M., Arita, M., Kiga, D., Sakamoto, K., Yokoyama, S. (1999) Towards Parallel Evaluation and Learning of Boolean μ-formulas with Molecules. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 48, 57-72.
[18]	Winfree, E. (1998) Simulations of Computing by Self-Assembly. Fourth International Meeting on DNA Based Computers, pp. 213-239.
[19]	Winfree, E., Liu, F.L., Wenzler, L.A., Seeman, N.C. (1998) Design and self-assembly of two-dimensional DNA crystals. Nature 394, 539-544. doi:10.1038/28998
[20]	Winfree, E., Yang, X., 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.
[21]	Rozenberg, G., Spaink, H. (2003) DNA computing by blocking. Theoretical Computer Science 292, 653-665