Time-Complexity of Multilayered DNA Strand Displacement Circuits
- Creators
- Seelig, Georg
- Soloveichik, David
- Others:
- Deaton, Russell
- Suyama, Akira
Abstract
Recently we have shown how molecular logic circuits with many components arranged in multiple layers can be built using DNA strand displacement reactions. The potential applications of this and similar technologies inspire the study of the computation time of multilayered molecular circuits. Using mass action kinetics to model DNA strand displacement-based circuits, we discuss how computation time scales with the number of layers. We show that depending on circuit architecture, the time-complexity does not necessarily scale linearly with the depth as is assumed in the usual study of circuit complexity. We compare circuits with catalytic and non-catalytic components, showing that catalysis fundamentally alters asymptotic time-complexity. Our results rely on simple asymptotic arguments that should be applicable to a wide class of chemical circuits. These results may help to improve circuit performance and may be useful for the construction of faster, larger and more reliable molecular circuitry.
Additional Information
© 2009 Springer-Verlag Berlin Heidelberg. We thank Ho-Lin Chen, Matthew Cook, Anton Andreev, Bernard Yurke and Erik Winfree for discussions and help. GS was supported by the Swiss National Science Foundation and by a Career Award at the Scientific Interface from the Burroughs Wellcome Fund.Additional details
- Eprint ID
- 27424
- DOI
- 10.1007/978-3-642-10604-0_15
- Resolver ID
- CaltechAUTHORS:20111025-150720323
- Swiss National Science Foundation (SNSF)
- Burroughs Wellcome Fund
- Created
-
2011-10-26Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Series Name
- Lecture Notes in Computer Science
- Series Volume or Issue Number
- 5877