World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Solving the Independent-set Problem in a DNA-Based Supercomputer Model

    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
    • L. Adleman, Science 266, 1021 (1994). Crossref, ISIGoogle Scholar
    • R. J. Lipton, Science 268, 542 (1995). Crossref, ISIGoogle Scholar
    • Q. Ouyanget al., Science 278, 446 (1997). Crossref, ISIGoogle 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 Scholar
    • N. Morimoto, M. Arita and A. Suyama, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 48 (1999) pp. 93–206. Google Scholar
    • A. Narayanan and S. Zorbala, DNA algorithms for computing shortest paths, Genetic Programming 1998: Proceedings of the Third Annual Conference, eds. J. R. Kozaet al. pp. 718–724. Google Scholar
    • S.-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. Bonehet al., Discrete Applied Mathematics, Special Issue on Computational Molecular Biology 71 (1996) pp. 79–94. Google Scholar
    • L. M. Adleman, 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. Roweiset al., 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 ) . CrossrefGoogle 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