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

Recent work(1-3) has demonstrated the self-assembly of designed periodic tw o-dimensional arrays composed of DNA tiles, in which the intermolecular con tacts are directed by `sticky' ends. In a mathematical context, aperiodic m osaics may be formed by the self-assembly of `Wang' tiles(4), a process tha t 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 se lf-assembly of DNA-based tiles could be used to perform DNA-based computati on(8). Algorithmic aperiodic self-assembly requires greater fidelity than p eriodic self-assembly, because correct tiles must compete with partially co rrect 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.