Slim sets of binary trees

DOI10.1016/J.JCTA.2011.09.007zbMATH Open1232.05054arXiv1006.5280OpenAlexW2026340248MaRDI QIDQ654890FDOQ654890

Authors: Stefan Grünewald 

Publication date: 23 December 2011

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

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.

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

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

zbMATH Keywords

phylogenetic treephylogeneticssupertreesquartet sets

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The complexity of reconstructing trees from qualitative characters and subtrees
• Phylogenetic supertrees. Combining information to reveal the tree of life
• Patching up \(X\)-trees
• A note on maximal hierarchies
• 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
• Algorithmic Aspects of Tree Amalgamation
• Patchworks

Cited In (3)

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

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)