We introduce ppsim, a software package for efficiently simulating population protocols, a widely-studied subclass of chemical reaction networks (CRNs) in which all reactions have two reactants and two products. Each step in the dynamics involves picking a uniform random pair from a population of $n$ molecules to collide and have a (potentially null) reaction. In a recent breakthrough, Berenbrink, Hammer, Kaaser, Meyer, Penschuck, and Tran [ESA 2020] discovered a population protocol simulation algorithm quadratically faster than the naive algorithm, simulating $\Theta(\sqrt{n})$ reactions in *constant* time, while preserving the *exact* stochastic dynamics. ppsim implements this algorithm, with a tightly optimized Cython implementation that can exactly simulate hundreds of billions of reactions in seconds. It dynamically switches to the CRN Gillespie algorithm for efficiency gains when the number of applicable reactions in a configuration becomes small. As a Python library, ppsim also includes many useful tools for data visualization in Jupyter notebooks, allowing robust visualization of time dynamics such as histogram plots at time snapshots and averaging repeated trials. Finally, we give a framework that takes any CRN with only bimolecular (2 reactant, 2 product) or unimolecular (1 reactant, 1 product) reactions, with arbitrary rate constants, and compiles it into a continuous-time population protocol. This lets ppsim exactly sample from the chemical master equation (unlike approximate heuristics such as tau-leaping or LNA), while achieving asymptotic gains in running time. In linked Jupyter notebooks, we demonstrate the efficacy of the tool on some protocols of interest in molecular programming, including the approximate majority CRN and CRN models of DNA strand displacement reactions.
翻译:我们引入了 ppsim, 这是高效模拟人口协议的软件包, 一个广泛研究的化学反应网络小类( CRN), 其中所有反应都有两个反应和两个产品。 动态的每个步骤都涉及从一个以美元为单位的分子群中取出一个统一的随机配对, 以相撞并产生一个( 可能无效) 反应。 在最近的突破中, Berenbrink、 Hammer、 Kaaser、 Meyer、 Penschuck 和 Tran [ES 2020] 发现了一个人口协议模拟算法, 速度比天真的算法要快得多, 在 * constatant* 时间里模拟 $@theta( sqrt{n})$, 在 *constaltarant * 时间里, 同时保存 * exactral etal mologyalalal modealalalalalal livestical livestical 。 在配置中, 将CRystemal motional motional motional motional motional motional 和 motion motionals motionals, mas max 也能够在任何动态中展示中展示一个动态中展示,,, 使Cryal 。