2026-07-24T21:14:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14360 2024-03-06T10:53:58Z ddc:004 open_access

Tree Diet: Reducing the Treewidth to Unlock FPT Algorithms in RNA Bioinformatics Marchand, Bertrand Ponty, Yann Bulteau, Laurent RNA treewidth FPT algorithms RNA design structure-sequence alignment Hard graph problems are ubiquitous in Bioinformatics, inspiring the design of specialized Fixed-Parameter Tractable algorithms, many of which rely on a combination of tree-decomposition and dynamic programming. The time/space complexities of such approaches hinge critically on low values for the treewidth tw of the input graph. In order to extend their scope of applicability, we introduce the Tree-Diet problem, i.e. the removal of a minimal set of edges such that a given tree-decomposition can be slimmed down to a prescribed treewidth tw'. Our rationale is that the time gained thanks to a smaller treewidth in a parameterized algorithm compensates the extra post-processing needed to take deleted edges into account. Our core result is an FPT dynamic programming algorithm for Tree-Diet, using 2^{O(tw)}n time and space. We complement this result with parameterized complexity lower-bounds for stronger variants (e.g., NP-hardness when tw' or tw-tw' is constant). We propose a prototype implementation for our approach which we apply on difficult instances of selected RNA-based problems: RNA design, sequence-structure alignment, and search of pseudoknotted RNAs in genomes, revealing very encouraging results. This work paves the way for a wider adoption of tree-decomposition-based algorithms in Bioinformatics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bertrand Marchand and Yann Ponty and Laurent Bulteau 2021 Is Part Of LIPIcs, Volume 201, 21st International Workshop on Algorithms in Bioinformatics (WABI 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2021.7 urn:nbn:de:0030-drops-143604 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2021.7 eng https://creativecommons.org/licenses/by/4.0/legalcode