20 Search Results for "Geary, Cody"

Volume

LIPIcs, Volume 174

26th International Conference on DNA Computing and Molecular Programming (DNA 26)

DNA 26, September 14-17, 2020, Oxford, UK (Virtual Conference)

Editors: Cody Geary and Matthew J. Patitz

Document
DOI: 10.4230/LIPIcs.DNA.31.2
A Coupled Reconfiguration Mechanism That Enables Powerful, Pseudoknot-Robust DNA Strand Displacement Devices with 2-Stranded Inputs

Authors: Hope Amber Johnson and Anne Condon

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
DNA strand displacement, a collective name for certain behaviors of short strands of DNA, has been used to build many interesting molecular devices over the past few decades. Among those devices are general implementation schemes for Chemical Reaction Networks, suggesting a place in an abstraction hierarchy for complex molecular programming. However, the possibilities of DNA strand displacement are far from fully explored. On a theoretical level, most DNA strand displacement systems are built out of a few simple motifs, with the space of possible motifs otherwise unexplored. On a practical level, the desire for general, large-scale DNA strand displacement systems is not fulfilled. Those systems that are scalable are not general, and those that are general don't scale up well. We have recently been exploring the space of possibilities for DNA strand displacement systems where all input complexes are made out of at most two strands of DNA. As a test case, we've had an open question of whether such systems can implement general Chemical Reaction Networks, in a way that has a certain set of other desirable properties - reversible, systematic, O(1) toeholds, bimolecular reactions, and correct according to CRN bisimulation - that the state-of-the-art implementations with more than 2-stranded inputs have. Until now we've had a few results that have all but one of those desirable properties, including one based on a novel mechanism we called coupled reconfiguration, but that depended on the physically questionable assumption that pseudoknots cannot occur. We wondered whether the same type of mechanism could be done in a pseudoknot-robust way. In this work we show that in fact, coupled reconfiguration can be done in a pseudoknot-robust way, and this mechanism can implement general Chemical Reaction Networks with all inputs being single strands of DNA. Going further, the same motifs used in this mechanism can implement stacks and surface-based bimolecular reactions. Those have been previously studied as part of polymer extensions of the Chemical Reaction Network model, and on an abstract model level, the resulting extensions are Turing-complete in ways the base Chemical Reaction Network model is not. Our mechanisms are significantly different from previously tested DNA strand displacement systems, which raises questions about their ability to be implemented experimentally, but we have some reasons to believe the challenges are solvable. So we present the pseudoknot-robust coupled reconfiguration mechanism and its use for general Chemical Reaction Network implementations; we present the extensions of the mechanism to stack and surface reactions; and we discuss the possible obstacles and solutions to experimental implementation, as well as the theoretical implications of this mechanism.
Cite as

