Search Results

Documents authored by Condon, Anne

Document
DOI: 10.4230/LIPIcs.DNA.29.3
On the Runtime of Chemical Reaction Networks Beyond Idealized Conditions

Authors: Anne Condon, Yuval Emek, and Noga Harlev

Published in: LIPIcs, Volume 276, 29th International Conference on DNA Computing and Molecular Programming (DNA 29) (2023)

Abstract
This paper studies the (discrete) chemical reaction network (CRN) computational model that emerged in the last two decades as an abstraction for molecular programming. The correctness of CRN protocols is typically established under one of two possible schedulers that determine how the execution advances: (1) a stochastic scheduler that obeys the (continuous time) Markov process dictated by the standard model of stochastic chemical kinetics; or (2) an adversarial scheduler whose only commitment is to maintain a certain fairness condition. The latter scheduler is justified by the fact that the former one crucially assumes "idealized conditions" that more often than not, do not hold in real wet-lab experiments. However, when it comes to analyzing the runtime of CRN protocols, the existing literature focuses strictly on the stochastic scheduler, thus raising the research question that drives this work: Is there a meaningful way to quantify the runtime of CRNs without the idealized conditions assumption? The main conceptual contribution of the current paper is to answer this question in the affirmative, formulating a new runtime measure for CRN protocols that does not rely on idealized conditions. This runtime measure is based on an adapted (weaker) fairness condition as well as a novel scheme that enables partitioning the execution into short rounds and charging the runtime for each round individually (inspired by definitions for the runtime of asynchronous distributed algorithms). Following that, we turn to investigate various fundamental computational tasks and establish (often tight) bounds on the runtime of the corresponding CRN protocols operating under the adversarial scheduler. This includes an almost complete chart of the runtime complexity landscape of predicate decidability tasks.
Cite as

