Error Suppresion Via Block Replacement

``Kinetic proofreading``, which was independently discovered by Hopfield and Ninio , is an error correcting mechanism employed by a variety of biological processes (e.g. RNA to protein translation) where a sequence of steps are utilized such that the process must progress through each, with step each "testing", or helping to ensure, the correctness of the last step. In , Winfree and Bekbolatov demonstrated such a technique (which they simply called proofreading) to reduce growth errors in the kTAM. In proofreading, individual tile types are replaced by n × n blocks of unique tile types such that the perimeter of the n × n block formed by them represents the same glues as the original single tile. (New glues are created for the interior of the block which are specific to the tile types composing each particular block.) However, those original glues are now split into n separate glues. The goal is to force multiple errors to occur before an incorrect n × n block can fully form, as opposed to the single error which would allow the analogous incorrect tile from the original tile set to bind. They found that by increasing \(n\), it is possible to reduce the growth errors - or alternatively to increase the speed of assembly while maintaining the same error rate.

For this example, we construct two of the substitutions for the 2 × 2 proofreading tile set for the Sierpinski triangle (shown in its original form in Figure 1 to the right.

Figure 1. The tile types for weakly self-assembling the Sierpinski triangle.

In Figure 2 (below), two of the tiles from the original set are replaced by 4 tiles each. Note how each group of 4 tiles forms a 2 × 2 block whose perimeter has versions of the glues from the original tile in corresponding locations. For example, the 0 glue on the south side of each original tile is now represented by two separate glues, \(0_L\) and \(0_R\), which correspond to the left 0 glue of each 2 × 2 block, and the right 0 glue. The glues on adjacent edges of tiles in the interior of blocks are replaced by new glues which are specific to each such location.

The tile set resulting from such a transformation reduces errors in the following way. In order for an incorrect block to assemble in a given location (i.e. a block which doesn't match the input from one of the two input directions), it must have more than one tile originally bind with only strength 1. Each of those tiles must then get "locked in" by subsequent tile attachments before falling off. Since it is much more unlikely for multiple instances of such errors to be locked in before detachment than it is for one, the overall likelihood of error is smaller for the proofreading system.

Replacing a "0-1" rule tile

Replacing a "0-0" rule tile

Figure 2. Example tile substitution by 2 × 2 blocks of tiles for proofreading. Each image shows a single rule tile for the Sierpinski triangle tile set on the right and the 4 tiles which replace it in the proofreading tile set on the left.