Local parallel biomolecular computation

Biomolecular Computation(BMC) is computation at the molecular scale, using biotechnology engineering techniques. Most proposed methods for BMC used distributed (molecular) paral-lelism (DP); where operations are executed in parallel on large numbers of distinct molecules. BMC done exclusively by DP requires that the computation execute sequentially within any given molecule (though done in parallel for multiple molecules). In contrast, local parallelism (LP) allows operations to be executed in parallel on each given molecule. Winfree, et al [W96, WYS96]) proposed an innovative method for LP-BMC, that of com-putation by unmediated self-assembly of 2D arrays of DNA molecules, applying known domino tiling techniques (see Buchi [B62], Berger [B66], and [R71, LP81]) in combination with recom-binant DNA nano-fabrication techniques of Seeman et al [SZC94]. The likelihood for successful unmediated self-assembly of computations has not been determined (we discuss a simple model of assembly where there may be blockages in self-assembly, but more sophisticated models may have a higher likelihood of success). We develop improved techniques to more fully exploit the potential power of LP-BMC. T