nips nips2013 nips2013-189 nips2013-189-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nils E. Napp, Ryan P. Adams
Abstract: Recent work on molecular programming has explored new possibilities for computational abstractions with biomolecules, including logic gates, neural networks, and linear systems. In the future such abstractions might enable nanoscale devices that can sense and control the world at a molecular scale. Just as in macroscale robotics, it is critical that such devices can learn about their environment and reason under uncertainty. At this small scale, systems are typically modeled as chemical reaction networks. In this work, we develop a procedure that can take arbitrary probabilistic graphical models, represented as factor graphs over discrete random variables, and compile them into chemical reaction networks that implement inference. In particular, we show that marginalization based on sum-product message passing can be implemented in terms of reactions between chemical species whose concentrations represent probabilities. We show algebraically that the steady state concentration of these species correspond to the marginal distributions of the random variables in the graph and validate the results in simulations. As with standard sum-product inference, this procedure yields exact results for tree-structured graphs, and approximate solutions for loopy graphs.
[1] Subhayu Basu, Yoram Gerchman, Cynthia H. Collins, Frances H. Arnold, and Ron Weiss. A synthetic multicellular system for programmed pattern formation. Nature, 434:1130–1134, 2005.
[2] Christopher M. Bishop. Pattern Recognition and Machine Learning. Information Science and Statistics. Springer, 2006.
[3] Luca Cardelli and Gianluigi Zavattaro. On the computational power of biochemistry. In Katsuhisa Horimoto, Georg Regensburger, Markus Rosenkranz, and Hiroshi Yoshida, editors, Algebraic Biology, volume 5147 of Lecture Notes in Computer Science, pages 65–80. Springer Berlin Heidelberg, 2008.
[4] Ho-Lin Chen, David Doty, and David Soloveichik. Deterministic function computation with chemical reaction networks. In Darko Stefanovic and Andrew Turberfield, editors, DNA Computing and Molecular Programming, volume 7433 of Lecture Notes in Computer Science, pages 25–42. Springer Berlin Heidelberg, 2012.
[5] Yuan-Jyue Chen, Neil Dalchau, Niranjan Srinivas, Andrew Phillips, Luca Cardelli, David Soloveichik, and Georg Seelig. Programmable chemical controllers made from DNA. Nature Nanotechnology, 8(10):755–762, October 2013.
[6] Matthew Cook, David Soloveichik, Erik Winfree, and Jehoshua Bruck. Programmability of chemical reaction networks. In Algorithmic Bioprocesses, Natural Computing Series, pages 543–584. Springer Berlin Heidelberg, 2009.
[7] Tal Danino, Octavio Mondragon-Palomino, Lev Tsimring, and Jeff Hasty. A synchronized quorum of genetic clocks. Nature, 463:326–330, 2010.
[8] Michael B. Elowitz and Stanislas Leibler. A synthetic oscillatory network of transcriptional regulators. Nature, 403:335–338, 2000.
[9] A Hjelmfelt, E D Weinberger, and J Ross. Chemical implementation of neural networks and Turing machines. Proceedings of the National Academy of Sciences, 88(24):10983–10987, 1991.
[10] Erik Winfree Jongmin Kim, John J. Hopfield. Neural network computation by in vitro transcriptional circuits. In Advances in Neural Information Processing Systems 17 (NIPS 2004). MIT Press, 2004.
[11] Marcelo O. Magnasco. Chemical kinetics is Turing universal. Phys. Rev. Lett., 78:1190–1193, Feb 1997.
[12] Chengde Mao, Thomas H. LaBean, John H. Reif, and Nadrian C. Seeman. Logical computation using algorithmic self-assembly of DNA triple-crossover molecules. Nature, 407:493–496, 2000.
[13] K. Oishi and E. Klavins. Biomolecular implementation of linear I/O systems. Systems Biology, IET, 5(4):252–260, 2011.
[14] Lulu Qian, Erik Winfree, and Jehoshua Bruck. Neural network computation with DNA strand displacement cascades. Nature, 475:368–372, 2011.
[15] Paul W. K Rothemund, Nick Papadakis, and Erik Winfree. Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol, 2(12):e424, 12 2004.
[16] Georg Seelig, David Soloveichik, David Yu Zhang, and Erik Winfree. Enzyme-free nucleic acid logic circuits. Science, 314(5805):1585–1588, 2006.
[17] David Soloveichik, Georg Seelig, and Erik Winfree. DNA as a universal substrate for chemical kinetics. Proceedings of the National Academy of Sciences, 107(12):5393–5398, 2010.
[18] Benjamin Vigoda. Analog Logic: Continuous-Time Analog Circuits for Statistical Signal Processing. PhD thesis, Massachusetts Institute of Technology, 2003.
[19] Jonathan S. Yedidia, W.T. Freeman, and Y. Weiss. Constructing free-energy approximations and generalized belief propagation algorithms. Information Theory, IEEE Transactions on, 51(7):2282–2312, 2005.
[20] David Yu Zhang and Georg Seelig. DNA-based fixed gain amplifiers and linear classifier circuits. In Yasubumi Sakakibara and Yongli Mi, editors, DNA Computing and Molecular Programming, volume 6518 of Lecture Notes in Computer Science, pages 176–186. Springer Berlin Heidelberg, 2011. 9