Book of Abstracts: Albany 2003

category image Albany 2003
Conversation 13
Abstract Book
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).

Hao Yan
Liping Feng
Thomas H. LaBean
John H. Reif

Department of Computer Science
Duke University
Durham, NC 27708

References and Footnotes
  1. C. Mao, T. H. LaBean, J. Reif, N. C. Seeman, Nature, 407, 493 (2000).
  2. T-J. Fu, and N. C. Seeman, Biochemistry, 32, 3211-3220, (1993).
  3. E. Winfree, T. Eng, G. Rozenberg, The 8th International Meeting on DNA Based Computers (DNA 8), Sapporo, Japan, June 10-13, 2002.