Phylogenetic information complexity: is testing a tree easier than finding it?

DOI10.1016/J.JTBI.2009.01.007MaRDI QIDQ1621089zbMATH OpenOpenAlexWikidataFDO

Authors Elchanan Mossel, Mike Steel, László A. Székely

Publication date 8 November 2018

Published in Journal of Theoretical Biology (Search for Journal in Brave)

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

zbMATH Keywords

phylogenetic treereconstructionsequence lengthinformation content

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15) Combinatorial probability (60C05)

Abstract: Phylogenetic trees describe the evolutionary history of a group of present-day species from a common ancestor. These trees are typically reconstructed from aligned DNA sequence data. In this paper we analytically address the following question: is the amount of sequence data required to accurately reconstruct a tree significantly more than the amount required to test whether or not a candidate tree was the `true' tree? By `significantly', we mean that the two quantities behave the same way as a function of the number of species being considered. We prove that, for a certain type of model, the amount of information required is not significantly different; while for another type of model, the information required to test a tree is independent of the number of leaves, while that required to reconstruct it grows with this number. Our results combine probabilistic and combinatorial arguments.

Recommendations

• Teasing Apart Two Trees
• Algorithms for phylogeny reconstruction in a new mathematical model
• Minimizing phylogenetic number to find good evolutionary trees
• A few logs suffice to build (almost) all trees (I)
• scientific article; zbMATH DE number 1405846

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• A few logs suffice to build (almost) all trees (I)
• A phase transition for a random cluster model on phylogenetic trees.
• Four Characters Suffice to Convexly Define a Phylogenetic Tree
• How much can evolved characters tell us about the tree that generated them?
• Inverting Random Functions II: Explicit Bounds for Discrete Maximum Likelihood Estimation, with Applications
• Inverting random functions
• Inverting random functions. III: Discrete MLE revisited
• On Distinct Hypotheses
• Optimal phylogenetic reconstruction
• Probability and random processes.
• Teasing Apart Two Trees
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Tree reconstruction from multi-state characters

Cited in

(4)

• Significance of the length of the shortest tree
• Teasing Apart Two Trees
• Mathematical aspects of phylogenetic groves
• On the information content of discrete phylogenetic characters

This page was built for publication: Phylogenetic information complexity: is testing a tree easier than finding it?

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