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

DOI10.1016/J.JTBI.2009.01.007zbMATH Open1402.92322arXiv0807.1756OpenAlexW2141527742WikidataQ43447510 ScholiaQ43447510MaRDI QIDQ1621089FDOQ1621089

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)

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.

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

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

zbMATH Keywords

phylogenetic treereconstructionsequence lengthinformation content

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Teasing Apart Two Trees
• Mathematical aspects of phylogenetic groves
• Significance of the length of the shortest tree
• 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)