DNA -based storage and retrieval of digital signals

Using DNA to store digital information offers significant advantages when compared to other media. The DNA molecule, especially in its double stranded form, is very stable, compact, and inexpensive. Querying the database can be implemented with a plethora of techniques. Given a query molecule, DNA annealing provides a very efficient way to search for similar molecules in the database, when compared to doing searches in a digital database. In digital databases query time increases proportionally with the size of the database. However, in DNA databases with annealing as a search mechanism, query time is independent of the size of the database.;Motivated by the above, we propose DNA-based storage and retrieval of digital signals. We consider two different forms; one for short-term storage and one for long-term storage. For short-term storage the database is kept in test tubes or other materials while for long-term storage the database is inserted inside an organism. We analyze and compare each and propose a laboratory method for converting between database forms.;We use annealing to perform associative searches. To perform searches based on signal similarity we introduce and utilize the Noise Tolerance Constraint. We present a stochastic local search algorithm to solve the codeword design problem. In addition we derive bounds on the length of the codewords.;In place of experimental verification we offer computer simulations of querying DNA databases. We present an elaborate framework to simulate single query and parallel query situations. Our framework allows for numerical solutions as well as approximations under certain conditions. With approximations, we show that the signal to noise ratio of a DNA database is upper bounded by the signal to noise ratio of an infinitely large DNA database that has the same source distribution. We also show that microarray technology can be used to estimate the source statistics of an 'unknown' DNA database.;Finally, we consider the problem of universal microarray design. We present a novel construction of reporter molecules that eliminates a number of disadvantages of previously proposed designs and identify the necessary constraints for the underlying word design problem.