Infrared

Infrared implements declarative modeling and tree-decomposition-based dynamic programming to provide exact optimization and controlled sampling for bioinformatics problems expressed as sparse feature networks.

Key Features:

• Declarative Modeling: Models problems as sets of variables over finite domains with dependencies captured by constraints and functions, formalizing problems as sparse feature networks (a generalization of constraint networks).
• Tree Decomposition Paradigm: Employs tree decomposition and cluster tree elimination algorithms, with complexity linear in the number of variables and exponential in the treewidth of the feature network.
• Generic Dynamic Programming Algorithms: Uses generic dynamic programming (DP) algorithms that automatically process declaratively modeled problems for exact optimization and controlled sampling.
• Versatile Applications in Bioinformatics: Applied to RNA design, RNA sequence-structure alignment, parsimony-driven inference of ancestral traits in phylogenetic trees/networks, coding-sequence design, and multidimensional Boltzmann sampling.
• Performance: Achieves computational complexities comparable to specialized algorithms and implementations on sparse networks with low to moderate treewidth.

Scientific Applications:

• RNA design: Enables exact optimization and controlled sampling for RNA design problems expressed as sparse feature networks.
• RNA sequence-structure alignment: Supports declarative modeling and DP-based exact solutions for sequence-structure alignment tasks.
• Parsimony-driven ancestral trait inference: Facilitates parsimony-driven inference of ancestral traits on phylogenetic trees and networks using declarative feature representations.
• Coding-sequence design: Applies exact optimization and sampling to the design of coding sequences within declarative models.
• Multidimensional Boltzmann sampling: Implements controlled, multidimensional Boltzmann sampling within the declarative tree-decomposition framework.

Methodology:

Problems are formalized as sparse feature networks using variables over finite domains with constraints and functions; solutions use tree decomposition and cluster tree elimination together with generic dynamic programming (DP) algorithms, yielding complexity linear in variables and exponential in treewidth.