Decreasing Errors by Increasing Redundancy

Abstract

While biology demonstrates that molecules can reliably transfer information and compute, design principles for implementing complex molecular computations in vitroare still being developed. In electronic computers, large-scale computation is made possible by redundancy, which allows errors to be detected and corrected. Increasing the amount of redundancy can exponentially reduce errors. Here, we use algorithmic self-assembly, a generalization of crystal growth in which the self-assembly process executes a program for growing an object, to examine experimentally whether redundancy can analogously reduce the rate at which errors occur during molecular self-assembly. We designed DNA double-crossover molecules to algorithmically self-assemble ribbon crystals that repeatedly copy a short bitstring, and we measured the error rate when each bit is encoded by 1 molecule, or redundantly encoded by 2, 3, or 4 molecules. Under our experimental conditions, each additional level of redundancy decreases the bitwise error rate by a factor of roughly 3, with the 4-redundant encoding yielding an error rate less than 0.1%. While theory and simulation predict that larger improvements in error rates are possible, our results already suggest that by using sufficient redundancy it may be possible to algorithmically self-assemble micrometer-sized objects with programmable, nanometer-scale features.

Overview

In practice, tiles often attach unfavorably but will fall off later because of the unfavorable attachment. However, if a second tile attaches to an unfavorably attached tile before it can fall off, the tile can be “locked in” as a mismatch error. Errors can be decreased in two ways. The first is by changing the physical conditions of assembly which includes temperature, molecular design, or tile concentrations. The other way is changing the logical properties of the tile set design, as that is what controls which kinds of rule violations cause errors in the final assembly. An example of logical properties is how information is propagated. Tile sets that propagate information in one direction, such as copying binary patterns from layer to layer, have error rates ranging from 0.01 to 2% per tile. Error rates increase to 1 to 10% per tile when tile sets propagate and process information in two directions for most assembly steps. Therefore, there may be some tiles sets that are logically more error prone but there could also be techniques for designing tile sets that have lower error rates. Once such technique is proofreading, which increases the size of the product while exponentially reducing self-assembly error rates. With proofreading tile sets, each tile is represented by a block of tiles. For two-dimensional information propagation, proofreading tile sets require a quadratic increase in the number of tile types. For one-dimensional information propagation, proofreading tile sets require just a linear increase in the number of tile types. The same input and output information is redundantly encoded on the perimeter of the block while binding domains on the interior of the block encode how the tiles within a block will fit together uniquely. Proofreading tiles require further mismatching errors to occur before an unfavorably attached tile is locked in, so it prevents assembly errors. The number of mismatches that must occur before a tile is locked in depends on the block size.

Results

The authors use four zig-zag tile set sequences that propagate information in one dimension. The tile sets used four levels of proofreading redundancy ranging from no redundancy (the 1-redundant tile set) to quadruple redundancy (the 4-redundant tile set). Simulations in the kinetic Tile Assembly Model (kTAM) are used to predict how the levels of redundancy and temperature should affect the error rate in addition to the error rates between seeded and unseeded tile assemblies. The tile and seed assemblies were then assessed to ensure they would form properly and that the resulting number of sequences were balanced so it would be easier to quantitatively measure how redundancy affects error rates . Error rates for the tile sets at each level of redundancy are then compared by counting the bits that were correctly and incorrectly copied.

As the level of redundancy increased, the error rate decreased by a factor of approximately 3, but the biggest decrease in error rates occurred after the first level of redundancy. This aligned with the authors predictions qualitatively, but the decrease in the error rates was much smaller than what was predicted by the simulations.

Per-bit error rates during growth. "1R" = 1-redundant, "2R" = 2-redundant, "3R" = 3-redundant, "4R" = 4-redundant. The graph quantities include both seeded and unseeded growth. The last three bars show error rates of 1-redundant growth under different conditions. “1R ns” is the error rate within 1-redundant grown without seeds. “1R s” is the error rate of 1-redundant grown with seeds that are seeded with very high probability because they begin with the seeded sequence, 0101 or 1010, that otherwise rarely nucleates. “1R w/3R” is the measured error rate for the fourth row of the 3-redundant tiles, which copied 1 bit nonredundantly. For each level of redundancy, the number of errors are tabulated using 25 AFM images of tiles 1 μm on each side, about 5000-10 000 ribbon rows.