Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis
From MaRDI portal
Publication:1948701
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.
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
Cites work
- scientific article; zbMATH DE number 5764888 (Why is no real title available?)
- scientific article; zbMATH DE number 3736679 (Why is no real title available?)
- scientific article; zbMATH DE number 2079368 (Why is no real title available?)
- scientific article; zbMATH DE number 1865935 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- scientific article; zbMATH DE number 3410334 (Why is no real title available?)
- A few logs suffice to build (almost) all trees (I)
- A few logs suffice to build (almost) all trees. II
- A memetic algorithm to schedule planned maintenance for the national grid
- A signal-to-noise analysis of phylogeny estimation by neighbor-joining: Insufficiency of polynomial length sequences
- Alignment Uncertainty and Genomic Analysis
- Global alignment of molecular sequences via ancestral state reconstruction
- Invertibility of the TKF model of sequence evolution
- Inverting Random Functions II: Explicit Bounds for Discrete Maximum Likelihood Estimation, with Applications
- Inverting random functions
- Maximal Accurate Forests from Distance Matrices
- Optimal phylogenetic reconstruction
- Phylogenies without branch bounds: contracting the short, pruning the deep
- Provably fast and accurate recovery of evolutionary trees through harmonic greedy triplets
- The performance of neighbor-joining methods of phylogenetic reconstruction
Cited in
(20)- Counting, Generating and Sampling Tree Alignments
- Comparative Genomics
- Pairwise sequence alignment at arbitrarily large evolutionary distance
- A note on probabilistic models over strings: the linear algebra approach
- Alignment- and reference-free phylogenomics with colored de Bruijn graphs
- Impossibility of consistent distance estimation from sequence lengths under the TKF91 model
- Near-linear time edit distance for indel channels
- Parametric analysis of alignment and phylogenetic uncertainty
- A signal-to-noise analysis of phylogeny estimation by neighbor-joining: Insufficiency of polynomial length sequences
- An impossibility result for phylogeny reconstruction from \(k\)-mer counts
- Phase transition in the sample complexity of likelihood-based phylogeny inference
- Phylogenies without branch bounds: contracting the short, pruning the deep
- Optimal sequence length requirements for phylogenetic tree reconstruction with indels
- Global alignment of molecular sequences via ancestral state reconstruction
- Counting, Generating, Analyzing and Sampling Tree Alignments
- scientific article; zbMATH DE number 7370576 (Why is no real title available?)
- Statistically consistent and computationally efficient inference of ancestral DNA sequences in the TKF91 model under dense taxon sampling
- Identifiability of phylogenetic parameters from \(k\)-mer data under the coalescent
- Likelihood-based tree reconstruction on a concatenation of aligned sequence data sets can be statistically inconsistent
- PhyBWT: alignment-free phylogeny via eBWT positional clustering
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)
