A Caltech Library Service

Parallel Computation Using Active Self-assembly

Chen, Moya and Xin, Doris and Woods, Damien (2013) Parallel Computation Using Active Self-assembly. In: DNA Computing and Molecular Programming. Lecture Notes in Computer Science. No.8141. Springer International Publishing , Berlin, Germany, pp. 16-30. ISBN 978-3-319-01927-7.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We study the computational complexity of the recently proposed nubots model of molecular-scale self-assembly. The model generalizes asynchronous cellular automaton to have non-local movement where large assemblies of molecules can be moved around, analogous to millions of molecular motors in animal muscle effecting the rapid movement of large arms and legs. We show that nubots is capable of simulating Boolean circuits of polylogarithmic depth and polynomial size, in only polylogarithmic expected time. In computational complexity terms, any problem from the complexity class NC is solved in polylogarithmic expected time on nubots that use a polynomial amount of workspace. Along the way, we give fast parallel algorithms for a number of problems including line growth, sorting, Boolean matrix multiplication and space-bounded Turing machine simulation, all using a constant number of nubot states (monomer types). Circuit depth is a well-studied notion of parallel time, and our result implies that nubots is a highly parallel model of computation in a formal sense. Thus, adding a movement primitive to an asynchronous non-deterministic cellular automation, as in nubots, drastically increases its parallel processing abilities.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2013 Springer International Publishing Switzerland. Supported by National Science Foundation grants CCF-1219274, 0832824. We thank Erik Winfree for valuable discussion and suggestions on our results, Paul Rothemund for stimulating conversations on molecular muscle, and Niall Murphy for informative discussions on circuit complexity theory. Damien thanks Beverley Henley for introducing him to developmental biology many moons ago.
Funding AgencyGrant Number
Series Name:Lecture Notes in Computer Science
Issue or Number:8141
Record Number:CaltechAUTHORS:20140506-085427393
Persistent URL:
Official Citation: Parallel Computation Using Active Self-assembly Moya Chen, Doris Xin, Damien Woods Pages 16-30
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:45513
Deposited By: Ruth Sustaita
Deposited On:06 May 2014 18:11
Last Modified:03 Oct 2019 06:31

Repository Staff Only: item control page