https://scholars.lib.ntu.edu.tw/handle/123456789/632195
標題: | On the Computational Power of Phosphate Transfer Reaction Networks | 作者: | Chan C.-H Shih C.-Y CHEN HO-LIN |
關鍵字: | Chemical reaction networks; Function computation; Phosphate transfer reactions | 公開日期: | 2022 | 來源出版物: | New Generation Computing | 摘要: | Phosphate transfer reactions (Principles of biochemistry, Prentice Hall, Upper Saddle River, 1996) involve 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 (Nat Comput 13:517??34, 2014) that a function can be deterministically computed by a CRN if and only if it is semilinear. However, the computational power of programmable phosphate transfer networks is unknown. In this paper, we present a formal model to describe PTRNs and study the computational power of these networks. We prove that when each molecule can only carry one phosphate group, the output must be the total initial count in a subset S1 minus the total initial count of another subset S2. On the other hand, when every molecule can carry up to three phosphate groups, or two phosphate groups with 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), we prove that the computational power is strictly stronger than PTRNs with at most one phosphate group per molecule. © 2022, Ohmsha, Ltd. and Springer Japan KK, part of Springer Nature. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85127295765&doi=10.1007%2fs00354-022-00154-6&partnerID=40&md5=0d5e453f1c57e8abe92b733d92cefe97 https://scholars.lib.ntu.edu.tw/handle/123456789/632195 |
ISSN: | 2883635 | DOI: | 10.1007/s00354-022-00154-6 | SDG/關鍵字: | Biochemistry; Chemical reactions; Chemical reaction networks; Computational power; Donor molecules; Function computations; Phosphate group; Phosphate transfer; Phosphate transfer reaction; Reaction network; Reaction principle; Transfer reaction; Molecules |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。