Research ArticleOpen AccessGoogle Scholar indexed
Applying Surface-Based DNA Computing for Solving the Dominating Set Problem
Department of pathology, Tabriz University of medical sciences, Tabriz, Iran
Department of Theoretical Physics and Astrophysics, Tabriz University, Tabriz, 51664, Iran
Department of pathology, Tabriz University of medical sciences, Tabriz, Iran
- 1 Department of pathology, Tabriz University of medical sciences, Tabriz, Iran
- 2 Department of Theoretical Physics and Astrophysics, Tabriz University, Tabriz, 51664, Iran
- 3 Department of pathology, Tabriz University of medical sciences, Tabriz, Iran
American Journal of Molecular Biology·Volume 02 (2012)·Pages 286–290·Published 27 July 2012·DOI10.4236/ajmb.2012.23030
Copy link · social · email
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.
KeywordsParallel ComputingSurface-Based DNA ComputersDominating Set ProblemNP-Complete Problem
- Adleman, L. M. (1994) Molecular computation of solutions to combinatorial problems. Science 266, 1021-1024. doi:10.1126/science.7973651
- 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.
- Lipton, R. J. (1995) DNA solution of hard computational problems. Science 268, 542-545. doi:10.1126/science.7725098
- Adleman, L.M. (1995) On Constructing a Molecular Computer. Manuscript, Department of Computer Science, University of Southern California.
- Adleman, L.M. (1996) On Constructing a Molecular Computer. In DNA based computers, pp.1-22.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Boneh, D., Dunworth, C., Lipton, R. (1996) Breaking DES Using a Molecular Computer. Princeton CS Tech-Report CS-TR-489-95.
- 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