Hope Amber Johnson and Anne Condon. A Coupled Reconfiguration Mechanism That Enables Powerful, Pseudoknot-Robust DNA Strand Displacement Devices with 2-Stranded Inputs. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{johnson_et_al:LIPIcs.DNA.31.2,
  author =	{Johnson, Hope Amber and Condon, Anne},
  title =	{{A Coupled Reconfiguration Mechanism That Enables Powerful, Pseudoknot-Robust DNA Strand Displacement Devices with 2-Stranded Inputs}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.2},
  URN =		{urn:nbn:de:0030-drops-238514},
  doi =		{10.4230/LIPIcs.DNA.31.2},
  annote =	{Keywords: Molecular programming, DNA strand displacement, Chemical Reaction Networks}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.5
Programmable Co‑Transcriptional Splicing: Realizing Regular Languages via Hairpin Deletion

Authors: Da-Jung Cho, Szilárd Zsolt Fazekas, Shinnosuke Seki, and Max Wiedenhöft

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
RNA co-transcriptionality, where RNA is spliced or folded during transcription from DNA templates, offers promising potential for molecular programming. It enables programmable folding of nanoscale RNA structures and has recently been shown to be Turing universal. While post-transcriptional splicing is well studied, co-transcriptional splicing is gaining attention for its efficiency, though its unpredictability still remains a challenge. In this paper, we focus on engineering co-transcriptional splicing, not only as a natural phenomenon but as a programmable mechanism for generating specific RNA target sequences from DNA templates. The problem we address is whether we can encode a set of RNA sequences for a given system onto a DNA template word, ensuring that all the sequences are generated through co-transcriptional splicing. Given that finding the optimal encoding has been shown to be NP-complete under the various energy models considered [Da-Jung Cho et al., 2025], we propose a practical alternative approach under the logarithmic energy model. More specifically, we provide a construction that encodes an arbitrary nondeterministic finite automaton (NFA) into a circular DNA template from which co-transcriptional splicing produces all sequences accepted by the NFA. As all finite languages can be efficiently encoded as NFA, this framework solves the problem of finding small DNA templates for arbitrary target sets of RNA sequences. The quest to obtain the smallest possible such templates naturally leads us to consider the problem of minimizing NFAs and certain practically motivated variants of it, but as we show, those minimization problems are computationally intractable.
Cite as

Da-Jung Cho, Szilárd Zsolt Fazekas, Shinnosuke Seki, and Max Wiedenhöft. Programmable Co‑Transcriptional Splicing: Realizing Regular Languages via Hairpin Deletion. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cho_et_al:LIPIcs.DNA.31.5,
  author =	{Cho, Da-Jung and Fazekas, Szil\'{a}rd Zsolt and Seki, Shinnosuke and Wiedenh\"{o}ft, Max},
  title =	{{Programmable Co‑Transcriptional Splicing: Realizing Regular Languages via Hairpin Deletion}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{5:1--5:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.5},
  URN =		{urn:nbn:de:0030-drops-238548},
  doi =		{10.4230/LIPIcs.DNA.31.5},
  annote =	{Keywords: RNA Transcription, Co-Transcriptional Splicing, Finite Automata Simulation, NFA Minimization}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.6
Secondary Structure Design for Cotranscriptional 3D RNA Origami Wireframes

Authors: Pekka Orponen, Shinnosuke Seki, and Antti Elonen

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
We address the task of secondary structure design for de novo 3D RNA origami wireframe structures in a way that takes into account the specifics of a cotranscriptional folding setting. We consider two issues: firstly, avoiding the topological obstacle of "polymerase trapping", where some helical domain cannot be hybridised due to a closed kissing-loop pair blocking the winding of the strand relative to the polymerase-DNA-template complex; and secondly, minimising the number of distinct kissing-loop designs needed, by reusing KL pairs that have already been hybridised in the folding process. For the first task, we present an efficient strand-routing method that guarantees the absence of polymerase traps for any 3D wireframe model, and for the second task, we provide a graph-theoretic formulation of the minimisation problem, show that it is NP-complete in the general case, and outline a branch-and-bound type enumerative approach to solving it. Key concepts in both cases are depth-first search in graphs and the ensuing DFS spanning trees. Both algorithms have been implemented in the DNAforge design tool (https://dnaforge.org) and we present some examples of the results.
Cite as

Pekka Orponen, Shinnosuke Seki, and Antti Elonen. Secondary Structure Design for Cotranscriptional 3D RNA Origami Wireframes. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{orponen_et_al:LIPIcs.DNA.31.6,
  author =	{Orponen, Pekka and Seki, Shinnosuke and Elonen, Antti},
  title =	{{Secondary Structure Design for Cotranscriptional 3D RNA Origami Wireframes}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.6},
  URN =		{urn:nbn:de:0030-drops-238558},
  doi =		{10.4230/LIPIcs.DNA.31.6},
  annote =	{Keywords: RNA origami, wireframe nanostructures, cotranscriptional folding, secondary structure, kissing loops, algorithms, self-assembly}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.130
An Efficient Algorithm to Compute the Minimum Free Energy of Interacting Nucleic Acid Strands

Authors: Ahmed Shalaby and Damien Woods

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
The information-encoding molecules RNA and DNA bind via base pairing to form an exponentially large set of secondary structures. Practitioners need algorithms to predict the most favoured structures, called minimum free energy (MFE) structures, or to compute a partition function that allows assigning a probability to any structure. MFE prediction is NP-hard in the presence pseudoknots - base pairings that violate a restricted planarity condition. However, for single-stranded unpseudoknotted structures, there are polynomial time dynamic programming algorithms. For multiple strands, the problem is significantly more complicated: Codon, Hajiaghayi and Thachuk [DNA27, 2021] proved it NP-hard for N bases and 𝒪(N) strands. Dirks, Bois, Schaeffer, Winfree and Pierce [SIAM Review, 2007] gave a polynomial time partition function algorithm for multiple (𝒪(1)) strands, now widely-used, however their technique did not generalise to MFE which they left open. We give an 𝒪(N⁴) time algorithm for unpseudoknotted multiple (𝒪(1)) strand MFE prediction, answering the open problem from Dirks et al. The challenge lies in considering the rotational symmetry of secondary structures, a global feature not immediately amenable to local subproblem decomposition used in dynamic programming. Our proof has two main technical contributions: First, a characterisation of symmetric secondary structures implying only quadratically many need to be considered when computing the rotational symmetry penalty. Second, that bound is leveraged by a backtracking algorithm to efficiently find the MFE in an exponential space of contenders.
Cite as

Ahmed Shalaby and Damien Woods. An Efficient Algorithm to Compute the Minimum Free Energy of Interacting Nucleic Acid Strands. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 130:1-130:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{shalaby_et_al:LIPIcs.ICALP.2025.130,
  author =	{Shalaby, Ahmed and Woods, Damien},
  title =	{{An Efficient Algorithm to Compute the Minimum Free Energy of Interacting Nucleic Acid Strands}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{130:1--130:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.130},
  URN =		{urn:nbn:de:0030-drops-235071},
  doi =		{10.4230/LIPIcs.ICALP.2025.130},
  annote =	{Keywords: Minimum free energy, MFE, partition function, nucleic acid, DNA, RNA, secondary structure, computational complexity, algorithm analysis and design, dynamic programming}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.DNA.2020
LIPIcs, Volume 174, DNA 26, Complete Volume

Authors: Cody Geary and Matthew J. Patitz

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

Abstract
LIPIcs, Volume 174, DNA 26, Complete Volume
Cite as

26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 1-230, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{geary_et_al:LIPIcs.DNA.2020,
  title =	{{LIPIcs, Volume 174, DNA 26, Complete Volume}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{1--230},
  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},
  URN =		{urn:nbn:de:0030-drops-129529},
  doi =		{10.4230/LIPIcs.DNA.2020},
  annote =	{Keywords: LIPIcs, Volume 174, DNA 26, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.DNA.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Cody Geary and Matthew J. Patitz

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{geary_et_al:LIPIcs.DNA.2020.0,
  author =	{Geary, Cody and Patitz, Matthew J.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{0:i--0:xiv},
  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.0},
  URN =		{urn:nbn:de:0030-drops-129533},
  doi =		{10.4230/LIPIcs.DNA.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.DNA.2020.1
The Topology of Scaffold Routings on Non-Spherical Mesh Wireframes

Authors: Abdulmelik Mohammed, Nataša Jonoska, and Masahico Saito

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

Abstract
The routing of a DNA-origami scaffold strand is often modelled as an Eulerian circuit of an Eulerian graph in combinatorial models of DNA origami design. The knot type of the scaffold strand dictates the feasibility of an Eulerian circuit to be used as the scaffold route in the design. Motivated by the topology of scaffold routings in 3D DNA origami, we investigate the knottedness of Eulerian circuits on surface-embedded graphs. We show that certain graph embeddings, checkerboard colorable, always admit unknotted Eulerian circuits. On the other hand, we prove that if a graph admits an embedding in a torus that is not checkerboard colorable, then it can be re-embedded so that all its non-intersecting Eulerian circuits are knotted. For surfaces of genus greater than one, we present an infinite family of checkerboard-colorable graph embeddings where there exist knotted Eulerian circuits.
Cite as

Abdulmelik Mohammed, Nataša Jonoska, and Masahico Saito. The Topology of Scaffold Routings on Non-Spherical Mesh Wireframes. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{mohammed_et_al:LIPIcs.DNA.2020.1,
  author =	{Mohammed, Abdulmelik and Jonoska, Nata\v{s}a and Saito, Masahico},
  title =	{{The Topology of Scaffold Routings on Non-Spherical Mesh Wireframes}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{1:1--1:17},
  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.1},
  URN =		{urn:nbn:de:0030-drops-129540},
  doi =		{10.4230/LIPIcs.DNA.2020.1},
  annote =	{Keywords: DNA origami, Scaffold routing, Graphs, Surfaces, Knots, Eulerian circuits}
}
Document
DOI: 10.4230/LIPIcs.DNA.2020.2
Simplifying Chemical Reaction Network Implementations with Two-Stranded DNA Building Blocks

Authors: Robert F. Johnson and Lulu Qian

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

Abstract
In molecular programming, the Chemical Reaction Network model is often used to describe real or hypothetical systems. Often, an interesting computational task can be done with a known hypothetical Chemical Reaction Network, but often such networks have no known physical implementation. One of the important breakthroughs in the field was that any Chemical Reaction Network can be physically implemented, approximately, using DNA strand displacement mechanisms. This allows us to treat the Chemical Reaction Network model as a programming language and the implementation schemes as its compiler. This also suggests that it would be useful to optimize the result of such a compilation, and in general to find effective ways to design better DNA strand displacement systems. We discuss DNA strand displacement systems in terms of "motifs", short sequences of elementary DNA strand displacement reactions. We argue that describing such motifs in terms of their inputs and outputs, then building larger systems out of the abstracted motifs, can be an efficient way of designing DNA strand displacement systems. We discuss four previously studied motifs in this abstracted way, and present a new motif based on cooperative 4-way strand exchange. We then show how Chemical Reaction Network implementations can be built out of abstracted motifs, discussing existing implementations as well as presenting two new implementations based on 4-way strand exchange, one of which uses the new cooperative motif. The new implementations both have two desirable properties not found in existing implementations, namely both use only at most 2-stranded DNA complexes for signal and fuel complexes and both are physically reversible. There are reasons to believe that those properties may make them more robust and energy-efficient, but at the expense of using more fuel complexes than existing implementation schemes.
Cite as

Robert F. Johnson and Lulu Qian. Simplifying Chemical Reaction Network Implementations with Two-Stranded DNA Building Blocks. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{johnson_et_al:LIPIcs.DNA.2020.2,
  author =	{Johnson, Robert F. and Qian, Lulu},
  title =	{{Simplifying Chemical Reaction Network Implementations with Two-Stranded DNA Building Blocks}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{2:1--2:14},
  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.2},
  URN =		{urn:nbn:de:0030-drops-129557},
  doi =		{10.4230/LIPIcs.DNA.2020.2},
  annote =	{Keywords: Molecular programming, DNA computing, Chemical Reaction Networks, DNA strand displacement}
}
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.DNA.2020.4
CRNs Exposed: A Method for the Systematic Exploration of Chemical Reaction Networks

Authors: Marko Vasic, David Soloveichik, and Sarfraz Khurshid

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

Abstract
Formal methods have enabled breakthroughs in many fields, such as in hardware verification, machine learning and biological systems. The key object of interest in systems biology, synthetic biology, and molecular programming is chemical reaction networks (CRNs) which formalizes coupled chemical reactions in a well-mixed solution. CRNs are pivotal for our understanding of biological regulatory and metabolic networks, as well as for programming engineered molecular behavior. Although it is clear that small CRNs are capable of complex dynamics and computational behavior, it remains difficult to explore the space of CRNs in search for desired functionality. We use Alloy, a tool for expressing structural constraints and behavior in software systems, to enumerate CRNs with declaratively specified properties. We show how this framework can enumerate CRNs with a variety of structural constraints including biologically motivated catalytic networks and metabolic networks, and seesaw networks motivated by DNA nanotechnology. We also use the framework to explore analog function computation in rate-independent CRNs. By computing the desired output value with stoichiometry rather than with reaction rates (in the sense that X → Y+Y computes multiplication by 2), such CRNs are completely robust to the choice of reaction rates or rate law. We find the smallest CRNs computing the max, minmax, abs and ReLU (rectified linear unit) functions in a natural subclass of rate-independent CRNs where rate-independence follows from structural network properties.
Cite as

Marko Vasic, David Soloveichik, and Sarfraz Khurshid. CRNs Exposed: A Method for the Systematic Exploration of Chemical Reaction Networks. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 4:1-4:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{vasic_et_al:LIPIcs.DNA.2020.4,
  author =	{Vasic, Marko and Soloveichik, David and Khurshid, Sarfraz},
  title =	{{CRNs Exposed: A Method for the Systematic Exploration of Chemical Reaction Networks}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{4:1--4:25},
  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.4},
  URN =		{urn:nbn:de:0030-drops-129574},
  doi =		{10.4230/LIPIcs.DNA.2020.4},
  annote =	{Keywords: molecular programming, formal methods}
}
Document
DOI: 10.4230/LIPIcs.DNA.2020.5
Population-Induced Phase Transitions and the Verification of Chemical Reaction Networks

Authors: James I. Lathrop, Jack H. Lutz, Robyn R. Lutz, Hugh D. Potter, and Matthew R. Riley

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

Abstract
We show that very simple molecular systems, modeled as chemical reaction networks, can have behaviors that exhibit dramatic phase transitions at certain population thresholds. Moreover, the magnitudes of these thresholds can thwart attempts to use simulation, model checking, or approximation by differential equations to formally verify the behaviors of such systems at realistic populations. We show how formal theorem provers can successfully verify some such systems at populations where other verification methods fail.
Cite as

James I. Lathrop, Jack H. Lutz, Robyn R. Lutz, Hugh D. Potter, and Matthew R. Riley. Population-Induced Phase Transitions and the Verification of Chemical Reaction Networks. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lathrop_et_al:LIPIcs.DNA.2020.5,
  author =	{Lathrop, James I. and Lutz, Jack H. and Lutz, Robyn R. and Potter, Hugh D. and Riley, Matthew R.},
  title =	{{Population-Induced Phase Transitions and the Verification of Chemical Reaction Networks}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{5:1--5:17},
  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.5},
  URN =		{urn:nbn:de:0030-drops-129583},
  doi =		{10.4230/LIPIcs.DNA.2020.5},
  annote =	{Keywords: chemical reaction networks, molecular programming, phase transitions, population protocols, verification}
}
Document
DOI: 10.4230/LIPIcs.DNA.2020.6
ALCH: An Imperative Language for Chemical Reaction Network-Controlled Tile Assembly

Authors: Titus H. Klinge, James I. Lathrop, Sonia Moreno, Hugh D. Potter, Narun K. Raman, and Matthew R. Riley

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

Abstract
In 2015 Schiefer and Winfree introduced the chemical reaction network-controlled tile assembly model (CRN-TAM), a variant of the abstract tile assembly model (aTAM), where tile reactions are mediated via non-local chemical signals. In this paper, we introduce ALCH, an imperative programming language for specifying CRN-TAM programs. ALCH contains common features like Boolean variables, conditionals, and loops. It also supports CRN-TAM-specific features such as adding and removing tiles. A unique feature of the language is the branch statement, a nondeterministic control structure that allows us to query the current state of tile assemblies. We also developed a compiler that translates ALCH to the CRN-TAM, and a simulator that simulates and visualizes the self-assembly of a CRN-TAM program. Using this language, we show that the discrete Sierpinski triangle can be strictly self-assembled in the CRN-TAM. This solves an open problem that the CRN-TAM is capable of self-assembling infinite shapes at scale one that the aTAM cannot. ALCH allows us to present this construction at a high level, abstracting species and reactions into C-like code that is simpler to understand. Our construction utilizes two new CRN-TAM techniques that allow us to tackle this open problem. First, it employs the branching feature of ALCH to probe the previously placed tiles of the assembly and detect the presence and absence of tiles. Second, it uses scaffolding tiles to precisely control tile placement by occluding any undesired binding sites.
Cite as

Titus H. Klinge, James I. Lathrop, Sonia Moreno, Hugh D. Potter, Narun K. Raman, and Matthew R. Riley. ALCH: An Imperative Language for Chemical Reaction Network-Controlled Tile Assembly. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{klinge_et_al:LIPIcs.DNA.2020.6,
  author =	{Klinge, Titus H. and Lathrop, James I. and Moreno, Sonia and Potter, Hugh D. and Raman, Narun K. and Riley, Matthew R.},
  title =	{{ALCH: An Imperative Language for Chemical Reaction Network-Controlled Tile Assembly}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{6:1--6:22},
  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.6},
  URN =		{urn:nbn:de:0030-drops-129592},
  doi =		{10.4230/LIPIcs.DNA.2020.6},
  annote =	{Keywords: Tile assembly, Chemical reaction network, Sierpinski triangle}
}
Document
DOI: 10.4230/LIPIcs.DNA.2020.7
Implementing Non-Equilibrium Networks with Active Circuits of Duplex Catalysts

Authors: Antti Lankinen, Ismael Mullor Ruiz, and Thomas E. Ouldridge

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

Abstract
DNA strand displacement (DSD) reactions have been used to construct chemical reaction networks in which species act catalytically at the level of the overall stoichiometry of reactions. These effective catalytic reactions are typically realised through one or more of the following: many-stranded gate complexes to coordinate the catalysis, indirect interaction between the catalyst and its substrate, and the recovery of a distinct "catalyst" strand from the one that triggered the reaction. These facts make emulation of the out-of-equilibrium catalytic circuitry of living cells more difficult. Here, we propose a new framework for constructing catalytic DSD networks: Active Circuits of Duplex Catalysts (ACDC). ACDC components are all double-stranded complexes, with reactions occurring through 4-way strand exchange. Catalysts directly bind to their substrates, and the "identity" strand of the catalyst recovered at the end of a reaction is the same molecule as the one that initiated it. We analyse the capability of the framework to implement catalytic circuits analogous to phosphorylation networks in living cells. We also propose two methods of systematically introducing mismatches within DNA strands to avoid leak reactions and introduce driving through net base pair formation. We then combine these results into a compiler to automate the process of designing DNA strands that realise any catalytic network allowed by our framework.
Cite as

Antti Lankinen, Ismael Mullor Ruiz, and Thomas E. Ouldridge. Implementing Non-Equilibrium Networks with Active Circuits of Duplex Catalysts. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 7:1-7:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lankinen_et_al:LIPIcs.DNA.2020.7,
  author =	{Lankinen, Antti and Mullor Ruiz, Ismael and Ouldridge, Thomas E.},
  title =	{{Implementing Non-Equilibrium Networks with Active Circuits of Duplex Catalysts}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{7:1--7:25},
  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.7},
  URN =		{urn:nbn:de:0030-drops-129602},
  doi =		{10.4230/LIPIcs.DNA.2020.7},
  annote =	{Keywords: DNA strand displacement, Catalysis, Information-processing networks}
}
Document
DOI: 10.4230/LIPIcs.DNA.2020.8
Design Automation of Polyomino Set That Self-Assembles into a Desired Shape

Authors: Yuta Matsumura, Ibuki Kawamata, and Satoshi Murata

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

Abstract
The problem of finding the smallest DNA tile set that self-assembles into a desired pattern or shape is a research focus that has been investigated by many researchers. In this paper, we take a polyomino, which is a non-square element composed of several connected square units, as an element of assembly and consider the design problem of the minimal set of polyominoes that self-assembles into a desired shape. We developed a self-assembly simulator of polyominoes based on the agent-based Monte Carlo method, in which the potential energy among the polyominoes is evaluated and the simulation state is updated toward the direction to decrease the total potential. Aggregated polyominoes are represented as an agent, which can move, merge, and split during the simulation. In order to search the minimal set of polyominoes, two-step evaluation strategy is adopted, because of enormous search space including many parameters such as the shape, the size, and the glue types attached to the polyominoes. The feasibility of the proposed method is shown through three examples with different size and complexity.
Cite as

Yuta Matsumura, Ibuki Kawamata, and Satoshi Murata. Design Automation of Polyomino Set That Self-Assembles into a Desired Shape. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{matsumura_et_al:LIPIcs.DNA.2020.8,
  author =	{Matsumura, Yuta and Kawamata, Ibuki and Murata, Satoshi},
  title =	{{Design Automation of Polyomino Set That Self-Assembles into a Desired Shape}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{8:1--8:15},
  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.8},
  URN =		{urn:nbn:de:0030-drops-129614},
  doi =		{10.4230/LIPIcs.DNA.2020.8},
  annote =	{Keywords: DNA polyomino, DNA nanostructure, DNA tile, Agent based simulation, Self-assembly, Combinatorial optimization, Simulated annealing}
}
  • Refine by Type
  • 19 Document/PDF
  • 4 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 4 2025
  • 14 2020
  • 1 2018
  • 1 2016

  • Refine by Author
  • 4 Geary, Cody
  • 4 Seki, Shinnosuke
  • 2 Condon, Anne
  • 2 Lathrop, James I.
  • 2 Patitz, Matthew J.
  • Show More...

  • Refine by Series/Journal
  • 19 LIPIcs

  • Refine by Classification
  • 6 Theory of computation → Models of computation
  • 3 Hardware → Biology-related information processing
  • 2 Applied computing → Biological networks
  • 2 Applied computing → Chemistry
  • 2 Applied computing → Molecular structural biology
  • Show More...

  • Refine by Keyword
  • 3 Chemical Reaction Networks
  • 3 DNA strand displacement
  • 3 self-assembly
  • 2 DNA origami
  • 2 Molecular programming
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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