Local Parallel Biomolecular Computation
John H. Reif
Biomolecular Computation (BMC) is computation at the molecular scale, using biotechnology engineering techniques. Most proposed methods for BMC used distributed (molecular) parallelism (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. [120, 124]) proposed an innovative method for LPBMC, that of computation by unmediated self-assembly of 2D arrays of DNA molecules, applying known domino tiling techniques (see Buchi [21], Berger [16], Robinson [88], and Lewis and Papadimitriou [50]) in combination with the DNA self-assembly techniques of Seeman et al. [105].
We develop improved techniques to more fully exploit the potential power of LP-BMC. we propose a refined step-wise assembly method, which provides control of the assembly in distinct steps. Step-wise assembly may increase the likelihood of success of assembly, decrease the number of tiles required, and provide additional control of the assembly process. The assembly depth is the number of stages of assembly required and the assembly size is the number of tiles required.
We also introduce the assembly frame, a rigid nanostructure which binds the input DNA strands in place on its boundaries and constrains the shape of the assembly. Our main results are LP-BMC algorithms for some fundamental problems that form the basis of many parallel computations. For these problems we decrease the assembly size to linear in the input size and and significantly decrease the assembly depth. We give LP-BMC algorithms with linear assembly size and logarithmic assembly depth, for the parallel prefix computation problems, which include integer addition, subtraction, multiplication by a constant number, finite state automata simulation, and fingerprinting (hashing) a string. We also give LP-BMC methods for perfect shuffle and pair-wise exchange using a linear size assembly and constant assembly depth. This provides logarithmic assembly depth LP-BMC algorithms for the large class of normal parallel algorithms [49, 112, 113] on shuffle-exchange networks, e.g. DFT, bitonic merge, fixed permutation of data, as well as evaluation of a bounded degree Boolean circuit in time bounded by the product of the circuit depth times a logarithm of the circuit size. Our LP-BMC methods may require somewhat smaller volumes than previous DP-BMC algorithms [75, 81] for these problems. All our LP-BMC assembly techniques can be combined with DP-BMC parallelism to simultaneously solve multiple problems with distinct inputs (e.g. do parallel arithmetic on multiple inputs, or determine satisfying inputs of a circuit), so they are an enhancement of the power of DP-BMC.