Phylogenetic automata, pruning, and multiple alignment

2011/03/22 by Oscar Westesson, Gerton Lunter, Westesson, Oscar +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #FOS: Biological sciences #Genomics (q-bio.GN) #Genomics and Phylogenetic Studies #Populations and Evolution (q-bio.PE) #Quantitative Methods (q-bio.QM) #RNA and protein synthesis mechanisms

paper · pdf · doi:10.48550/arxiv.1103.4347

openalex publication_date 2011/03/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We present an extension of Felsenstein's algorithm to indel models defined on entire sequences, without the need to condition on one multiple alignment. The algorithm makes use of a generalization from probabilistic substitution matrices to weighted finite-state transducers. Our approach may equivalently be viewed as a probabilistic formulation of progressive multiple sequence alignment, using partial-order graphs to represent ensemble profiles of ancestral sequences. We present a hierarchical stochastic approximation technique which makes this algorithm tractable for alignment analyses of reasonable size.

Citations

• Dating of the human-ape splitting by a molecular clock of mitochondrial DNA
• Evolutionary trees from DNA sequences: A maximum likelihood approach
• Probability distribution of molecular evolutionary trees: A new method of phylogenetic inference

Related

• Global Alignment of Molecular Sequences via Ancestral State Reconstruction
• BayesCAT: Bayesian Co-estimation of Alignment and Tree
• Pairwise sequence alignment at arbitrarily large evolutionary distance
• Approximate statistical alignment by iterative sampling of substitution\n matrices
• Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels