DNA molecules, complementarity rule, combinatorial problems, algorithms, computational complexity
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.