More Like this

1. Cycle and Commute: Rare-Event Probability Verification for Chemical Reaction Networks

   Taylor, Landon; Israelsen, Bryant; Zhang, Zhen (October 2023, Formal Methods in ComputerAided Design)

   Nadel, Alexander; Rozier, Kristin_Yvonne (Ed.)

   In synthetic biological systems, rare events can cause undesirable behavior leading to pathological effects. Due to their low observability, rare events are challenging to analyze using existing stochastic simulation methods. Chemical Reaction Networks (CRNs) are a general-purpose formal language for modeling chemical kinetics. This paper presents a fully automated approach to efficiently construct a large number of concurrent traces by expanding a sample of known traces. These traces constitute a partial state space containing only traces leading to a rare event of interest. This state space is then used to compute a lower bound for the rare event’s probability. We propose a novel approach for the analysis of highly concurrent CRNs, including a CRN reaction independence analysis and an algorithm that exploits CRN concurrency to rapidly enumerate parallel traces. We then present a novel algorithm to add cycles to a partial state space to further increase the rare event’s probability lower bound to its actual value. The resulting prototype tool, RAGTIMER, demonstrates improvement over stochastic simulation and probabilistic model checking. 

   more » « less
2. A Comprehensive Survey on Rare Event Prediction

   https://doi.org/10.1145/3699955  

   Shyalika, Chathurangi; Wickramarachchi, Ruwan; Sheth, Amit P (March 2025, ACM Computing Surveys)

   Rare event prediction involves identifying and forecasting events with a low probability using machine learning (ML) and data analysis. Due to the imbalanced data distributions, where the frequency of common events vastly outweighs that of rare events, it requires using specialized methods within each step of the ML pipeline, that is, from data processing to algorithms to evaluation protocols. Predicting the occurrences of rare events is important for real-world applications, such as Industry 4.0, and is an active research area in statistical and ML. This article comprehensively reviews the current approaches for rare event prediction along four dimensions: rare event data, data processing, algorithmic approaches, and evaluation approaches. Specifically, we consider 73 datasets from different modalities (i.e., numerical, image, text, and audio), four major categories of data processing, five major algorithmic groupings, and two broader evaluation approaches. This article aims to identify gaps in the current literature and highlight the challenges of predicting rare events. It also suggests potential research directions, which can help guide practitioners and researchers. 

   more » « less
3. Estimation of cyber network risk using rare event simulation

   https://doi.org/10.1177/1548512920934551  

   Krall, Alexander L; Kuhl, Michael E; Yang, Shanchieh J (June 2020, The Journal of Defense Modeling and Simulation: Applications, Methodology, Technology)

   Inherent vulnerabilities in a cyber network’s constituent machine services can be exploited by malicious agents. As a result, the machines on any network are at risk. Security specialists seek to mitigate the risk of intrusion events through network reconfiguration and defense. When dealing with rare cyber events, high-quality risk estimates using standard simulation approaches may be unattainable, or have significant attached uncertainty, even with a large computational simulation budget. To address this issue, an efficient rare event simulation modeling and analysis technique, namely, importance sampling for cyber networks, is developed. The importance sampling method parametrically amplifies certain aspects of the network in order to cause a rare event to happen more frequently. Output collected under these amplified conditions is then scaled back into the context of the original network to provide meaningful statistical inferences. The importance sampling methodology is tailored to cyber network attacks and takes the attacker’s successes and failures as well as the attacker’s targeting choices into account. The methodology is shown to produce estimates of higher quality than standard simulation with greater computational efficiency. 

   more » « less
4. Quantifying Rare Events in Stochastic Reaction-Diffusion Dynamics Using Tensor Networks

   https://doi.org/10.1103/PhysRevX.13.041006  

   Nicholson, Schuyler B.; Gingrich, Todd R. (October 2023, Physical Review X)

   The interplay between stochastic chemical reactions and diffusion can generate rich spatiotemporal patterns. While the timescale for individual reaction or diffusion events may be very fast, the timescales for organization can be much longer. That separation of timescales makes it particularly challenging to anticipate how the rapid microscopic dynamics gives rise to macroscopic rates in the nonequilibrium dynamics of many reacting and diffusing chemical species. Within the regime of stochastic fluctuations, the standard approach is to employ Monte Carlo sampling to simulate realizations of random trajectories. Here, we present an alternative numerically tractable approach to extract macroscopic rates from the full ensemble evolution of many-body reaction-diffusion problems. The approach leverages the Doi-Peliti second-quantized representation of reaction-diffusion master equations along with compression and evolution algorithms from tensor networks. By focusing on a Schlögl model with one-dimensional diffusion between L otherwise well-mixed sites, we illustrate the potential of the tensor network approach to compute rates from many-body systems, here with approximately 3 × 10^15 microstates. Specifically, we compute the rate for switching between metastable macrostates, with the expense for computing those rates growing subexponentially in L. Because we directly work with ensemble evolutions, we crucially bypass many of the difficulties encountered by rare event sampling techniques—detailed balance and reaction coordinates are not needed. 

   more » « less
5. Reactamole: Functional Reactive Molecular Programming

   Klinge, Titus H.; Lathrop, James I.; Osera, Peter-Michael; Rogers, Allison (January 2021, 27th International Conference on DNA Computing and Molecular Programming (DNA 27))

   Lakin, Matthew R.; Šulc, Petr (Ed.)

   Chemical reaction networks (CRNs) are an important tool for molecular programming, a field that is rapidly expanding our ability to deploy computer programs into biological systems for a variety of applications. However, CRNs are also difficult to work with due to their massively parallel nature, leading to the need for higher-level languages that allow for easier computation with CRNs. Recently, research has been conducted into a variety of higher-level languages for deterministic CRNs but modeling CRN parallelism, managing error accumulation, and finding natural CRN representations are ongoing challenges. We introduce Reactamole, a higher-level language for deterministic CRNs that utilizes the functional reactive programming (FRP) paradigm to represent CRNs as a reactive dataflow network. Reactamole equates a CRN with a functional reactive program, implementing the key primitives of the FRP paradigm directly as CRNs. The functional nature of Reactamole makes reasoning about molecular programs easier, and its strong static typing allows us to ensure that a CRN is well-formed by virtue of being well-typed. In this paper, we describe the design of Reactamole and how we use CRNs to represent the common datatypes and operations found in FRP. We also demonstrate the potential of this functional reactive approach to molecular programming by giving an extended example where a CRN is constructed using FRP to modulate and demodulate an amplitude modulated signal. 

   more » « less