DNA computing

• Autorzy: Formanowicz P.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

DNA molecules; complementarity rule; combinatorial problems; algorithms; computational complexity

• Wydawca: Institute of Bioorganic Chemistry Scientific Publishers OWN, Polish Academy of Sciences
• Czasopismo: Computational Methods in Science and Technology
• Rocznik: 2005
• Tom: Vol. 11, nr 1
• Strony: 11--20
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Formanowicz P.

• Institute of Computing Science, Poznań University of Technology Piotrowo 3A, 60-965 Poznań, Poland

Bibliografia

• [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).