探討伴隨磷酸鹽轉移子反應網路的計算能力

On the Computational Power of Phosphate Transfer Reaction Networks

施承佑(Cheng-Yu Shih)

指導教授 ： 陳和麟

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2020年)

https://doi.org/10.6342/NTU202001272

摘要

伴隨磷酸鹽轉移子反應是指磷酸基從供給者到接收者的轉移反應，這在生化環境中是相當常見的反應。 除了自然系統外，像是 seesaw gates 這類的合成分子系統都等同於一個伴隨磷酸鹽轉移子反應網路(的子集合)。本論文中，我們主要探討伴隨磷酸鹽轉移子反應網路的計算能力，如同字面上，伴隨磷酸鹽轉移子反應網路是僅由伴隨磷酸鹽轉移子反應所構成的一種化學反應網路。在過往的研究中，化學反應網路的計算能力已經被證明恰巧是任意的半線性函數。而伴隨磷酸鹽轉移子反應網路的計算能力則是根據分子最多能攜帶的磷酸基數量決定。

在本論文中，我們提出了一個正式描述伴隨磷酸鹽轉移子反應網路的模型。我們證明當分子最多僅能攜帶一個磷酸基的網路中，函數輸出必定是輸入的某兩個子集合數量的差值。另一方面，當分子能攜帶三個磷酸基或是兩個功能有所差異的磷酸基，伴隨磷酸鹽轉移子反應網路有能力「模擬」任意的化學反應網路。最後，當每個分子僅能最多攜帶兩個功能一致的磷酸基 (等同於兩個磷酸基一定得依序添加/移除)，這樣的計算能力會是嚴格落在前兩者之間。

關鍵字

化學反應網路 ； 決定性計算 ； 隨機系統 ； 代幣轉移系統 ； 伴隨磷酸鹽轉移子反應網路

並列摘要

Phosphate transfer reactions involves the transfer of a phosphate group from a donor molecule to an accepter, which is ubiquitous in biochemistry. Besides natural systems, some synthetic molecular systems such as seesaw gates are also equivalent to (subsets of) phosphate transfer reaction networks. In this paper, we study the computational power of phosphate transfer reaction networks (PTRNs). PTRNs are chemical reaction networks (CRNs) with only phosphate transfer reactions. Previously, it is known that a function can be deterministically computed by a CRN if and only if it is semilinear. The computational power of PTRNs, on the other hand, depends on how many phosphate group each molecule can carry.

In this paper, we present a formal model to describe PTRNs. We prove that when each molecule can only carry one phosphate group, the output must be the total input count in a subset $S_1$ minus the total input count of another subset $S_2$. On the other hand, when every molecule can carry up to three phosphate groups, or two phosphate group which may have different functions, PTRNs can ``simulate'' arbitrary CRNs. Finally, when each molecule can carry up to two functionally-identical phosphate groups, (or, equivalently, two phosphate groups which must be added/removed in a sequential manner), the computational power is strictly between the above two cases.

並列關鍵字

Chemical Reaction Networks ； Deterministic Computation ； Stochastic Systems ； Token-transferring Systems ； Phosphate Transfer Reaction Networks

參考文獻

[1] D. Angluin, J. Aspnes, and D. Eisenstat. Fast computation by population protocolswith a leader. InDistributed Computing, pages 61–75. Springer, 2006.

[2] D. Angluin, J. Aspnes, and D. Eisenstat. Stably computable predicates are semi-linear. InProceedings of the twenty-fifth annual ACM symposium on Principles ofdistributed computing, pages 292–299. ACM, 2006.

[3] C.-H. Chan and H.-L. Chen. Deterministic function computation with phosphatetransferreactionnetworks. PosterintheThirteenthAnnualConferenceontheFoun-dations of Nanoscience, 2016.

[4] H.-L. Chen, D. Doty, and D. Soloveichik. Deterministic function computation withchemical reaction networks.Natural computing, 13(4):517–534, 2014.

[5] H.-L.Chen,D.Doty,andD.Soloveichik. Rate-independentcomputationincontinu-ouschemicalreactionnetworks. InProceedingsofthe5thconferenceonInnovationsin theoretical computer science, pages 313–326. ACM, 2014.