Solving the Independent-set Problem in a DNA-Based Supercomputer Model
Abstract
In this paper, it is demonstrated how the DNA (DeoxyriboNucleic Acid) operations presented by Adleman and Lipton can be used to develop the parallel genetic algorithm that solves the independent-set problem. The advantage of the genetic algorithm is the huge parallelism inherent in DNA based computing. Furthermore, this work represents obvious evidence for the ability of DNA based parallel computing to solve NP-complete problems.
References
-
R. R. Sinden , DNA Structure and Function ( Academic Press , 1994 ) . Google Scholar - Science 266, 1021 (1994). Crossref, ISI, Google Scholar
- Science 268, 542 (1995). Crossref, ISI, Google Scholar
- Science 278, 446 (1997). Crossref, ISI, Google Scholar
M. Arita , A. Suyama and M. Hagiya , A heuristic approach for Hamiltonian path problem with molecules, Proceedings of 2nd Genetic Programming (GP-97) pp. 457–462. Google ScholarN. Morimoto , M. Arita and A. Suyama ,DIMACS Series in Discrete Mathematics and Theoretical Computer Science 48 (1999) pp. 93–206. Google ScholarA. Narayanan and S. Zorbala , DNA algorithms for computing shortest paths, Genetic Programming 1998: Proceedings of the Third Annual Conference, eds.J. R. Koza pp. 718–724. Google ScholarS.-Y. Shin , B.-T. Zhang and S.-S. Jun , Solving traveling salesman problems using molecular programming, Proceedings of the 1999 Congress on Evolutionary Computation (CEC99)2 (1999) pp. 994–1000. Google Scholar-
T. H. Cormen , C. E. Leiserson and R. L. Rivest , Introduction to algorithms ( ) . Google Scholar -
M. R. Garey and D. S. Johnson , Computer and intractability ( Freeman , San Fransico, CA , 1979 ) . Google Scholar D. Boneh , Discrete Applied Mathematics, Special Issue on Computational Molecular Biology 71 (1996) pp. 79–94. Google Scholar- ,
DIMACS: series in Discrete Mathematics and Theoretical Computer Science , eds.R. Lipton and E. Baum (American Mathematical Society, 1996) pp. 1–21. Google Scholar - M. Amos. "DNA Computation", Ph.D. Thesis, department of computer science, the University of Warwick, 1997 . Google Scholar
S. Roweis , A Sticker Based Model for DNA Computation,DIMACS: series in Discrete Mathematics and Theoretical Computer Science ,2nd annual workshop on DNA Computing (), eds.L. Landweber and E. Baum (Princeton University, American Mathematical Society, 1999) pp. 1–29. Google Scholar-
M. J. Perez-Jimenez and F. Sancho-Caparrini , Solving Knapsack Problems in a Sticker Based Model ,DIMACS: series in Discrete Mathematics and Theoretical Computer Science ,7th annual workshop on DNA Computing ( ) ( American Mathematical Society , 2001 ) . Google Scholar -
G. Paun , G. Rozenberg and A. Salomaa , DNA Computing: New Computing Paradigms ( Springer-Verlag , New York , 1998 ) . Crossref, Google Scholar -
W.-L. Chang and M. Guo , Solving the Dominating-set Problem in Adleman-Lipton's Model , Proceedings of Third International Conference on Parallel and Distributed Computing ( Applications and Technologies , Japan , 2002 ) . Google Scholar -
W.-L. Chang and M. Guo , Solving the Clique Problem and the Vertex Cover Problem in Adleman-Lipton's Model , Proceedings of IASTED International Conference, Networks, Parallel and Distributed Processing, and Applications . Google Scholar -
W.-L. Chang and Minyi Guo , Solving the Set Cover Problem and the Problem of Exact Cover By 3Sets in the Adleman-Lipton Model ,The Third International Conference on Unconventional Models of Computation ( 2002 ) . Google Scholar -
W.-L. Chang and M. Guo , Resolving the 3-Dimensional Matching Problem and the Set Packing Problem in Adleman-Lipton's Model , the Proceedings of IASTED International Conference, Networks, Parallel and Distributed Processing, and Applications . Google Scholar


