Logical computation using algorithmic self-assembly of dna triple-crossover molecules

Recent work has demonstrated the self-assembly of designed periodic two-dimensional arrays composed of DNA tiles, in which the intermolecular contacts are directed by 'sticky ' ends. In a mathematical context, aperiodic mosaics may be formed by the self-assembly of 'Wang ' tiles 4, a process that emulates the operation of a Turing machine. Macroscopic self-assembly has been used to perform computations 5; there is also a logical equivalence between DNA sticky ends and Wang tile edges 6, 7. This suggests that the self-assembly of DNA-based tiles could be used to perform DNA-based computation 8. Algorithmic aperiodic self-assembly requires greater fidelity than periodic self-assembly, because correct tiles must compete with partially correct tiles. Here we report a one-dimensional algorithmic self-assembly of DNA triple-crossover molecules 9 that can be used to execute four steps of a logical (cumulative XOR) operation on a string of binary bits. A variety of different DNA tile types have been used in previous assemblies, including double-crossover molecules 1, triple-crossover molecules 9, and parallelograms produced from Holliday junction analogues 3