On the Computational Power of Phosphate Transfer Reaction Networks
Journal
New Generation Computing
Date Issued
2022
Author(s)
Abstract
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.
Subjects
Chemical reaction networks; Function computation; Phosphate transfer reactions
Other Subjects
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
Type
journal article