DROPS

Document

Programmable Co‑Transcriptional Splicing: Realizing Regular Languages via Hairpin Deletion

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

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

Abstract

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

Cite as

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

Copy BibTex To Clipboard

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

Document

DOI: 10.4230/LIPIcs.DISC.2020.7

Distributed Computation with Continual Population Growth

Authors: Da-Jung Cho, Matthias Függer, Corbin Hopper, Manish Kushwaha, Thomas Nowak, and Quentin Soubeyran

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract

Computing with synthetically engineered bacteria is a vibrant and active field with numerous applications in bio-production, bio-sensing, and medicine. Motivated by the lack of robustness and by resource limitation inside single cells, distributed approaches with communication among bacteria have recently gained in interest. In this paper, we focus on the problem of population growth happening concurrently, and possibly interfering, with the desired bio-computation. Specifically, we present a fast protocol in systems with continuous population growth for the majority consensus problem and prove that it correctly identifies the initial majority among two inputs with high probability if the initial difference is Ω(√{nlog n}) where n is the total initial population. We also present a fast protocol that correctly computes the NAND of two inputs with high probability. We demonstrate that combining the NAND gate protocol with the continuous-growth majority consensus protocol, using the latter as an amplifier, it is possible to implement circuits computing arbitrary Boolean functions.

Cite as

Da-Jung Cho, Matthias Függer, Corbin Hopper, Manish Kushwaha, Thomas Nowak, and Quentin Soubeyran. Distributed Computation with Continual Population Growth. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cho_et_al:LIPIcs.DISC.2020.7,
  author =	{Cho, Da-Jung and F\"{u}gger, Matthias and Hopper, Corbin and Kushwaha, Manish and Nowak, Thomas and Soubeyran, Quentin},
  title =	{{Distributed Computation with Continual Population Growth}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.7},
  URN =		{urn:nbn:de:0030-drops-130856},
  doi =		{10.4230/LIPIcs.DISC.2020.7},
  annote =	{Keywords: microbiological circuits, majority consensus, birth-death processes}
}

Search Results

Documents authored by Cho, Da-Jung

Programmable Co‑Transcriptional Splicing: Realizing Regular Languages via Hairpin Deletion

Abstract

Cite as

Distributed Computation with Continual Population Growth

Abstract

Cite as

Thanks for your feedback!

Could not send message