18 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.30.2
Domain-Based Nucleic-Acid Minimum Free Energy: Algorithmic Hardness and Parameterized Bounds

Authors: Erik D. Demaine, Timothy Gomez, Elise Grizzell, Markus Hecher, Jayson Lynch, Robert Schweller, Ahmed Shalaby, and Damien Woods

Published in: LIPIcs, Volume 314, 30th International Conference on DNA Computing and Molecular Programming (DNA 30) (2024)

Abstract
Molecular programmers and nanostructure engineers use domain-level design to abstract away messy DNA/RNA sequence, chemical and geometric details. Such domain-level abstractions are enforced by sequence design principles and provide a key principle that allows scaling up of complex multistranded DNA/RNA programs and structures. Determining the most favoured secondary structure, or Minimum Free Energy (MFE), of a set of strands, is typically studied at the sequence level but has seen limited domain-level work. We analyse the computational complexity of MFE for multistranded systems in a simple setting were we allow only 1 or 2 domains per strand. On the one hand, with 2-domain strands, we find that the MFE decision problem is NP-complete, even without pseudoknots, and requires exponential time algorithms assuming SAT does. On the other hand, in the simplest case of 1-domain strands there are efficient MFE algorithms for various binding modes. However, even in this single-domain case, MFE is P-hard for promiscuous binding, where one domain may bind to multiple as experimentally used by Nikitin [Nat Chem., 2023], which in turn implies that strands consisting of a single domain efficiently implement arbitrary Boolean circuits.
Cite as

Erik D. Demaine, Timothy Gomez, Elise Grizzell, Markus Hecher, Jayson Lynch, Robert Schweller, Ahmed Shalaby, and Damien Woods. Domain-Based Nucleic-Acid Minimum Free Energy: Algorithmic Hardness and Parameterized Bounds. In 30th International Conference on DNA Computing and Molecular Programming (DNA 30). Leibniz International Proceedings in Informatics (LIPIcs), Volume 314, pp. 2:1-2:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.DNA.30.2,
  author =	{Demaine, Erik D. and Gomez, Timothy and Grizzell, Elise and Hecher, Markus and Lynch, Jayson and Schweller, Robert and Shalaby, Ahmed and Woods, Damien},
  title =	{{Domain-Based Nucleic-Acid Minimum Free Energy: Algorithmic Hardness and Parameterized Bounds}},
  booktitle =	{30th International Conference on DNA Computing and Molecular Programming (DNA 30)},
  pages =	{2:1--2:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-344-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{314},
  editor =	{Seki, Shinnosuke and Stewart, Jaimie Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.30.2},
  URN =		{urn:nbn:de:0030-drops-209304},
  doi =		{10.4230/LIPIcs.DNA.30.2},
  annote =	{Keywords: Domain-based DNA designs, minimum free energy, efficient algorithms, NP-hard, P-hard, NC, fixed-parameter tractable}
}
Document
DOI: 10.4230/LIPIcs.DNA.30.4
Designing 3D RNA Origami Nanostructures with a Minimum Number of Kissing Loops

Authors: Antti Elonen and Pekka Orponen

Published in: LIPIcs, Volume 314, 30th International Conference on DNA Computing and Molecular Programming (DNA 30) (2024)

Abstract
We present a general design technique for rendering any 3D wireframe model, that is any connected graph linearly embedded in 3D space, as an RNA origami nanostructure with a minimum number of kissing loops. The design algorithm, which applies some ideas and methods from topological graph theory, produces renderings that contain at most one kissing-loop pair for many interesting model families, including for instance all fully triangulated wireframes and the wireframes of all Platonic solids. The design method is already implemented and available for use in the design tool DNAforge (https://dnaforge.org).
Cite as

Antti Elonen and Pekka Orponen. Designing 3D RNA Origami Nanostructures with a Minimum Number of Kissing Loops. In 30th International Conference on DNA Computing and Molecular Programming (DNA 30). Leibniz International Proceedings in Informatics (LIPIcs), Volume 314, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{elonen_et_al:LIPIcs.DNA.30.4,
  author =	{Elonen, Antti and Orponen, Pekka},
  title =	{{Designing 3D RNA Origami Nanostructures with a Minimum Number of Kissing Loops}},
  booktitle =	{30th International Conference on DNA Computing and Molecular Programming (DNA 30)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-344-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{314},
  editor =	{Seki, Shinnosuke and Stewart, Jaimie Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.30.4},
  URN =		{urn:nbn:de:0030-drops-209325},
  doi =		{10.4230/LIPIcs.DNA.30.4},
  annote =	{Keywords: RNA origami, wireframe nanostructures, polyhedra, kissing loops, topological graph embeddings, self-assembly}
}
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}
}
Document
DOI: 10.4230/LIPIcs.DNA.2020.9
scadnano: A Browser-Based, Scriptable Tool for Designing DNA Nanostructures