Anne Condon, Yuval Emek, and Noga Harlev. On the Runtime of Chemical Reaction Networks Beyond Idealized Conditions. In 29th International Conference on DNA Computing and Molecular Programming (DNA 29). Leibniz International Proceedings in Informatics (LIPIcs), Volume 276, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{condon_et_al:LIPIcs.DNA.29.3,
  author =	{Condon, Anne and Emek, Yuval and Harlev, Noga},
  title =	{{On the Runtime of Chemical Reaction Networks Beyond Idealized Conditions}},
  booktitle =	{29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
  pages =	{3:1--3:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-297-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{276},
  editor =	{Chen, Ho-Lin and Evans, Constantine G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.3},
  URN =		{urn:nbn:de:0030-drops-187861},
  doi =		{10.4230/LIPIcs.DNA.29.3},
  annote =	{Keywords: chemical reaction networks, adversarial runtime, weak fairness, predicate decidability}
}
Document
DOI: 10.4230/LIPIcs.DNA.29.5
Revisiting Hybridization Kinetics with Improved Elementary Step Simulation

Authors: Jordan Lovrod, Boyan Beronov, Chenwei Zhang, Erik Winfree, and Anne Condon

Published in: LIPIcs, Volume 276, 29th International Conference on DNA Computing and Molecular Programming (DNA 29) (2023)

Abstract
Nucleic acid strands, which react by forming and breaking Watson-Crick base pairs, can be designed to form complex nanoscale structures or devices. Controlling such systems requires accurate predictions of the reaction rate and of the folding pathways of interacting strands. Simulators such as Multistrand model these kinetic properties using continuous-time Markov chains (CTMCs), whose states and transitions correspond to secondary structures and elementary base pair changes, respectively. The transient dynamics of a CTMC are determined by a kinetic model, which assigns transition rates to pairs of states, and the rate of a reaction can be estimated using the mean first passage time (MFPT) of its CTMC. However, use of Multistrand is limited by its slow runtime, particularly on rare events, and the quality of its rate predictions is compromised by a poorly-calibrated and simplistic kinetic model. The former limitation can be addressed by constructing truncated CTMCs, which only include a small subset of states and transitions, selected either manually or through simulation. As a first step to address the latter limitation, Bayesian posterior inference in an Arrhenius-type kinetic model was performed in earlier work, using a small experimental dataset of DNA reaction rates and a fixed set of manually truncated CTMCs, which we refer to as Assumed Pathway (AP) state spaces. In this work we extend this approach, by introducing a new prior model that is directly motivated by the physical meaning of the parameters and that is compatible with experimental measurements of elementary rates, and by using a larger dataset of 1105 reactions as well as larger truncated state spaces obtained from the recently introduced stochastic Pathway Elaboration (PE) method. We assess the quality of the resulting posterior distribution over kinetic parameters, as well as the quality of the posterior reaction rates predicted using AP and PE state spaces. Finally, we use the newly parameterised PE state spaces and Multistrand simulations to investigate the strong variation of helix hybridization reaction rates in a dataset of Hata et al. While we find strong evidence for the nucleation-zippering model of hybridization, in the classical sense that the rate-limiting phase is composed of elementary steps reaching a small "nucleus" of critical stability, the strongly sequence-dependent structure of the trajectory ensemble up to nucleation appears to be much richer than assumed in the model by Hata et al. In particular, rather than being dominated by the collision probability of nucleation sites, the trajectory segment between first binding and nucleation tends to visit numerous secondary structures involving misnucleation and hairpins, and has a sizeable effect on the probability of overcoming the nucleation barrier.
Cite as

Jordan Lovrod, Boyan Beronov, Chenwei Zhang, Erik Winfree, and Anne Condon. Revisiting Hybridization Kinetics with Improved Elementary Step Simulation. In 29th International Conference on DNA Computing and Molecular Programming (DNA 29). Leibniz International Proceedings in Informatics (LIPIcs), Volume 276, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lovrod_et_al:LIPIcs.DNA.29.5,
  author =	{Lovrod, Jordan and Beronov, Boyan and Zhang, Chenwei and Winfree, Erik and Condon, Anne},
  title =	{{Revisiting Hybridization Kinetics with Improved Elementary Step Simulation}},
  booktitle =	{29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-297-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{276},
  editor =	{Chen, Ho-Lin and Evans, Constantine G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.5},
  URN =		{urn:nbn:de:0030-drops-187889},
  doi =		{10.4230/LIPIcs.DNA.29.5},
  annote =	{Keywords: DNA reaction kinetics, kinetic model calibration, simulation-based Bayesian inference, continuous-time Markov chains}
}
Document
DOI: 10.4230/LIPIcs.DNA.28.3
A Coupled Reconfiguration Mechanism for Single-Stranded DNA Strand Displacement Systems

Authors: Hope Amber Johnson and Anne Condon

Published in: LIPIcs, Volume 238, 28th International Conference on DNA Computing and Molecular Programming (DNA 28) (2022)

Abstract
DNA Strand Displacement (DSD) systems model basic reaction rules, such as toehold-mediated strand displacement and 4-way branch migration, that modify complexes of bound DNA strands. DSD systems have been widely used to design and reason about the correctness of molecular programs, including implementations of logic circuits, neural networks, and Chemical Reaction Networks. Such implementations employ a valuable toolkit of mechanisms - sequences of basic reaction rules - that achieve catalysis, reduce errors (e.g., due to leak), or simulate simple computational units such as logic gates, both in solution and on surfaces. Expanding the DSD toolkit of DSD mechanisms can lead to new and better ways of programming with DNA. Here we introduce a new mechanism, which we call controlled reconfiguration. We describe one example where two single-stranded DSD complexes interact, changing the bonds in both complexes in a way that would not be possible for each independently on its own via the basic reaction rules allowed by the model. We use coupled reconfiguration to refer to instances of controlled reconfiguration in which two reactants change each other in this way. We note that our DSD model disallows pseudoknots and that properties of our coupled reconfiguration construction rely on this restriction of the model. A key feature of our coupled reconfiguration example, which distinguishes it from mechanisms (such as 3-way strand displacement or 4-way branch migration) that are typically used to implement molecular programs, is that the reactants are single-stranded. Leveraging this feature, we show how to use coupled reconfiguration to implement Chemical Reaction Networks (CRNs), with a DSD system that has both single-stranded signals (which represent the species of the CRN) and single-stranded fuels (which drive the CRN reactions). Our implementation also has other desirable properties; for example it is capable of implementing reversible CRNs and uses just two distinct toeholds. We discuss drawbacks of our implementation, particularly the reliance on pseudoknot-freeness for correctness, and suggest directions for future research that can provide further insight on the capabilities and limitations of controlled reconfiguration.
Cite as

Hope Amber Johnson and Anne Condon. A Coupled Reconfiguration Mechanism for Single-Stranded DNA Strand Displacement Systems. In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{johnson_et_al:LIPIcs.DNA.28.3,
  author =	{Johnson, Hope Amber and Condon, Anne},
  title =	{{A Coupled Reconfiguration Mechanism for Single-Stranded DNA Strand Displacement Systems}},
  booktitle =	{28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-253-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{238},
  editor =	{Ouldridge, Thomas E. and Wickham, Shelley F. J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.28.3},
  URN =		{urn:nbn:de:0030-drops-167889},
  doi =		{10.4230/LIPIcs.DNA.28.3},
  annote =	{Keywords: Molecular programming, DNA Strand Displacement, Chemical Reaction Networks}
}
Document
DOI: 10.4230/LIPIcs.DNA.27.9
Predicting Minimum Free Energy Structures of Multi-Stranded Nucleic Acid Complexes Is APX-Hard

Authors: Anne Condon, Monir Hajiaghayi, and Chris Thachuk

Published in: LIPIcs, Volume 205, 27th International Conference on DNA Computing and Molecular Programming (DNA 27) (2021)

Abstract
Given multiple nucleic acid strands, what is the minimum free energy (MFE) secondary structure that they can form? As interacting nucleic acid strands are the basis for DNA computing and molecular programming, e.g., in DNA self-assembly and DNA strand displacement systems, determining the MFE structure is an important step in the design and verification of these systems. Efficient dynamic programming algorithms are well known for predicting the MFE pseudoknot-free secondary structure of a single nucleic acid strand. In contrast, we prove that for a simple energy model, the problem of predicting the MFE pseudoknot-free secondary structure formed from multiple interacting nucleic acid strands is NP-hard and also APX-hard. The latter result implies that there does not exist a polynomial time approximation scheme for this problem, unless 𝖯 = NP, and it suggests that heuristic methods should be investigated.
Cite as

Anne Condon, Monir Hajiaghayi, and Chris Thachuk. Predicting Minimum Free Energy Structures of Multi-Stranded Nucleic Acid Complexes Is APX-Hard. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{condon_et_al:LIPIcs.DNA.27.9,
  author =	{Condon, Anne and Hajiaghayi, Monir and Thachuk, Chris},
  title =	{{Predicting Minimum Free Energy Structures of Multi-Stranded Nucleic Acid Complexes Is APX-Hard}},
  booktitle =	{27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-205-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{205},
  editor =	{Lakin, Matthew R. and \v{S}ulc, Petr},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.9},
  URN =		{urn:nbn:de:0030-drops-146765},
  doi =		{10.4230/LIPIcs.DNA.27.9},
  annote =	{Keywords: Nucleic Acid Secondary Structure Prediction, APX-Hardness, NP-Hardness}
}
Document
DOI: 10.4230/LIPIcs.DNA.2020.3
Composable Computation in Leaderless, Discrete Chemical Reaction Networks

Authors: Hooman Hashemi, Ben Chugg, and Anne Condon

Published in: LIPIcs, Volume 174, 26th International Conference on DNA Computing and Molecular Programming (DNA 26) (2020)

Abstract
We classify the functions f:ℕ^d → ℕ that are stably computable by leaderless, output-oblivious discrete (stochastic) Chemical Reaction Networks (CRNs). CRNs that compute such functions are systems of reactions over species that include d designated input species, whose initial counts represent an input x ∈ ℕ^d, and one output species whose eventual count represents f(x). Chen et al. showed that the class of functions computable by CRNs is precisely the semilinear functions. In output-oblivious CRNs, the output species is never a reactant. Output-oblivious CRNs are easily composable since a downstream CRN can consume the output of an upstream CRN without affecting its correctness. Severson et al. showed that output-oblivious CRNs compute exactly the subclass of semilinear functions that are eventually the minimum of quilt-affine functions, i.e., affine functions with different intercepts in each of finitely many congruence classes. They call such functions the output-oblivious functions. A leaderless CRN can compute only superadditive functions, and so a leaderless output-oblivious CRN can compute only superadditive, output-oblivious functions. In this work we show that a function f:ℕ^d → ℕ is stably computable by a leaderless, output-oblivious CRN if and only if it is superadditive and output-oblivious.
Cite as

Hooman Hashemi, Ben Chugg, and Anne Condon. Composable Computation in Leaderless, Discrete Chemical Reaction Networks. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hashemi_et_al:LIPIcs.DNA.2020.3,
  author =	{Hashemi, Hooman and Chugg, Ben and Condon, Anne},
  title =	{{Composable Computation in Leaderless, Discrete Chemical Reaction Networks}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-163-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{174},
  editor =	{Geary, Cody and Patitz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.2020.3},
  URN =		{urn:nbn:de:0030-drops-129560},
  doi =		{10.4230/LIPIcs.DNA.2020.3},
  annote =	{Keywords: Chemical Reaction Networks, Stable Function Computation, Output-Oblivious, Output-Monotonic}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.21
Output-Oblivious Stochastic Chemical Reaction Networks

Authors: Ben Chugg, Hooman Hashemi, and Anne Condon

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
We classify the functions f:N^2 -> N which are stably computable by output-oblivious Stochastic Chemical Reaction Networks (CRNs), i.e., systems of reactions in which output species are never reactants. While it is known that precisely the semilinear functions are stably computable by CRNs, such CRNs sometimes rely on initially producing too many output species, and then consuming the excess in order to reach a correct stable state. These CRNs may be difficult to integrate into larger systems: if the output of a CRN C becomes the input to a downstream CRN C', then C' could inadvertently consume too many outputs before C stabilizes. If, on the other hand, C is output-oblivious then C' may consume C's output as soon as it is available. In this work we prove that a semilinear function f:N^2 -> N is stably computable by an output-oblivious CRN with a leader if and only if it is both increasing and either grid-affine (intuitively, its domains are congruence classes), or the minimum of a finite set of fissure functions (intuitively, functions behaving like the min function).
Cite as

Ben Chugg, Hooman Hashemi, and Anne Condon. Output-Oblivious Stochastic Chemical Reaction Networks. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chugg_et_al:LIPIcs.OPODIS.2018.21,
  author =	{Chugg, Ben and Hashemi, Hooman and Condon, Anne},
  title =	{{Output-Oblivious Stochastic Chemical Reaction Networks}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.21},
  URN =		{urn:nbn:de:0030-drops-100815},
  doi =		{10.4230/LIPIcs.OPODIS.2018.21},
  annote =	{Keywords: Chemical Reaction Networks, Stable Function Computation, Output-Oblivious, Output-Monotonic}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact