Research ArticleOpen AccessGoogle Scholar indexed
Solving the independent set problem by sticker based DNA computers
Department of Pathology, Tabriz University of Medical Sciences, Tabriz, Iran
Department of Computer Engineering, Faculty of Engineering, Isfahan University, Isfahan, Iran
Department of Theoretical Physics and Astrophysics, Tabriz University, Tabriz, 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 Computer Engineering, Faculty of Engineering, Isfahan University, Isfahan, Iran
- 3 Department of Theoretical Physics and Astrophysics, Tabriz University, Tabriz, Iran
- 4 Department of Pathology, Tabriz University of Medical Sciences, Tabriz, Iran
American Journal of Molecular Biology·Volume 02 (2012)·Pages 153–158·Published 28 April 2012·DOI10.4236/ajmb.2012.22017
Copy link · social · email
Abstract
In this paper, the sticker based DNA computing was used for solving the independent set problem. At first, solution space was constructed by using appropriate DNA memory complexes. We defined a new operation called “divide” and applied it in construction of solution space. Then, by application of a sticker based parallel algorithm using biological operations, independent set problem was resolved in polynomial time.
KeywordsParallel ComputingSticker Based DNA ComputersIndependent Set ProblemNP-Complete Problem
- Adleman, L.M. (1994) Molecular computation of solutions to combinatorial problems. Science, 266, 1021-1024. doi:10.1126/science.7973651
- Roweis, S., et al. (1999) A sticker based model for DNA computation. In: Landweber, L. and Baum, E., Eds., The 2nd Annual Workshop on DNA Computing, Princeton University, Series in Discrete Mathematics and Theoretical Computer Science, DIMACS, American Mathematical Society, 1-29.
- 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. University of Southern California, Los Angeles, 1995.
- Adleman, L.M. (1996) On constructing a molecular computer. In: Lipton, R.J. and Baum E.B., Eds., DNA Based Computers, American Mathematical Society, 1-22.
- Chang, W.-L., Guo, M. (2002) Solving the dominating-set problem in Adleman—Lipton’s model. The 3rd International Conference on Parallel and Distributed Computing, Applications and Technologies, Japan, 2-4 July 2003, 167-172.
- Chang, W.-L. and Guo, M. (2002) Solving the clique problem and the vertex cover problem in Adleman— Lipton’s model. IASTED International Conference, Networks, Parallel and Distributed Processing, and Applications, Japan, 2-4 July 2003, 431-436.
- Chang, W.-L. and Guo, M. (2002) Solving NP-complete problem in the Adleman—Lipton model. The Proceedings of 2002 International Conference on Computer and Information Technology, Japan, 157-162.
- Perez-Jimenez, M.J. and Sancho-Caparrini, F. (2001) Solving knapsack problems in a sticker based model. Series in Discrete Mathematics and Theoretical Computer Science, Seventh Annual Workshop on DNA Computing, Princeton University, Series in Discrete Mathematics and Theoretical Computer Science, DIMACS, American Mathematical Society.
- Adleman, L., Rothemund, P., Roweis, S. and Winfree E. (1999) On applying molecular computation to the data encryption standard. The 2nd Annual Workshop on DNA Computing, Princeton University, Series in Discrete Mathematics and Theoretical Computer Science, DIMACS, American Mathematical Society, 31-44.
- Boneh, D., Dunworth, C. and Lipton, R. (1996) Breaking DES using a molecular computer. Technical Reports, TR-489-95, Princeton University, Princeton.
- Quyang, Q., Kaplan, P.D., Liu, S. and Libchaber, A. (1997) DNA solution of the maximal clique problem. Science, 278, 446-449. doi:10.1126/science.278.5337.446