Scientific Research

An Academic Publisher

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

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

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.

[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 |

Copyright © 2019 by authors and Scientific Research Publishing Inc.

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