Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Về Năng Lực Tính Toán của Mạng Phản Ứng Chuyển Phosphate
Tóm tắt
Các phản ứng chuyển phosphate (Nguyên lý hóa sinh, Prentice Hall, Upper Saddle River, 1996) liên quan đến việc chuyển một nhóm phosphate từ một phân tử cho đến một phân tử nhận, điều này rất phổ biến trong hóa sinh. Ngoài các hệ thống tự nhiên, một số hệ thống phân tử tổng hợp như cổng seesaw cũng tương đương với (một tập con của) mạng phản ứng chuyển phosphate. Trong bài báo này, chúng tôi nghiên cứu năng lực tính toán của các mạng phản ứng chuyển phosphate (PTRNs). PTRNs là mạng phản ứng hóa học (CRNs) chỉ có các phản ứng chuyển phosphate. Trước đây, đã được biết rằng (Nat Comput 13:517–534, 2014) một hàm có thể được tính toán một cách xác định bởi một CRN nếu và chỉ nếu nó là bán tuyến tính. Tuy nhiên, năng lực tính toán của các mạng chuyển phosphate lập trình được vẫn chưa được biết. Trong bài báo này, chúng tôi trình bày một mô hình chính thức để mô tả PTRNs và nghiên cứu năng lực tính toán của các mạng này. Chúng tôi chứng minh rằng khi mỗi phân tử chỉ mang được một nhóm phosphate, đầu ra phải là tổng số ban đầu trong một tập con $$S_1$$ trừ đi tổng số ban đầu của một tập con khác $$S_2$$. Mặt khác, khi mỗi phân tử có thể mang tối đa ba nhóm phosphate, hoặc hai nhóm phosphate với các chức năng khác nhau, PTRNs có thể "mô phỏng" các CRNs tùy ý. Cuối cùng, khi mỗi phân tử có thể mang tối đa hai nhóm phosphate chức năng giống nhau (hoặc, tương đương, hai nhóm phosphate phải được thêm/và bớt theo thứ tự), chúng tôi chứng minh rằng năng lực tính toán mạnh hơn rõ rệt so với PTRNs với tối đa một nhóm phosphate mỗi phân tử.
Từ khóa
#phản ứng chuyển phosphate #mạng phản ứng hóa học #tính toán #mô hình chính thứcTài liệu tham khảo
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4), 235–253 (2006)
Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. In: Distributed computing, pp. 61–75. Springer, Berlin (2006)
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, pp. 292–299. ACM (2006)
Chan, C.H., Chen, H.L.: Deterministic function computation with phosphate transfer reaction networks. In: Poster in the thirteenth annual conference on the foundations of nanoscience (2016)
Chen, H.L., Doty, D., Soloveichik, D.: Deterministic function computation with chemical reaction networks. Natural Comput. 13(4), 517–534 (2014)
Chen, H.L., Doty, D., Soloveichik, D.: Rate-independent computation in continuous chemical reaction networks. In: Proceedings of the 5th conference on Innovations in theoretical computer science, pp. 313–326. ACM (2014)
Doty, D., Monir, H.: Leaderless deterministic chemical reaction networks. Natural Comput. 14, 213–223 (2015)
Elowitz, M.B., Levine, A.J., Siggia, E.D., Swain, P.S.: Stochastic gene expression in a single cell. Science 297(5584), 1183–1186 (2002)
Esparza, J.: Decidability and complexity of petri net problems—an introduction. In: Lectures on Petri Nets I: basic models, pp. 374–428. Springer, Berlin (1998)
Hjelmfelt, A., Weinberger, E.D., Ross, J.: Chemical implementation of neural networks and turing machines. Proc. Natl. Acad. Sci. 88(24), 10983–10987 (1991)
Horn, F., Jackson, R.: General mass action kinetics. Arch. Ration. Mech. Anal. 47(2), 81–116 (1972)
Horton, H.R., Moran, L.A., Ochs, R.S., Rawn, J.D., Scrimgeour, K.G.: Principles of biochemistry. Prentice Hall, Upper Saddle River (1996)
Johnson, R., Dong, Q., Winfree, E.: Verifying chemical reaction network implementations: a bisimulation approach. Theor. Comput. Sci. 765, 3–46 (2018)
Karp, R.M., Miller, R.E.: Parallel program schemata. J. Comput. Syst. Sci. 3(2), 147–195 (1969)
Lodish, H.F., Berk, A., Zipursky, S.L., Matsudaira, P., Baltimore, D., Darnell, J., et al.: Molecular cell biology, vol. 4. Citeseer (2000)
Magnasco, M.O.: Chemical kinetics is turing universal. Phys. Rev. Lett. 78(6), 1190 (1997)
McAdams, H.H., Arkin, A.: Stochastic mechanisms in gene expression. Proc. Natl. Acad. Sci. 94(3), 814–819 (1997)
Minsky, M.L.: Computation: finite and infinite machines. Prentice-Hall, Inc., Upper Saddle River (1967)
Qian, L., Winfree, E.: Scaling up digital circuit computation with DNA strand displacement cascades. Science 332(6034), 1196–1201 (2011)
Qian, L., Winfree, E.: A simple DNA gate motif for synthesizing large-scale circuits. J. R. Soc. Interface 8(62), 1281–1297 (2011)
Reece, J., Urry, L.A., Meyers, N., Cain, M.L., Wasserman, S.A., Minorsky, P.V., Jackson, R.B., Cooke, B.N.: Campbell biology. Pearson Higher Education, Hoboken (2011)
Shin, S.W., Thachuk, C., Winfree, E.: Verifying chemical reaction network implementations: a pathway decomposition approach. Theor. Comput. Sci. 765, 67–96 (2017)
Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Nat. Comput. 7(4), 615–633 (2008)
Soloveichik, D., Seelig, G., Winfree, E.: DNA as a universal substrate for chemical kinetics. Proc. Natl. Acad. Sci. 107(12), 5393–5398 (2010)
Süel, G.M., Garcia-Ojalvo, J., Liberman, L.M., Elowitz, M.B.: An excitable gene regulatory circuit induces transient cellular differentiation. Nature 440(7083), 545–550 (2006)