Authors: David Doty, Benjamin L Lee, and Tristan Stérin

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

Abstract
We introduce scadnano (short for "scriptable cadnano"), a computational tool for designing synthetic DNA structures. Its design is based heavily on cadnano [Douglas et al., 2009], the most widely-used software for designing DNA origami [Paul W. K. Rothemund, 2006], with three main differences: 1) scadnano runs entirely in the browser, with no software installation required. 2) scadnano designs, while they can be edited manually, can also be created and edited by a well-documented Python scripting library, to help automate tedious tasks. 3) The scadnano file format is easily human-readable. This goal is closely aligned with the scripting library, intended to be helpful when debugging scripts or interfacing with other software. The format is also somewhat more expressive than that of cadnano, able to describe a broader range of DNA structures than just DNA origami.
Cite as

David Doty, Benjamin L Lee, and Tristan Stérin. scadnano: A Browser-Based, Scriptable Tool for Designing DNA Nanostructures. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{doty_et_al:LIPIcs.DNA.2020.9,
  author =	{Doty, David and Lee, Benjamin L and St\'{e}rin, Tristan},
  title =	{{scadnano: A Browser-Based, Scriptable Tool for Designing DNA Nanostructures}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{9:1--9: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.9},
  URN =		{urn:nbn:de:0030-drops-129624},
  doi =		{10.4230/LIPIcs.DNA.2020.9},
  annote =	{Keywords: computer-aided design, structural DNA nanotechnology, DNA origami}
}
Document
DOI: 10.4230/LIPIcs.DNA.2020.10
Verification and Computation in Restricted Tile Automata

Authors: David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie

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

Abstract
Many models of self-assembly have been shown to be capable of performing computation. Tile Automata was recently introduced combining features of both Celluar Automata and the 2-Handed Model of self-assembly both capable of universal computation. In this work we study the complexity of Tile Automata utilizing features inherited from the two models mentioned above. We first present a construction for simulating Turing Machines that performs both covert and fuel efficient computation. We then explore the capabilities of limited Tile Automata systems such as 1-Dimensional systems (all assemblies are of height 1) and freezing Systems (tiles may not repeat states). Using these results we provide a connection between the problem of finding the largest uniquely producible assembly using n states and the busy beaver problem for non-freezing systems and provide a freezing system capable of uniquely assembling an assembly whose length is exponential in the number of states of the system. We finish by exploring the complexity of the Unique Assembly Verification problem in Tile Automata with different limitations such as freezing and systems without the power of detachment.
Cite as

David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie. Verification and Computation in Restricted Tile Automata. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{caballero_et_al:LIPIcs.DNA.2020.10,
  author =	{Caballero, David and Gomez, Timothy and Schweller, Robert and Wylie, Tim},
  title =	{{Verification and Computation in Restricted Tile Automata}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{10:1--10: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.10},
  URN =		{urn:nbn:de:0030-drops-129635},
  doi =		{10.4230/LIPIcs.DNA.2020.10},
  annote =	{Keywords: Tile Automata, Turing Machines, Unique Assembly Verification}
}
  • Refine by Author
  • 4 Geary, Cody
  • 2 Gomez, Timothy
  • 2 Lathrop, James I.
  • 2 Patitz, Matthew J.
  • 2 Potter, Hugh D.
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Models of computation
  • 3 Computer systems organization → Molecular computing
  • 3 Hardware → Biology-related information processing
  • 2 Applied computing → Biological networks
  • 2 Applied computing → Life and medical sciences
  • Show More...

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

  • Refine by Type
  • 17 document
  • 1 volume

  • Refine by Publication Year
  • 14 2020
  • 2 2024
  • 1 2016
  • 1 2018

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 Imprint Privacy Contact