Fast phylogeny reconstruction through learning of ancestral sequences

DOI10.1007/S00453-012-9644-4MaRDI QIDQ1950394zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 13 May 2013

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

ancestral sequence reconstructioninformation flowIsing modelphase transitionsphylogenetic forestsphylogenetic reconstruction

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Algorithms on strings (68W32) Problems related to evolution (92D15)

Abstract: Given natural limitations on the length DNA sequences, designing phylogenetic reconstruction methods which are reliable under limited information is a crucial endeavor. There have been two approaches to this problem: reconstructing partial but reliable information about the tree (cite{Mo07, DMR08,DHJ06,GMS08}), and reaching "deeper" in the tree through reconstruction of ancestral sequences. In the latter category, cite{DMR06} settled an important conjecture of M.Steel, showing that, under the CFN model of evolution, all trees on $n$ leaves with edge lengths bounded by the Ising model phase transition can be recovered with high probability from genomes of length $O(logn)$ with a polynomial time algorithm. Their methods had a running time of $O(n^{10})$. Here we enhance our methods from cite{DHJ06} with the learning of ancestral sequences and provide an algorithm for reconstructing a sub-forest of the tree which is reliable given available data, without requiring a-priori known bounds on the edge lengths of the tree. Our methods are based on an intuitive minimum spanning tree approach and run in $O(n^3)$ time. For the case of full reconstruction of trees with edges under the phase transition, we maintain the same sequence length requirements as cite{DMR06}, despite the considerably faster running time.

Recommendations

• Fast and reliable reconstruction of phylogenetic trees with indistinguishable edges
• Optimal phylogenetic reconstruction
• Phylogenies without branch bounds: contracting the short, pruning the deep
• A few logs suffice to build (almost) all trees (I)
• On the inference of large phylogenies with long branches: how long is too long?

Cites work

• A few logs suffice to build (almost) all trees (I)
• A few logs suffice to build (almost) all trees. II
• Estimation of evolutionary distances between homologous nucleotide sequences.
• scientific article; zbMATH DE number 5764888 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Maximal Accurate Forests from Distance Matrices
• Optimal phylogenetic reconstruction
• Phase transitions in phylogeny
• Phylogenies without branch bounds: contracting the short, pruning the deep
• Sequence length bounds for resolving a deep phylogenetic divergence
• Taxonomy with confidence

Cited in

(15)

• Ancestral sequence reconstruction with maximum parsimony
• Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis
• Species tree estimation under joint modeling of coalescence and duplication: sample complexity of quartet methods
• Ancestral state reconstruction with large numbers of sequences and edge-length estimation
• Absolute convergence: True trees from short sequences
• Fast and reliable reconstruction of phylogenetic trees with indistinguishable edges
• Optimal phylogenetic reconstruction
• Phylogenies without branch bounds: contracting the short, pruning the deep
• A few logs suffice to build (almost) all trees (I)
• scientific article; zbMATH DE number 1945176 (Why is no real title available?)
• New absolute fast converging phylogeny estimation methods with improved scalability and accuracy
• Optimal sequence length requirements for phylogenetic tree reconstruction with indels
• On the inference of large phylogenies with long branches: how long is too long?
• Phase transition in the sample complexity of likelihood-based phylogeny inference
• Global alignment of molecular sequences via ancestral state reconstruction

This page was built for publication: Fast phylogeny reconstruction through learning of ancestral sequences

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