Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics

Area of Science:

• Bioinformatics
• Computational Complexity
• Graph Theory

Background:

• Hard graph problems are common in bioinformatics.
• Fixed-Parameter Tractable (FPT) algorithms often use tree-decomposition and dynamic programming.
• Algorithm efficiency depends on the treewidth of the input graph.

Purpose of the Study:

• Introduce the TREE-DIET problem: removing minimal edges to reduce treewidth.
• Develop an FPT algorithm for TREE-DIET.
• Apply the approach to RNA-based bioinformatics problems.

Main Methods:

• Developed a Fixed-Parameter Tractable (FPT) dynamic programming algorithm for TREE-DIET.
• Analyzed parameterized complexity and established lower bounds for related problems.
• Implemented a prototype and tested it on RNA design, sequence-structure alignment, and pseudoknotted RNA searches.

Main Results:

• Achieved an FPT dynamic programming algorithm for TREE-DIET with [Formula: see text] time and space complexity.
• Demonstrated NP-hardness for certain variants of the problem.
• Showcased encouraging results on challenging RNA-based bioinformatics instances.

Conclusions:

• The TREE-DIET problem and its FPT algorithm offer a viable strategy to enhance bioinformatics computations.
• This method can make tree-decomposition-based algorithms more applicable to complex biological problems.
• The approach shows promise for improving RNA design, alignment, and genome analysis.