Volume
LIPIcs, Volume 174
26th International Conference on DNA Computing and Molecular Programming (DNA 26)
Publication Details
- published at: 2020-09-04
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-163-4
- DBLP: db/conf/dna/dna2020
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 174, DNA 26, Complete Volume
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-dev.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
Front Matter, Table of Contents, Preface, Conference Organization
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-dev.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
The Topology of Scaffold Routings on Non-Spherical Mesh Wireframes
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-dev.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
Simplifying Chemical Reaction Network Implementations with Two-Stranded DNA Building Blocks
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-dev.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
Composable Computation in Leaderless, Discrete Chemical Reaction Networks
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-dev.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
CRNs Exposed: A Method for the Systematic Exploration of Chemical Reaction Networks
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-dev.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
Population-Induced Phase Transitions and the Verification of Chemical Reaction Networks
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-dev.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
ALCH: An Imperative Language for Chemical Reaction Network-Controlled Tile Assembly
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-dev.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
Implementing Non-Equilibrium Networks with Active Circuits of Duplex Catalysts
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-dev.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
Design Automation of Polyomino Set That Self-Assembles into a Desired Shape
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-dev.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
scadnano: A Browser-Based, Scriptable Tool for Designing DNA Nanostructures
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-dev.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
Verification and Computation in Restricted Tile Automata
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-dev.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}
}
Document
Turning Machines
Abstract
Molecular robotics is challenging, so it seems best to keep it simple. We consider an abstract molecular robotics model based on simple folding instructions that execute asynchronously. Turning Machines are a simple 1D to 2D folding model, also easily generalisable to 2D to 3D folding. A Turning Machine starts out as a line of connected monomers in the discrete plane, each with an associated turning number. A monomer turns relative to its neighbours, executing a unit-distance translation that drags other monomers along with it, and through collective motion the initial set of monomers eventually folds into a programmed shape. We fully characterise the ability of Turning Machines to execute line rotations, and to do so efficiently: computing an almost-full line rotation of 5π/3 radians is possible, yet a full 2π rotation is impossible. We show that such line-rotations represent a fundamental primitive in the model, by using them to efficiently and asynchronously fold arbitrarily large zig-zag-rastered squares and y-monotone shapes.
Cite as
Irina Kostitsyna, Cai Wood, and Damien Woods. Turning Machines. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{kostitsyna_et_al:LIPIcs.DNA.2020.11,
author = {Kostitsyna, Irina and Wood, Cai and Woods, Damien},
title = {{Turning Machines}},
booktitle = {26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
pages = {11:1--11:21},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.2020.11},
URN = {urn:nbn:de:0030-drops-129649},
doi = {10.4230/LIPIcs.DNA.2020.11},
annote = {Keywords: model of computation, molecular robotics, self-assembly, nubot, reconfiguration}
}