Share This Article:

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

Abstract Full-Text HTML XML Download Download as PDF (Size:338KB) PP. 286-290
DOI: 10.4236/ajmb.2012.23030    4,433 Downloads   8,182 Views   Citations

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.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

Taghipour, H. , Rezaei, M. and Esmaili, H. (2012) Applying Surface-Based DNA Computing for Solving the Dominating Set Problem. American Journal of Molecular Biology, 2, 286-290. doi: 10.4236/ajmb.2012.23030.

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

  
comments powered by Disqus

Copyright © 2019 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.