Slim sets of binary trees

DOI10.1016/J.JCTA.2011.09.007MaRDI QIDQ654890zbMATH OpenOpenAlexFDO

Authors Stefan Grünewald

Publication date 23 December 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

phylogenetic treephylogeneticssupertreesquartet sets

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05)

Abstract: A classical problem in phylogenetic tree analysis is to decide whether there is a phylogenetic tree $T$ that contains all information of a given collection $cP$ of phylogenetic trees. If the answer is "yes" we say that $cP$ is compatible and $T$ displays $cP$. This decision problem is NP-complete even if all input trees are quartets, that is binary trees with exactly four leaves. In this paper, we prove a sufficient condition for a set of binary phylogenetic trees to be compatible. That result is used to give a short and self-contained proof of the known characterization of quartet sets of minimal cardinality which are displayed by a unique phylogenetic tree.

Recommendations

• Extension operations on sets of leaf-labelled trees
• Reconstructing phylogenetic trees from multipartite quartet systems
• Quartet compatibility and the quartet graph
• On the compatibility of quartet trees
• On the compatibility of quartet trees

Cites work

• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• A note on maximal hierarchies
• Algorithmic Aspects of Tree Amalgamation
• Classification, clustering, and data mining applications. Proceedings of the meeting of the International Federation of Classification Societies (IFCS), Chicago, IL, USA, July 15--18, 2004.
• From subtrees to supertrees
• Patching up \(X\)-trees
• Patchworks
• Phylogenetic supertrees. Combining information to reveal the tree of life
• The complexity of reconstructing trees from qualitative characters and subtrees

Cited in

(3)

• On the quartet distance given partial information
• Quartet compatibility and the quartet graph
• Phylogenetic flexibility via Hall-type inequalities and submodularity

This page was built for publication: Slim sets of binary trees

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