Infrared: a declarative tree decomposition-powered framework for bioinformatics.

Area of Science:

• Bioinformatics
• Computational Biology
• Algorithm Development

Background:

• Dynamic Programming (DP) offers exact solutions for bioinformatics but requires specialized, complex implementations.
• Existing DP methods are often difficult to adapt to variations in problem settings.

Purpose of the Study:

• Introduce the Infrared framework to generalize and simplify the application of DP in bioinformatics.
• Enable efficient development of exact optimization and controlled sampling tools for diverse bioinformatics tasks.

Main Methods:

• Infrared models problems as sparse feature networks, a generalization of constraint networks.
• Utilizes generic cluster tree elimination algorithms on tree decompositions of feature networks.
• Achieves complexities linear in the number of variables and exponential in treewidth.

Main Results:

• The Infrared software facilitates rapid development of bioinformatics applications in Python.
• Problems are declaratively modeled, and solved automatically by generic DP algorithms.
• Demonstrated applications include RNA design, sequence-structure alignment, phylogenetic inference, and coding sequence design.

Conclusions:

• Infrared provides a powerful and flexible framework for solving a wide range of bioinformatics problems.
• Offers practical empirical efficiency comparable to specialized algorithms.
• Lowers the barrier to entry for developing advanced computational biology tools.