Volume
LIPIcs, Volume 205
27th International Conference on DNA Computing and Molecular Programming (DNA 27)
Event
DNA 27, September 13-16, 2021, Oxford, UK (Virtual Conference)Editors
- Department of Computer Science, Department of Chemical & Biological Engineering, Center for Biomedical Engineering, University of New Mexico, Albuquerque, NM, USA
Publication Details
- published at: 2021-09-08
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-205-1
- DBLP: db/conf/dna/dna2021
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 205, DNA 27, Complete Volume
Abstract
LIPIcs, Volume 205, DNA 27, Complete Volume
Cite as
27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 1-240, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@Proceedings{lakin_et_al:LIPIcs.DNA.27,
title = {{LIPIcs, Volume 205, DNA 27, Complete Volume}},
booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
pages = {1--240},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-205-1},
ISSN = {1868-8969},
year = {2021},
volume = {205},
editor = {Lakin, Matthew R. and \v{S}ulc, Petr},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27},
URN = {urn:nbn:de:0030-drops-146669},
doi = {10.4230/LIPIcs.DNA.27},
annote = {Keywords: LIPIcs, Volume 205, DNA 27, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{lakin_et_al:LIPIcs.DNA.27.0,
author = {Lakin, Matthew R. and \v{S}ulc, Petr},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
pages = {0:i--0:xiv},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-205-1},
ISSN = {1868-8969},
year = {2021},
volume = {205},
editor = {Lakin, Matthew R. and \v{S}ulc, Petr},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.0},
URN = {urn:nbn:de:0030-drops-146679},
doi = {10.4230/LIPIcs.DNA.27.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Robust Digital Molecular Design of Binarized Neural Networks
Abstract
Molecular programming - a paradigm wherein molecules are engineered to perform computation - shows great potential for applications in nanotechnology, disease diagnostics and smart therapeutics. A key challenge is to identify systematic approaches for compiling abstract models of computation to molecules. Due to their wide applicability, one of the most useful abstractions to realize is neural networks. In prior work, real-valued weights were achieved by individually controlling the concentrations of the corresponding "weight" molecules. However, large-scale preparation of reactants with precise concentrations quickly becomes intractable. Here, we propose to bypass this fundamental problem using Binarized Neural Networks (BNNs), a model that is highly scalable in a molecular setting due to the small number of distinct weight values. We devise a noise-tolerant digital molecular circuit that compactly implements a majority voting operation on binary-valued inputs to compute the neuron output. The network is also rate-independent, meaning the speed at which individual reactions occur does not affect the computation, further increasing robustness to noise. We first demonstrate our design on the MNIST classification task by simulating the system as idealized chemical reactions. Next, we map the reactions to DNA strand displacement cascades, providing simulation results that demonstrate the practical feasibility of our approach. We perform extensive noise tolerance simulations, showing that digital molecular neurons are notably more robust to noise in the concentrations of chemical reactants compared to their analog counterparts. Finally, we provide initial experimental results of a single binarized neuron. Our work suggests a solid framework for building even more complex neural network computation.
Cite as
Johannes Linder, Yuan-Jyue Chen, David Wong, Georg Seelig, Luis Ceze, and Karin Strauss. Robust Digital Molecular Design of Binarized Neural Networks. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{linder_et_al:LIPIcs.DNA.27.1,
author = {Linder, Johannes and Chen, Yuan-Jyue and Wong, David and Seelig, Georg and Ceze, Luis and Strauss, Karin},
title = {{Robust Digital Molecular Design of Binarized Neural Networks}},
booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
pages = {1:1--1:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-205-1},
ISSN = {1868-8969},
year = {2021},
volume = {205},
editor = {Lakin, Matthew R. and \v{S}ulc, Petr},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.1},
URN = {urn:nbn:de:0030-drops-146685},
doi = {10.4230/LIPIcs.DNA.27.1},
annote = {Keywords: Molecular Computing, Neural Network, Binarized Neural Network, Digital Logic, DNA, Strand Displacement}
}
Document
Computing Properties of Thermodynamic Binding Networks: An Integer Programming Approach
Abstract
The thermodynamic binding networks (TBN) model [Breik et al., 2021] is a tool for studying engineered molecular systems. The TBN model allows one to reason about their behavior through a simplified abstraction that ignores details about molecular composition, focusing on two key determinants of a system’s energetics common to any chemical substrate: how many molecular bonds are formed, and how many separate complexes exist in the system. We formulate as an integer program the NP-hard problem of computing stable (a.k.a., minimum energy) configurations of a TBN: those configurations that maximize the number of bonds and complexes. We provide open-source software solving this integer program. We give empirical evidence that this approach enables dramatically faster computation of TBN stable configurations than previous approaches based on SAT solvers [Breik et al., 2019]. Furthermore, unlike SAT-based approaches, our integer programming formulation can reason about TBNs in which some molecules have unbounded counts. These improvements in turn allow us to efficiently automate verification of desired properties of practical TBNs. Finally, we show that the TBN has a natural representation with a unique Hilbert basis describing the "fundamental components" out of which locally minimal energy configurations are composed. This characterization helps verify correctness of not only stable configurations, but entire "kinetic pathways" in a TBN.
Cite as
David Haley and David Doty. Computing Properties of Thermodynamic Binding Networks: An Integer Programming Approach. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{haley_et_al:LIPIcs.DNA.27.2,
author = {Haley, David and Doty, David},
title = {{Computing Properties of Thermodynamic Binding Networks: An Integer Programming Approach}},
booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
pages = {2:1--2:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-205-1},
ISSN = {1868-8969},
year = {2021},
volume = {205},
editor = {Lakin, Matthew R. and \v{S}ulc, Petr},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.2},
URN = {urn:nbn:de:0030-drops-146694},
doi = {10.4230/LIPIcs.DNA.27.2},
annote = {Keywords: thermodynamic binding networks, integer programming, constraint programming}
}
Document
Self-Replication via Tile Self-Assembly (Extended Abstract)
Abstract
In this paper we present a model containing modifications to the Signal-passing Tile Assembly Model (STAM), a tile-based self-assembly model whose tiles are capable of activating and deactivating glues based on the binding of other glues. These modifications consist of an extension to 3D, the ability of tiles to form "flexible" bonds that allow bound tiles to rotate relative to each other, and allowing tiles of multiple shapes within the same system. We call this new model the STAM*, and we present a series of constructions within it that are capable of self-replicating behavior. Namely, the input seed assemblies to our STAM* systems can encode either "genomes" specifying the instructions for building a target shape, or can be copies of the target shape with instructions built in. A universal tile set exists for any target shape (at scale factor 2), and from a genome assembly creates infinite copies of the genome as well as the target shape. An input target structure, on the other hand, can be "deconstructed" by the universal tile set to form a genome encoding it, which will then replicate and also initiate the growth of copies of assemblies of the target shape. Since the lengths of the genomes for these constructions are proportional to the number of points in the target shape, we also present a replicator which utilizes hierarchical self-assembly to greatly reduce the size of the genomes required. The main goals of this work are to examine minimal requirements of self-assembling systems capable of self-replicating behavior, with the aim of better understanding self-replication in nature as well as understanding the complexity of mimicking it.
Cite as
Andrew Alseth, Daniel Hader, and Matthew J. Patitz. Self-Replication via Tile Self-Assembly (Extended Abstract). In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{alseth_et_al:LIPIcs.DNA.27.3,
author = {Alseth, Andrew and Hader, Daniel and Patitz, Matthew J.},
title = {{Self-Replication via Tile Self-Assembly (Extended Abstract)}},
booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
pages = {3:1--3:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-205-1},
ISSN = {1868-8969},
year = {2021},
volume = {205},
editor = {Lakin, Matthew R. and \v{S}ulc, Petr},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.3},
URN = {urn:nbn:de:0030-drops-146707},
doi = {10.4230/LIPIcs.DNA.27.3},
annote = {Keywords: Algorithmic self-assembly, tile assembly model, self-replication}
}
Document
Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D
Abstract
We investigate a fundamental question regarding a benchmark class of shapes in one of the simplest, yet most widely utilized abstract models of algorithmic tile self-assembly. More specifically, we study the directed tile complexity of a k × N thin rectangle in Winfree’s ubiquitous abstract Tile Assembly Model, assuming that cooperative binding cannot be enforced (temperature-1 self-assembly) and that tiles are allowed to be placed at most one step into the third dimension (just-barely 3D). While the directed tile complexities of a square and a scaled-up version of any algorithmically specified shape at temperature 1 in just-barely 3D are both asymptotically the same as they are (respectively) at temperature 2 in 2D, the (nearly tight) bounds on the directed tile complexity of a thin rectangle at temperature 2 in 2D are not currently known to hold at temperature 1 in just-barely 3D. Motivated by this discrepancy, we establish new lower and upper bounds on the directed tile complexity of a thin rectangle at temperature 1 in just-barely 3D. The proof of our upper bound is based on the construction of a novel, just-barely 3D temperature-1 self-assembling counter. Each value of the counter is comprised of k-2 digits, represented in a geometrically staggered fashion within k rows. This nearly optimal digit density, along with the base of the counter, which is proportional to N^{1/(k-1)}, results in an upper bound of O(N^{1/(k-1)} + log N), and is an asymptotic improvement over the previous state-of-the-art upper bound. On our way to proving our lower bound, we develop a new, more powerful type of specialized Window Movie Lemma that lets us bound the number of "sufficiently similar" ways to assign glues to a set (rather than a sequence) of fixed locations. Consequently, our lower bound, Ω(N^{1/k}), is also an asymptotic improvement over the previous state-of-the-art lower bound.
Cite as
David Furcy, Scott M. Summers, and Logan Withers. Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{furcy_et_al:LIPIcs.DNA.27.4,
author = {Furcy, David and Summers, Scott M. and Withers, Logan},
title = {{Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D}},
booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
pages = {4:1--4:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-205-1},
ISSN = {1868-8969},
year = {2021},
volume = {205},
editor = {Lakin, Matthew R. and \v{S}ulc, Petr},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.4},
URN = {urn:nbn:de:0030-drops-146716},
doi = {10.4230/LIPIcs.DNA.27.4},
annote = {Keywords: Self-assembly, algorithmic self-assembly, tile self-assembly}
}
Document
ENSnano: A 3D Modeling Software for DNA Nanostructures
Abstract
Since the 1990s, increasingly complex nanostructures have been reliably obtained out of self-assembled DNA strands: from "simple" 2D shapes to 3D gears and articulated nano-objects, and even computing structures. The success of the assembly of these structures relies on a fine tuning of their structure to match the peculiar geometry of DNA helices. Various softwares have been developed to help the designer. These softwares provide essentially four kind of tools: an abstract representation of DNA helices (e.g. cadnano, scadnano, DNApen, 3DNA, Hex-tiles); a 3D view of the design (e.g., vHelix, Adenita, oxDNAviewer); fully automated design (e.g., BScOR, Daedalus, Perdix, Talos, Athena), generally dedicated to a specific kind of design, such as wireframe origami; and coarse grain or thermodynamical physics simulations (e.g., oxDNA, MrDNA, SNUPI, Nupack, ViennaRNA,...). MagicDNA combines some of these approaches to ease the design of configurable DNA origamis.
We present our first step in the direction of conciliating all these different approaches and purposes into one single reliable GUI solution: the first fully usable version (design from scratch to export) of our general purpose 3D DNA nanostructure design software ENSnano. We believe that its intuitive, swift and yet powerful graphical interface, combining 2D and 3D editable views, allows fast and precise editing of DNA nanostructures. It also handles editing of large 2D/3D structures smoothly, and imports from the most common solutions. Our software extends the concept of grids introduced in cadnano. Grids allow to abstract and articulated the different parts of a design. ENSnano also provides new design tools which speeds up considerably the design of complex large 3D structures, most notably: a 2D split view, which allows to edit intricate 3D structures which cannot easily be mapped in a 2D view, and a copy, paste & repeat functionality, which takes advantage of the grids to design swiftly large repetitive chunks of a structure. ENSnano has been validated experimentally, as proven by the AFM images of a DNA origami entirely designed in ENSnano.
ENSnano is a light-weight ready-to-run independent single-file app, running seamlessly in most of the operating systems (Windows 10, MacOS 10.13+ and Linux). Precompiled versions for Windows and MacOS are ready to download on ENSnano website. As of writing this paper, our software is being actively developed to extend its capacities in various directions discussed in this article. Still, its 3D and 2D editing interface is already meeting our usability goals. Because of its stability and ease of use, we believe that ENSnano could already be integrated in anyone’s design chain, when precise editing of a larger nanostructure is needed.
Cite as
Nicolas Levy and Nicolas Schabanel. ENSnano: A 3D Modeling Software for DNA Nanostructures. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{levy_et_al:LIPIcs.DNA.27.5,
author = {Levy, Nicolas and Schabanel, Nicolas},
title = {{ENSnano: A 3D Modeling Software for DNA Nanostructures}},
booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
pages = {5:1--5:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-205-1},
ISSN = {1868-8969},
year = {2021},
volume = {205},
editor = {Lakin, Matthew R. and \v{S}ulc, Petr},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.5},
URN = {urn:nbn:de:0030-drops-146722},
doi = {10.4230/LIPIcs.DNA.27.5},
annote = {Keywords: Software, DNA nanostructure, Molecular design, molecular self-assembly}
}
Document
Directed Non-Cooperative Tile Assembly Is Decidable
Abstract
We provide a complete characterisation of all final states of a model called directed non-cooperative tile self-assembly, also called directed temperature 1 tile assembly, which proves that this model cannot possibly perform Turing computation. This model is a deterministic version of the more general undirected model, whose computational power is still open. Our result uses recent results in the domain, and solves a conjecture formalised in 2011. We believe that this is a major step towards understanding the full model.
Temperature 1 tile assembly can be seen as a two-dimensional extension of finite automata, where geometry provides a form of memory and synchronisation, yet the full power of these "geometric blockings" was still largely unknown until recently (note that nontrivial algorithms which are able to build larger structures than the naive constructions have been found).
Cite as
Pierre-Étienne Meunier and Damien Regnault. Directed Non-Cooperative Tile Assembly Is Decidable. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{meunier_et_al:LIPIcs.DNA.27.6,
author = {Meunier, Pierre-\'{E}tienne and Regnault, Damien},
title = {{Directed Non-Cooperative Tile Assembly Is Decidable}},
booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
pages = {6:1--6:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-205-1},
ISSN = {1868-8969},
year = {2021},
volume = {205},
editor = {Lakin, Matthew R. and \v{S}ulc, Petr},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.6},
URN = {urn:nbn:de:0030-drops-146735},
doi = {10.4230/LIPIcs.DNA.27.6},
annote = {Keywords: Self-assembly, Molecular Computing, Models of Computation, Computational Geometry}
}
Document
Molecular Machines from Topological Linkages
Abstract
Life is built upon amazingly sophisticated molecular machines whose behavior combines mechanical and chemical action. Engineering of similarly complex nanoscale devices from first principles remains an as yet unrealized goal of bioengineering. In this paper we formalize a simple model of mechanical motion (mechanical linkages) combined with chemical bonding. The model has a natural implementation using DNA with double-stranded rigid links, and single-stranded flexible joints and binding sites. Surprisingly, we show that much of the complex behavior is preserved in an idealized topological model which considers solely the graph connectivity of the linkages. We show a number of artifacts including Boolean logic, catalysts, a fueled motor, and chemo-mechanical coupling, all of which can be understood and reasoned about in the topological model. The variety of achieved behaviors supports the use of topological chemical linkages in understanding and engineering complex molecular behaviors.
Cite as
Keenan Breik, Austin Luchsinger, and David Soloveichik. Molecular Machines from Topological Linkages. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{breik_et_al:LIPIcs.DNA.27.7,
author = {Breik, Keenan and Luchsinger, Austin and Soloveichik, David},
title = {{Molecular Machines from Topological Linkages}},
booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
pages = {7:1--7:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-205-1},
ISSN = {1868-8969},
year = {2021},
volume = {205},
editor = {Lakin, Matthew R. and \v{S}ulc, Petr},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.7},
URN = {urn:nbn:de:0030-drops-146749},
doi = {10.4230/LIPIcs.DNA.27.7},
annote = {Keywords: chemical computation, mechanical computation, bioengineering, models of biochemistry, molecular machines, mechanical linkages, generic rigidity}
}
Document
Small Tile Sets That Compute While Solving Mazes
Abstract
We ask the question of how small a self-assembling set of tiles can be yet have interesting computational behaviour. We study this question in a model where supporting walls are provided as an input structure for tiles to grow along: we call it the Maze-Walking Tile Assembly Model. The model has a number of implementation prospects, one being DNA strands that attach to a DNA origami substrate. Intuitively, the model suggests a separation of signal routing and computation: the input structure (maze) supplies a routing diagram, and the programmer’s tile set provides the computational ability. We ask how simple the computational part can be.
We give two tiny tile sets that are computationally universal in the Maze-Walking Tile Assembly Model. The first has four tiles and simulates Boolean circuits by directly implementing NAND, NXOR and NOT gates. Our second tile set has 6 tiles and is called the Collatz tile set as it produces patterns found in binary/ternary representations of iterations of the Collatz function. Using computer search we find that the Collatz tile set is expressive enough to encode Boolean circuits using blocks of these patterns. These two tile sets give two different methods to find simple universal tile sets, and provide motivation for using pre-assembled maze structures as circuit wiring diagrams in molecular self-assembly based computing.
Cite as
Matthew Cook, Tristan Stérin, and Damien Woods. Small Tile Sets That Compute While Solving Mazes. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{cook_et_al:LIPIcs.DNA.27.8,
author = {Cook, Matthew and St\'{e}rin, Tristan and Woods, Damien},
title = {{Small Tile Sets That Compute While Solving Mazes}},
booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
pages = {8:1--8:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-205-1},
ISSN = {1868-8969},
year = {2021},
volume = {205},
editor = {Lakin, Matthew R. and \v{S}ulc, Petr},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.8},
URN = {urn:nbn:de:0030-drops-146758},
doi = {10.4230/LIPIcs.DNA.27.8},
annote = {Keywords: model of computation, self-assembly, small universal tile set, Boolean circuits, maze-solving}
}
Document
Predicting Minimum Free Energy Structures of Multi-Stranded Nucleic Acid Complexes Is APX-Hard
Abstract
Given multiple nucleic acid strands, what is the minimum free energy (MFE) secondary structure that they can form? As interacting nucleic acid strands are the basis for DNA computing and molecular programming, e.g., in DNA self-assembly and DNA strand displacement systems, determining the MFE structure is an important step in the design and verification of these systems. Efficient dynamic programming algorithms are well known for predicting the MFE pseudoknot-free secondary structure of a single nucleic acid strand. In contrast, we prove that for a simple energy model, the problem of predicting the MFE pseudoknot-free secondary structure formed from multiple interacting nucleic acid strands is NP-hard and also APX-hard. The latter result implies that there does not exist a polynomial time approximation scheme for this problem, unless 𝖯 = NP, and it suggests that heuristic methods should be investigated.
Cite as
Anne Condon, Monir Hajiaghayi, and Chris Thachuk. Predicting Minimum Free Energy Structures of Multi-Stranded Nucleic Acid Complexes Is APX-Hard. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{condon_et_al:LIPIcs.DNA.27.9,
author = {Condon, Anne and Hajiaghayi, Monir and Thachuk, Chris},
title = {{Predicting Minimum Free Energy Structures of Multi-Stranded Nucleic Acid Complexes Is APX-Hard}},
booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
pages = {9:1--9:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-205-1},
ISSN = {1868-8969},
year = {2021},
volume = {205},
editor = {Lakin, Matthew R. and \v{S}ulc, Petr},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.9},
URN = {urn:nbn:de:0030-drops-146765},
doi = {10.4230/LIPIcs.DNA.27.9},
annote = {Keywords: Nucleic Acid Secondary Structure Prediction, APX-Hardness, NP-Hardness}
}
Document
Reactamole: Functional Reactive Molecular Programming
Abstract
Chemical reaction networks (CRNs) are an important tool for molecular programming, a field that is rapidly expanding our ability to deploy computer programs into biological systems for a variety of applications. However, CRNs are also difficult to work with due to their massively parallel nature, leading to the need for higher-level languages that allow for easier computation with CRNs. Recently, research has been conducted into a variety of higher-level languages for deterministic CRNs but modeling CRN parallelism, managing error accumulation, and finding natural CRN representations are ongoing challenges.
We introduce Reactamole, a higher-level language for deterministic CRNs that utilizes the functional reactive programming (FRP) paradigm to represent CRNs as a reactive dataflow network. Reactamole equates a CRN with a functional reactive program, implementing the key primitives of the FRP paradigm directly as CRNs. The functional nature of Reactamole makes reasoning about molecular programs easier, and its strong static typing allows us to ensure that a CRN is well-formed by virtue of being well-typed. In this paper, we describe the design of Reactamole and how we use CRNs to represent the common datatypes and operations found in FRP. We also demonstrate the potential of this functional reactive approach to molecular programming by giving an extended example where a CRN is constructed using FRP to modulate and demodulate an amplitude modulated signal.
Cite as
Titus H. Klinge, James I. Lathrop, Peter-Michael Osera, and Allison Rogers. Reactamole: Functional Reactive Molecular Programming. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{klinge_et_al:LIPIcs.DNA.27.10,
author = {Klinge, Titus H. and Lathrop, James I. and Osera, Peter-Michael and Rogers, Allison},
title = {{Reactamole: Functional Reactive Molecular Programming}},
booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
pages = {10:1--10:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-205-1},
ISSN = {1868-8969},
year = {2021},
volume = {205},
editor = {Lakin, Matthew R. and \v{S}ulc, Petr},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.10},
URN = {urn:nbn:de:0030-drops-146775},
doi = {10.4230/LIPIcs.DNA.27.10},
annote = {Keywords: Chemical Reaction Network, Functional Reactive Programming, Domain Specific Language}
}
Document
Parallel Pairwise Operations on Data Stored in DNA: Sorting, Shifting, and Searching
Abstract
Prior research has introduced the Single-Instruction-Multiple-Data paradigm for DNA computing (SIMD DNA). It offers the potential for storing information and performing in-memory computations on DNA, with massive parallelism. This paper introduces three new SIMD DNA operations: sorting, shifting, and searching. Each is a fundamental operation in computer science. Our implementations demonstrate the effectiveness of parallel pairwise operations with this new paradigm.
Cite as
Tonglin Chen, Arnav Solanki, and Marc Riedel. Parallel Pairwise Operations on Data Stored in DNA: Sorting, Shifting, and Searching. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{chen_et_al:LIPIcs.DNA.27.11,
author = {Chen, Tonglin and Solanki, Arnav and Riedel, Marc},
title = {{Parallel Pairwise Operations on Data Stored in DNA: Sorting, Shifting, and Searching}},
booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
pages = {11:1--11:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-205-1},
ISSN = {1868-8969},
year = {2021},
volume = {205},
editor = {Lakin, Matthew R. and \v{S}ulc, Petr},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.11},
URN = {urn:nbn:de:0030-drops-146780},
doi = {10.4230/LIPIcs.DNA.27.11},
annote = {Keywords: Molecular Computing, DNA Computing, DNA Storage, Parallel Computing, Strand Displacement}
}