HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

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

* 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.
Keywords :
Document type :
Conference papers

https://hal.inria.fr/hal-03206132
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

### File

main.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-03206132, version 1

### Citation

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