Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis
From MaRDI portal
Publication:1948701
DOI10.1214/12-AAP852zbMATH Open1377.92060arXiv1109.5002OpenAlexW3103262072MaRDI QIDQ1948701FDOQ1948701
Authors: Constantinos Daskalakis, Sebastien Roch 
Publication date: 24 April 2013
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Abstract: We present an efficient phylogenetic reconstruction algorithm allowing insertions and deletions which provably achieves a sequence-length requirement (or sample complexity) growing polynomially in the number of taxa. Our algorithm is distance-based, that is, it relies on pairwise sequence comparisons. More importantly, our approach largely bypasses the difficult problem of multiple sequence alignment.
Full work available at URL: https://arxiv.org/abs/1109.5002
Recommendations
- Optimal sequence length requirements for phylogenetic tree reconstruction with indels
- Phylogenies without branch bounds: contracting the short, pruning the deep
- Optimal phylogenetic reconstruction
- Phase transition in the sample complexity of likelihood-based phylogeny inference
- Fast phylogeny reconstruction through learning of ancestral sequences
Genetics and epigenetics (92D10) Applications of branching processes (60J85) Interacting random processes; statistical mechanics type models; percolation theory (60K35)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The performance of neighbor-joining methods of phylogenetic reconstruction
- Title not available (Why is that?)
- Inverting random functions
- Optimal phylogenetic reconstruction
- A few logs suffice to build (almost) all trees (I)
- Learning nonsingular phylogenies and hidden Markov models
- Phylogenies without branch bounds: contracting the short, pruning the deep
- A few logs suffice to build (almost) all trees. II
- Title not available (Why is that?)
- Inverting Random Functions II: Explicit Bounds for Discrete Maximum Likelihood Estimation, with Applications
- A signal-to-noise analysis of phylogeny estimation by neighbor-joining: Insufficiency of polynomial length sequences
- Global alignment of molecular sequences via ancestral state reconstruction
- Alignment Uncertainty and Genomic Analysis
- Provably fast and accurate recovery of evolutionary trees through harmonic greedy triplets
- Invertibility of the TKF model of sequence evolution
- Maximal Accurate Forests from Distance Matrices
- A memetic algorithm to schedule planned maintenance for the national grid
Cited In (20)
- Global alignment of molecular sequences via ancestral state reconstruction
- An impossibility result for phylogeny reconstruction from \(k\)-mer counts
- A note on probabilistic models over strings: the linear algebra approach
- Impossibility of consistent distance estimation from sequence lengths under the TKF91 model
- Parametric analysis of alignment and phylogenetic uncertainty
- Identifiability of phylogenetic parameters from \(k\)-mer data under the coalescent
- Phylogenies without branch bounds: contracting the short, pruning the deep
- Counting, Generating, Analyzing and Sampling Tree Alignments
- Comparative Genomics
- Pairwise sequence alignment at arbitrarily large evolutionary distance
- PhyBWT: alignment-free phylogeny via eBWT positional clustering
- Title not available (Why is that?)
- Likelihood-based tree reconstruction on a concatenation of aligned sequence data sets can be statistically inconsistent
- Alignment- and reference-free phylogenomics with colored de Bruijn graphs
- A signal-to-noise analysis of phylogeny estimation by neighbor-joining: Insufficiency of polynomial length sequences
- Near-linear time edit distance for indel channels
- Optimal sequence length requirements for phylogenetic tree reconstruction with indels
- Statistically consistent and computationally efficient inference of ancestral DNA sequences in the TKF91 model under dense taxon sampling
- Phase transition in the sample complexity of likelihood-based phylogeny inference
- Counting, Generating and Sampling Tree Alignments
Uses Software
This page was built for publication: Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1948701)
