Abstract
When disallowing error, traditional chemical reaction networks (CRNs) are very limited in computational power: Angluin et al. and Chen et al. showed that only semilinear predicates and functions are stably computable by CRNs. Qian et al. and others have shown that polymer-supplemented CRNs (psCRNs) are capable of Turing-universal computation. However, their model requires that inputs are pre-loaded on the polymers, in contrast with the traditional convention that inputs are represented by counts of molecules in solution. Here, we show that psCRNs can stably simulate Turing-universal computations even with solution-based inputs. However, such simulations use a unique “leader” polymer per input type and thus involve many slow bottleneck reactions. We further refine the polymer-supplemented CRN model to allow for anonymous polymers, that is, multiple functionally-identical copies of a polymer, and provide an illustrative example of how bottleneck reactions can be avoided in this new model.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Nat. Comput. 7(4), 615–633 (2008)
Chen, H.-L., Doty, D., Soloveichik, D.: Deterministic function computation with chemical reaction networks. Nat. Comput. 13, 517–534 (2014)
Angluin, D., Aspnes, J., Eisenstat, D.: Stably computable predicates are semilinear. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, New York, pp. 292–299. ACM Press (2006)
Cummings, R., Doty, D., Soloveichik, D.: Probability 1 computation with chemical reaction networks. Nat. Comput. 15(2), 245–261 (2014)
Qian, L., Soloveichik, D., Winfree, E.: Efficient turing-universal computation with DNA polymers. In: Sakakibara, Y., Mi, Y. (eds.) DNA 2010. LNCS, vol. 6518, pp. 123–140. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-18305-8_12
Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Nat. Comput. 7, 615–633 (2008)
Bennett, C.: Logical reversibility of computation. IBM J. Res. Dev. 17(6), 525–532 (1973)
Bennett, C.: The thermodynamics of computation - a review. Int. J. Theor. Phys. 21(12), 905–940 (1981)
Johnson, R., Winfree, E.: Verifying polymer reaction networks using bisimulation (2014)
Cardelli, L., Zavattaro, G.: Turing universality of the biochemical ground form. Math. Struct. Comput. Sci. 20, 45–73 (2010)
Jiang, H., Riedel, M., Parhi, K.: Synchronous sequential computation with molecular reactions. In: Proceedings of the 48th Design Automation Conference, DAC 2011, New York, pp. 836–841. ACM (2011)
Lakin, M.R., Phillips, A.: Modelling, simulating and verifying turing-powerful strand displacement systems. In: Cardelli, L., Shih, W. (eds.) DNA 2011. LNCS, vol. 6937, pp. 130–144. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23638-9_12
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18, 235–253 (2006)
Chatzigiannakis, I., Michail, O., Nikolaou, S., Pavlogiannis, A., Spirakis, P.G.: Passively mobile communicating machines that use restricted space. In: Proceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing, FOMC 2011, New York, pp. 6–15. ACM (2011)
Chen, H.-L., Cummings, R., Doty, D., Soloveichik, D.: Speed faults in computation by chemical reaction networks. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 16–30. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45174-8_2
Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. In: Dolev, S. (ed.) DISC 2006. LNCS, vol. 4167, pp. 61–75. Springer, Heidelberg (2006). https://doi.org/10.1007/11864219_5
Gibson, M.A., Bruck, J.: Efficient exact stochastic simulation of chemical systems with many species and many channels. J. Phys. Chem. A 104(9), 1876–1889 (2000)
Gillespie, D.T.: Exact stochastic simulation of coupled chemical reactions. J. Phys. Chem. 81(25), 2340–2361 (1977)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Tai, A., Condon, A. (2019). Error-Free Stable Computation with Polymer-Supplemented Chemical Reaction Networks. In: Thachuk, C., Liu, Y. (eds) DNA Computing and Molecular Programming. DNA 2019. Lecture Notes in Computer Science(), vol 11648. Springer, Cham. https://doi.org/10.1007/978-3-030-26807-7_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-26807-7_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-26806-0
Online ISBN: 978-3-030-26807-7
eBook Packages: Computer ScienceComputer Science (R0)