Molecular associative memory: An associative memory framework with exponential storage capacity for DNA computing

Associative memory problem: Find the closest stored vector (in Hamming distance) to a given query vector. There are different ways to implement an associative memory, including the neural networks and DNA strands. Using neural networks, connection weights are adjusted in order to perform association. Recall procedure is iterative and relies on simple neural operations. In this case, the design criteria is maximizing the number of stored patterns C while having some noise tolerance. The molecular implementation is based on synthesizing C DNA strands as stored vectors. Recall procedure is usually done in one shot via chemical reactions and relies on highly parallelism of DNA computing. Here, the design criteria: finding proper DNA sequences to minimize probability of error during the recall phase. Current molecular associative memories are either low in storage capacity, if implemented using molecular realizations of neural networks, or very complex to implement, if all the stored sequences have to be synthesized. We introduce an associative memory framework with exponential storage capacity based on transcriptional networks of DNA switches. The advantages of the proposed approach over current methods are: 1. Exponential storage capacities with current neural network-based approaches can not be achieved. 2. For other methods, although having exponential storage capacities is possible, it is very complex as it requires synthesizing an extraordinarily large number of DNA strands.