skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, June 12 until 2:00 AM ET on Friday, June 13 due to maintenance. We apologize for the inconvenience.


Title: Efficient Parameter Estimation for DNA Kinetics Modeled as Continuous-Time Markov Chains
Nucleic acid kinetic simulators aim to predict the kinetics of interacting nucleic acid strands. Many simulators model the kinetics of interacting nucleic acid strands as continuous-time Markov chains (CTMCs). States of the CTMCs represent a collection of secondary structures, and transitions between the states correspond to the forming or breaking of base pairs and are determined by a nucleic acid kinetic model. The number of states these CTMCs can form may be exponentially large in the length of the strands, making two important tasks challenging, namely, mean first passage time (MFPT) estimation and parameter estimation for kinetic models based on MFPTs. Gillespie’s stochastic simulation algorithm (SSA) is widely used to analyze nucleic acid folding kinetics, but could be computationally expensive for reactions whose CTMC has a large state space or for slow reactions. It could also be expensive for arbitrary parameter sets that occur in parameter estimation. Our work addresses these two challenging tasks, in the full state space of all non-pseudoknotted secondary structures of each reaction. In the first task, we show how to use a reduced variance stochastic simulation algorithm (RVSSA), which is adapted from SSA, to estimate the MFPT of a reaction’s CTMC. In the second task, we estimate model parameters based on MFPTs. To this end, first, we show how to use a generalized method of moments (GMM) approach, where we minimize a squared norm of moment functions that we formulate based on experimental and estimated MFPTs. Second, to speed up parameter estimation, we introduce a fixed path ensemble inference (FPEI) approach, that we adapt from RVSSA. We implement and evaluate RVSSA and FPEI using the Multistrand kinetic simulator. In our experiments on a dataset of DNA reactions, FPEI speeds up parameter estimation compared to inference using SSA, by more than a factor of three for slow reactions. Also, for reactions with large state spaces, it speeds up parameter estimation by more than a factor of two.  more » « less
Award ID(s):
1643606
PAR ID:
10112046
Author(s) / Creator(s):
; ; ; ; ;
Date Published:
Journal Name:
DNA Computing and Molecular Programming
Volume:
11648
Page Range / eLocation ID:
80-99
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Models of nucleic acid thermal stability are calibrated to a wide range of experimental observations, and typically predict equilibrium probabilities of nucleic acid secondary structures with reasonable accuracy. By comparison, a similar calibration and evaluation of nucleic acid kinetic models to a broad range of measurements has not been attempted so far. We introduce an Arrhenius model of interacting nucleic acid kinetics that relates the activation energy of a state transition with the immediate local environment of the affected base pair. Our model can be used in stochastic simulations to estimate kinetic properties and is consistent with existing thermodynamic models. We infer parameters for our model using an ensemble Markov chain Monte Carlo (MCMC) approach on a training dataset with 320 kinetic measurements of hairpin closing and opening, helix association and dissociation, bubble closing and toehold-mediated strand exchange. Our new model surpasses the performance of the previously established Metropolis model both on the training set and on a testing set of size 56 composed of toehold-mediated 3-way strand displacement with mismatches and hairpin opening and closing rates: reaction rates are predicted to within a factor of three for 93.4% and 78.5% of reactions for the training and testing sets, respectively. 
    more » « less
  2. Abstract Oligonucleotide hybridization is crucial in various biological, prebiotic and nanotechnological processes, including gene regulation, non-enzymatic primer extension and DNA nanodevice assembly. Although extensive research has focused on the thermodynamics and kinetics of nucleic acid hybridization, the behavior of complex mixtures and the outcome of competition for target binding remain less well understood. In this study, we investigate the impact of mismatches and bulges in a 12 bp DNA or RNA duplex on its association (kon) and dissociation (koff) kinetics. We find that such defects have relatively small effects on the association kinetics, while the dissociation kinetics vary in a position-dependent manner by up to 6 orders of magnitude. Building upon this observation, we explored a competition scenario involving multiple oligonucleotides, and observed a transient low specificity of probe hybridization to fully versus partially complementary targets in solution. We characterize these long-lived metastable states and their evolution toward equilibrium, and show that sufficiently long-lived mis-paired duplexes can serve as substrates for prebiotically relevant chemical copying reactions. Our results suggest that transient low accuracy states may spontaneously emerge within all complex nucleic acid systems comprising a large enough number of competing strands, with potential repercussions for gene regulation in the realm of modern biology and the prebiotic preservation of genetic information. 
    more » « less
  3. Chen, Ho-Lin; Evans, Constantine G. (Ed.)
    Polynomial time dynamic programming algorithms play a crucial role in the design, analysis and engineering of nucleic acid systems including DNA computers and DNA/RNA nanostructures. However, in complex multistranded or pseudoknotted systems, computing the minimum free energy (MFE), and partition function of nucleic acid systems is NP-hard. Despite this, multistranded and/or pseudoknotted systems represent some of the most utilised and successful systems in the field. This leaves open the tempting possibility that many of the kinds of multistranded and/or pseudoknotted systems we wish to engineer actually fall into restricted classes, that do in fact have polynomial time algorithms, but we've just not found them yet. Here, we give polynomial time algorithms for MFE and partition function calculation for a restricted kind of multistranded system called the 1D scaffolded DNA computer. This model of computation thermodynamically favours correct outputs over erroneous states, simulates finite state machines in 1D and Boolean circuits in 2D, and is amenable to DNA storage applications. In an effort to begin to ask the question of whether we can naturally compare the expressivity of nucleic acid systems based on the computational complexity of prediction of their preferred energetic states, we show our MFE problem is in logspace (the complexity class L), making it perhaps one of the simplest known, natural, nucleic acid MFE problems. Finally, we provide a stochastic kinetic simulator for the 1D scaffolded DNA computer and evaluate strategies for efficiently speeding up this thermodynamically favourable system in a constant-temperature kinetic regime. 
    more » « less
  4. Abstract. Mineral specific surface area (SSA) increases as primaryminerals weather and restructure into secondary phyllosilicate, oxide, andoxyhydroxide minerals. SSA is a measurable property that captures cumulativeeffects of many physical and chemical weathering processes in a singlemeasurement and has meaningful implications for many soil processes,including water-holding capacity and nutrient availability. Here we reportour measurements of SSA and mineralogy of two 21 m deep SSA profiles attwo landscape positions, in which the emergence of a very small mass percent(<0.1 %) of secondary oxide generated 36 %–81 % of the total SSAin both drill cores. The SSA transition occurred near 3 m at bothlocations and did not coincide with the boundary of soil to weathered rock. The3 m boundary in each weathering profile coincides with the depth extentof secondary iron oxide minerals and secondary phyllosilicates. Althoughelemental depletions in both profiles extend to 7 and 10 m depth, themineralogical changes did not result in SSA increase until 3 m depth. Theemergence of secondary oxide minerals at 3 m suggests that this boundary may bethe depth extent of oxidation weathering reactions. Our results suggest thatoxidation weathering reactions may be the primary limitation in thecoevolution of both secondary silicate and secondary oxide minerals. Wevalue element depletion profiles to understand weathering, but our findingof nested weathering fronts driven by different chemical processes (e.g.,oxidation to 3 m and acid dissolution to 10 m) warrants the recognition thatelement depletion profiles are not able to identify the full set ofprocesses that occur in weathering profiles. 
    more » « less
  5. Abstract Hybridization and strand displacement kinetics determine the evolution of the base paired configurations of mixtures of oligonucleotides over time. Although much attention has been focused on the thermodynamics of DNA and RNA base pairing in the scientific literature, much less work has been done on the time dependence of interactions involving multiple strands, especially in RNA. Here we provide a study of oligoribonucleotide interaction kinetics and show that it is possible to calculate the association, dissociation and strand displacement rates displayed by short oligonucleotides (5nt–12nt) that exhibit no expected secondary structure as simple functions of oligonucleotide length, CG content, ΔG of hybridization and ΔG of toehold binding. We then show that the resultant calculated kinetic parameters are consistent with the experimentally observed time dependent changes in concentrations of the different species present in mixtures of multiple competing RNA strands. We show that by changing the mixture composition, it is possible to create and tune kinetic traps that extend by orders of magnitude the typical sub-second hybridization timescale of two complementary oligonucleotides. We suggest that the slow equilibration of complex oligonucleotide mixtures may have facilitated the nonenzymatic replication of RNA during the origin of life. 
    more » « less