DROPS

Document

DOI: 10.4230/LIPIcs.WABI.2024.18

RNA Triplet Repeats: Improved Algorithms for Structure Prediction and Interactions

Authors: Kimon Boehmer, Sarah J. Berkemer, Sebastian Will, and Yann Ponty

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract

RNAs composed of Triplet Repeats (TR) have recently attracted much attention in the field of synthetic biology. We study the mimimum free energy (MFE) secondary structures of such RNAs and give improved algorithms to compute the MFE and the partition function. Furthermore, we study the interaction of multiple RNAs and design a new algorithm for computing MFE and partition function for RNA-RNA interactions, improving the previously known factorial running time to exponential. In the case of TR, we show computational hardness but still obtain a parameterized algorithm. Finally, we propose a polynomial-time algorithm for computing interactions from a base set of RNA strands and conduct experiments on the interaction of TR based on this algorithm. For instance, we study the probability that a base pair is formed between two strands with the same triplet pattern, allowing an assessment of a notion of orthogonality between TR.

Cite as

Kimon Boehmer, Sarah J. Berkemer, Sebastian Will, and Yann Ponty. RNA Triplet Repeats: Improved Algorithms for Structure Prediction and Interactions. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 18:1-18:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{boehmer_et_al:LIPIcs.WABI.2024.18,
  author =	{Boehmer, Kimon and Berkemer, Sarah J. and Will, Sebastian and Ponty, Yann},
  title =	{{RNA Triplet Repeats: Improved Algorithms for Structure Prediction and Interactions}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{18:1--18:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.18},
  URN =		{urn:nbn:de:0030-drops-206625},
  doi =		{10.4230/LIPIcs.WABI.2024.18},
  annote =	{Keywords: RNA folding, RNA interactions, triplet repeats, dynamic programming, NP-hardness}
}

Search Results

Documents authored by Boehmer, Kimon

RNA Triplet Repeats: Improved Algorithms for Structure Prediction and Interactions

Abstract

Cite as

Thanks for your feedback!

Could not send message