Phylogenetic automata, pruning, and multiple alignment (2011-03-22T00:00:00.000000Z)

TL;DR

This work presents an extension of Felsenstein's algorithm to indel models defined on entire sequences, without the need to condition on one multiple alignment, using a hierarchical stochastic approximation technique which makes this algorithm tractable for alignment analyses of reasonable size.

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.

Authors

Oscar Westesson

1 papers

G. Lunter

1 papers

B. Paten

1 papers

TL;DR

Abstract

Authors

References39 items

pplacer: linear time maximum-likelihood and Bayesian phylogenetic placement of sequences onto a fixed reference tree

Evolutionary Triplet Models of Structured RNA

Genome-wide nucleotide-level mammalian ancestor reconstruction.

Phylogeny-Aware Gap Placement Prevents Errors in Sequence Alignment and Evolutionary Analysis

Alignment Uncertainty and Genomic Analysis

Transducers: an emerging probabilistic framework for modeling indels on trees

BAli-Phy: simultaneous Bayesian inference of alignment and phylogeny

Identification and Classification of Conserved RNA Secondary Structures in the Human Genome

Evolutionary models for insertions and deletions in a probabilistic modeling framework

Computational identification of evolutionarily conserved exons

A "Long Indel" model for evolutionary sequence alignment.

Phylogenetic estimation of context-dependent substitution rates by maximum likelihood.

Sequence alignments and pair hidden Markov models using evolutionary history.

Using guide trees to construct multiple-sequence evolutionary HMMs

Combining Phylogenetic and Hidden Markov Models in Biosequence Analysis

Statistical alignment based on fragment insertion and deletion models

Multiple sequence alignment using partial order graphs

Evolutionary HMMs: a Bayesian approach to multiple alignment

Factor graphs and the sum-product algorithm

An Algorithm for Statistical Alignment of Sequences Related by a Binary Tree

Statistical alignment: computational properties, homology testing and goodness-of-fit.

Codon-substitution models for heterogeneous selection pressure at amino acid sites.

RNA secondary structure prediction using stochastic context-free grammars and evolutionary history

Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids

Probability distribution of molecular evolutionary trees: A new method of phylogenetic inference

Combining protein evolution and secondary structure.

Estimating the pattern of nucleotide substitution

An evolutionary model for maximum likelihood alignment of DNA sequences

Evolution of Protein Molecules

A general model for the genetic analysis of pedigree data.

A First Course on Stochastic Processes

Evolutionary trees from DNA sequences: A maximum likelihood approach

Dating of the human-ape splitting by a molecular clock of mitochondrial DNA

BMC Bioinformatics BioMed Central Methodology article Accelerated probabilistic inference of RNA structure evolution

Inching toward reality: An improved likelihood model of sequence evolution

Weighted finite-state transducers in speech recognition

CHAPTER 24 – Evolution of Protein Molecules

Simultaneous comparison of three or more sequences related by a tree

BIOINFORMATICS ORIGINAL PAPER doi:10.1093/bioinformatics/btn104 Sequence analysis Combining statistical alignment and phylogenetic footprinting to detect regulatory elements

Field of Study

Journal Information

Name