A note on probabilistic models over strings: the linear algebra approach.

Area of Science:

• Computational Biology
• Theoretical Computer Science
• Statistical Modeling

Background:

• Probabilistic models over strings are crucial for phylogenetic inference, considering insertions and deletions (indels).
• Previous research focused on automata and transducers for inference, with a key theoretical question being the computational complexity of normalizing string-valued graphical models.
• Existing methods utilize combinatorics, dynamic programming, and graph theory, with applications in Bayesian phylogenetics.

Purpose of the Study:

• To revisit the theoretical question of normalizing string-valued graphical models from a novel linear algebra perspective.
• To develop results that aid in the analysis and design of inference algorithms for these models.
• To provide a more extensible framework for analyzing probabilistic models over strings.

Main Methods:

• A novel approach based on linear algebra to analyze string-valued graphical models.
• Development of results facilitating inference algorithm design.
• Introduction of the 'triangular transducers' condition for model extensibility.

Main Results:

• A new, elementary proof for the complexity of inference on the TKF91 model using the linear algebra perspective.
• Demonstration that the linear algebra view simplifies algorithm description and composition.
• Identification of the 'triangular transducers' condition as a practical and extensible method.

Conclusions:

• The linear algebra approach offers a powerful and extensible framework for inference on string-valued graphical models.
• This method allows for the potential integration of high-performance computing techniques, such as GPU-based libraries and low-rank matrix approximations.
• The findings pave the way for more efficient and adaptable phylogenetic inference methods.