HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Tree Diet: Reducing the Treewidth to Unlock FPT Algorithms in RNA Bioinformatics

Bertrand Marchand 1, 2 Yann Ponty 1, * Laurent Bulteau 2, *
* Corresponding author
1 AMIBIO - Algorithms and Models for Integrative BIOlogy
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Contributor : Yann Ponty Connect in order to contact the contributor
Submitted on : Friday, April 23, 2021 - 12:38:17 AM
Last modification on : Friday, January 14, 2022 - 3:41:41 AM
Long-term archiving on: : Saturday, July 24, 2021 - 6:12:47 PM


Files produced by the author(s)


  • HAL Id : hal-03206132, version 1



Bertrand Marchand, Yann Ponty, Laurent Bulteau. Tree Diet: Reducing the Treewidth to Unlock FPT Algorithms in RNA Bioinformatics. WABI 2021 - 21st Workshop on Algorithms in Bioinformatics, 2021, Paris, France. ⟨hal-03206132⟩



Record views


Files downloads