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

DOI10.1007/S11538-013-9906-6MaRDI QIDQ2446798zbMATH OpenOpenAlexWikidataFDO

Authors Alexandre Bouchard-Côté

Publication date 22 April 2014

Published in Bulletin of Mathematical Biology (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.5054

zbMATH Keywords

alignmentsautomatafactor graphsgraphical modelsindelphylogeneticsstring transducersTKF91

Mathematics Subject Classification ID

Applications of graph theory (05C90) Basic linear algebra (15A99) Problems related to evolution (92D15)

Abstract: Probabilistic models over strings have played a key role in developing methods allowing indels to be treated as phylogenetically informative events. There is an extensive literature on using automata and transducers on phylogenies to do inference on these probabilistic models, in which an important theoretical question in the field is the complexity of computing the normalization of a class of string-valued graphical models. This question has been investigated using tools from combinatorics, dynamic programming, and graph theory, and has practical applications in Bayesian phylogenetics. In this work, we revisit this theoretical question from a different point of view, based on linear algebra. The main contribution is a new proof of a known result on the complexity of inference on TKF91, a well-known probabilistic model over strings. Our proof uses a different approach based on classical linear algebra results, and is in some cases easier to extend to other models. The proving method also has consequences on the implementation and complexity of inference algorithms.

Recommendations

• scientific article; zbMATH DE number 5247137
• The consensus string problem and the complexity of comparing hidden Markov models.
• The most probable string: an algorithmic study
• Biological Sequence Analysis
• scientific article; zbMATH DE number 2081009

Cites work

• A sufficient condition for reducing recursions in hidden Markov models
• Alignment Uncertainty and Genomic Analysis
• Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis
• An Improved Model for Statistical Alignment
• Applying the Thorne-Kishino-Felsenstein model to sequence evolution on a star-shaped tree
• Automated empirical optimizations of software and the ATLAS project
• Auxiliary Variable Methods for Markov Chain Monte Carlo with Applications
• GENERIC ∊-REMOVAL AND INPUT ∊-NORMALIZATION ALGORITHMS FOR WEIGHTED TRANSDUCERS
• Gibbs sampler for statistical multiple alignment
• Graphical models
• Handbook of weighted automata
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• Multiplying matrices faster than coppersmith-winograd
• On the definition of a family of automata
• Pattern recognition and machine learning.
• The Kronecker product and stochastic automata networks

Cited in

(3)

• scientific article; zbMATH DE number 6999908 (Why is no real title available?)
• Grammatical Inference: Algorithms and Applications
• Bootstraps to strings: solving random matrix models with positivity

Describes a project that uses

Uses Software

• PRMLT
• fastDNAml
• Statalign
• Bali-phy
• ATLAS

This page was built for publication: A note on probabilistic models over strings: the linear algebra approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2446798)