Book of Abstracts: Albany 2003
June 17-21 2003
Parallel Molecular Computation of Pair-wise XOR using DNA ?String Tile? Self-Assembly
Recently, several proposed models for DNA computing have been experimentally demonstrated. The massive parallelism inherent in DNA-based computers has driven thinking in this field. Computation by self-assembly of DNA is an efficient method of executing parallel DNA computing. A logical computation using algorithmic self-assembly of DNA tiles has recently been demonstrated (1) for fixed inputs. Here we report a multi-bit parallel computation of pair-wise XOR using self-assembly of DNA double crossover molecules (DX) (2) based on the ?string tile? model proposed by Winfree et al (3). A set of DX tiles encoding the truth table for XOR was constructed. Parallel self-assembly and ligation of the tiles led to reporter strands containing both input and output information, which was decoded by sequencing the reporter strands. The resultant set of reporter strands represents a molecular look-up table containing all possible pair-wise XOR calculations up to a certain size input string. As far as we know, this is the first experimental demonstration of a truly parallel computation by DNA self-assembly in which a large number of distinct inputs are simultaneously processed.
This work has been supported by grants from NSF (EIA-00-86015, EIA-0218376, EIA-0218359) and DARPA/AFSOR (F30602-01-2-0561).
Department of Computer Science