DNA computing appeared in the literature in 1994 when Leonard Adleman suggested to solve an NP-complete problem by using DNA molecules. Since one can store a large amount of molecules in a small volume, and since it is possible to apply operations to all of them in parallel, the result is a surprisingly interesting performance of DNA computations. In recent years, possible computationally complete models that might be implemented in a molecular biology laboratory have been suggested. Experiments are being performed in order to test the feasibility of DNA computations by using such models. We will report on some of the ideas, discussions, and results that have appeared in the literature so far, and we will stress some new issues in DNA computing that suggest a revisitation of complexity theory.
DNA computing: a new computational paradigm using molecules
PISANTI, NADIA
1999-01-01
Abstract
DNA computing appeared in the literature in 1994 when Leonard Adleman suggested to solve an NP-complete problem by using DNA molecules. Since one can store a large amount of molecules in a small volume, and since it is possible to apply operations to all of them in parallel, the result is a surprisingly interesting performance of DNA computations. In recent years, possible computationally complete models that might be implemented in a molecular biology laboratory have been suggested. Experiments are being performed in order to test the feasibility of DNA computations by using such models. We will report on some of the ideas, discussions, and results that have appeared in the literature so far, and we will stress some new issues in DNA computing that suggest a revisitation of complexity theory.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
