Diverse and robust molecular algorithms using reprogrammable DNA self-assembly

Abstract

Molecular biology provides an inspiring proof-of-principle that chemical systems can store and process information to direct molecular activities such as the fabrication of complex structures from molecular components. A first step towards mimicking this capability is understanding how molecular interactions encode and execute algorithms, with self-assembly of relatively simple units into complex products1 particularly well-suited for such investigations. Theory has indeed shown that full-fledged algorithmic behavior can be embedded within molecular self-assembly processes2,3, and this has been experimentally demonstrated by using DNA nanotechnology4 and up to 22 tile types5,6,7,8,9,10,11. But many information technologies exhibit a complexity threshold – such as the minimum transistor count needed for a general-purpose computer – beyond which the power of a reprogrammable system increases qualitatively, and it remains unclear whether the biophysics of DNA self-assembly allows that threshold to be exceeded. Here we report the design and experimental validation of a DNA tile set that contains 355 single-stranded tiles and can, through simple tile selection, be reprogrammed to implement a wide variety of 6-bit algorithms. We use this set to implement 21 circuits that include copying, sorting, recognizing palindromes and multiples of 3, random walking, obtaining an unbiased choice from a biased random source, electing a leader, simulating cellular automata, generating deterministic and randomised patterns, and serving as a period 63 counter, and find an average per-tile error rate less than 1 in 3000. These findings suggest that molecular self-assembly may serve as a reliable algorithmic component within future programmable chemical systems that could serve as creative spaces where high-level molecular programmers can flourish.