DNA computing
Institute of Computing Science, Poznań University of Technology
Piotrowo 3A, 60-965 Poznań, Poland
Institute of Bioorganic Chemistry, Polish Academy of Sciences
Noskowskiego 12/14, 61-704 Poznań, Poland
Received:
Rec. 20 May 2004
DOI: 10.12921/cmst.2005.11.01.11-20
OAI: oai:lib.psnc.pl:577
Abstract:
DNA computing is an alternative method of performing computations. It is based on the observation that in general it is possible to design a series of biochemical experiments involving DNA molecules which is equivalent to processing information encoded in these molecules. In classical computing devices electronic logic gates are elements which allow for storing and transforming information. Designing of an appropriate sequence or a net of “store” and “transform” operations (in a sense of building a device or writing a program) is equivalent to preparing some computations. In DNA computing the situation is analogous. The main difference is the type of computing devices, since in this new method of computing instead of electronic gates DNA molecules are used for storing and transforming information. From this follows that the set of basic operations is different in comparison to electronic devices but the results of using them may be similar. Moreover, the inherent massive parallelism of DNA computing may lead to methods solving some intractable computational problems. In this paper basic principles of DNA computing are described and examples of DNA based algorithms solving some combinatorial problems are presented.
Key words:
algorithms, combinatorial problems, complementarity rule, computational complexity, DNA molecules
References:
[1] L. Adleman, Molecular computations of solutions to combinatorial problems, Science 266, 1021-1024 (1994).
[2] J. Błażewicz, K. H. Ecker, E. Pesch, G. Schmidt and J. Węglarz, Scheduling Computer and Manufacturing Processes, Springer-Verlag, Berlin 1996.
[3] J. Błażewicz, P. Formanowicz, and R. Urbaniak, DNA Based Algorithms for Some Scheduling Problems, Lecture Notes in Computer Science 2611, 673-683 (2003).
[4] P. Formanowicz, Selected deterministic scheduling problems with limited machine availability, Pro Dialog, 13, 91- 105 (2001).
[5] M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness W. H. Freeman and Company, San Francisco 1979.
[6] C.-Y. Lee, Machine scheduling with an availability constraint, Journal of Global Optimization, 9, 395-416 (1996).
[7] L. F. Landweber, E. B. Baum (eds.), DNA Based Computers II, American Mathematical Society, 1999.
[8] R. J. Lipton, DNA solution of hard computational problems, Science 268, 542-545 (1995).
[9] R. J. Lipton, E. B. Baum (eds.), DNA Based Computers, American Mathematical Society, 1996.
[10] A. Marathe, A. E. Condon and R. M. Corn, On combinatorial DNA word design, Journal of Computational Biology, 8, 201-219 (2001).
[11] Q. Ouyang, P. D. Kaplan, S. Liu and A. Libchaber, DNA solution of the maximal clique problem, Science, 278, 446-449 (1997).
[12] G. Păun, G. Rozenberg and A. Salomaa, DNA Computing. New Computing Paradigms, Springer-Verlag, Berlin 1998.
[13] M. Pinedo and Scheduling, Theory, Algorithms, and Systems, Prentice Hall, Englewood Cliffs, New Jersey 1995.
[14] S. Roweis and E. Winfree, On the reduction of errors in DNA computation, Journal of Computational Biology, 6, 65-75 (1999).
[15] S. Roweis, E. Winfree, R. Burgoyne, N. V. Chelyapov, M. F. Goodman, P. W. K. Rothemund and L. M. Adleman, A sticker-based model for DNA computation, Journal of Computational Biology, 5, 615-629 (1998).
[16] J. D. Watson and F. H. C. Crick, A structure of deoxiribose nucleic acid, Nature, 171, 737-738 (1953).
DNA computing is an alternative method of performing computations. It is based on the observation that in general it is possible to design a series of biochemical experiments involving DNA molecules which is equivalent to processing information encoded in these molecules. In classical computing devices electronic logic gates are elements which allow for storing and transforming information. Designing of an appropriate sequence or a net of “store” and “transform” operations (in a sense of building a device or writing a program) is equivalent to preparing some computations. In DNA computing the situation is analogous. The main difference is the type of computing devices, since in this new method of computing instead of electronic gates DNA molecules are used for storing and transforming information. From this follows that the set of basic operations is different in comparison to electronic devices but the results of using them may be similar. Moreover, the inherent massive parallelism of DNA computing may lead to methods solving some intractable computational problems. In this paper basic principles of DNA computing are described and examples of DNA based algorithms solving some combinatorial problems are presented.
Key words:
algorithms, combinatorial problems, complementarity rule, computational complexity, DNA molecules
References:
[1] L. Adleman, Molecular computations of solutions to combinatorial problems, Science 266, 1021-1024 (1994).
[2] J. Błażewicz, K. H. Ecker, E. Pesch, G. Schmidt and J. Węglarz, Scheduling Computer and Manufacturing Processes, Springer-Verlag, Berlin 1996.
[3] J. Błażewicz, P. Formanowicz, and R. Urbaniak, DNA Based Algorithms for Some Scheduling Problems, Lecture Notes in Computer Science 2611, 673-683 (2003).
[4] P. Formanowicz, Selected deterministic scheduling problems with limited machine availability, Pro Dialog, 13, 91- 105 (2001).
[5] M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness W. H. Freeman and Company, San Francisco 1979.
[6] C.-Y. Lee, Machine scheduling with an availability constraint, Journal of Global Optimization, 9, 395-416 (1996).
[7] L. F. Landweber, E. B. Baum (eds.), DNA Based Computers II, American Mathematical Society, 1999.
[8] R. J. Lipton, DNA solution of hard computational problems, Science 268, 542-545 (1995).
[9] R. J. Lipton, E. B. Baum (eds.), DNA Based Computers, American Mathematical Society, 1996.
[10] A. Marathe, A. E. Condon and R. M. Corn, On combinatorial DNA word design, Journal of Computational Biology, 8, 201-219 (2001).
[11] Q. Ouyang, P. D. Kaplan, S. Liu and A. Libchaber, DNA solution of the maximal clique problem, Science, 278, 446-449 (1997).
[12] G. Păun, G. Rozenberg and A. Salomaa, DNA Computing. New Computing Paradigms, Springer-Verlag, Berlin 1998.
[13] M. Pinedo and Scheduling, Theory, Algorithms, and Systems, Prentice Hall, Englewood Cliffs, New Jersey 1995.
[14] S. Roweis and E. Winfree, On the reduction of errors in DNA computation, Journal of Computational Biology, 6, 65-75 (1999).
[15] S. Roweis, E. Winfree, R. Burgoyne, N. V. Chelyapov, M. F. Goodman, P. W. K. Rothemund and L. M. Adleman, A sticker-based model for DNA computation, Journal of Computational Biology, 5, 615-629 (1998).
[16] J. D. Watson and F. H. C. Crick, A structure of deoxiribose nucleic acid, Nature, 171, 737-738 (1953).
