Skip to main content

Local parallel biomolecular computation

Publication ,  Journal Article
Reif, JH
Published in: International Journal of Unconventional Computing
December 1, 2012

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 LP-BMC, 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, decrese 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. © 2013 Old City Publishing, Inc.

Duke Scholars

Published In

International Journal of Unconventional Computing

EISSN

1548-7202

ISSN

1548-7199

Publication Date

December 1, 2012

Volume

8

Issue

5-6

Start / End Page

459 / 507

Related Subject Headings

  • Fluids & Plasmas
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H. (2012). Local parallel biomolecular computation. International Journal of Unconventional Computing, 8(5–6), 459–507.
Reif, J. H. “Local parallel biomolecular computation.” International Journal of Unconventional Computing 8, no. 5–6 (December 1, 2012): 459–507.
Reif JH. Local parallel biomolecular computation. International Journal of Unconventional Computing. 2012 Dec 1;8(5–6):459–507.
Reif, J. H. “Local parallel biomolecular computation.” International Journal of Unconventional Computing, vol. 8, no. 5–6, Dec. 2012, pp. 459–507.
Reif JH. Local parallel biomolecular computation. International Journal of Unconventional Computing. 2012 Dec 1;8(5–6):459–507.

Published In

International Journal of Unconventional Computing

EISSN

1548-7202

ISSN

1548-7199

Publication Date

December 1, 2012

Volume

8

Issue

5-6

Start / End Page

459 / 507

Related Subject Headings

  • Fluids & Plasmas