AJMB  Vol.2 No.3 , July 2012
Applying Surface-Based DNA Computing for Solving the Dominating Set Problem
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.

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

 
 
Top