Compatibility of partitions with trees, hierarchies, and split systems

DOI10.1016/J.DAM.2022.03.014MaRDI QIDQ2127632zbMATH OpenOpenAlexFDO

Authors Marc Hellmuth, David Schaller, Peter F. Stadler

Publication date 20 April 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

compatibilityFitch maphierarchypartitionphylogenetic treerecognition algorithmsplit system

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Applications of graph theory (05C90) Problems related to evolution (92D15)

Abstract: The question whether a partition $mathcalP$ and a hierarchy $mathcalH$ or a tree-like split system $mathfrakS$ are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether the sets of $mathcalP$coincide with leaf sets of connected components obtained by deleting some edges from the tree $T$ that represents $mathcalH$ or $mathfrakS$, respectively. More generally, we ask whether a refinement $T^{\ast }$ of $T$ exists such that $T^{\ast }$ and $mathcalP$ are compatible in this sense. The latter is closely related to the question as to whether there exists a tree at all that is compatible with $mathcalP$. We report several characterizations for (refinements of) hierarchies and split systems that are compatible with (systems of) partitions. In addition, we provide a linear-time algorithm to check whether refinements of trees and a given partition are compatible. The latter problem becomes NP-complete but fixed-parameter tractable if a system of partitions is considered instead of a single partition. In this context, we also explore the close relationship of the concept of compatibility and so-called Fitch maps.

Recommendations

• A novel insight into the perfect phylogeny problem
• Convex tree realizations of partitions
• Extension operations on sets of leaf-labelled trees
• Identifying phylogenetic trees
• Compatibility, incompatibility, tree-width, and forbidden phylogenetic minors

Cites work

• A short note on undirected Fitch graphs
• Basic phylogenetic combinatorics.
• Best match graphs with binary trees
• Braids of partitions
• Compatibility of unrooted phylogenetic trees is FPT
• Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees
• Generalized Fitch graphs. III: Symmetrized Fitch maps and sets of symmetric binary relations that are explained by unrooted edge-labeled trees
• Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees
• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• scientific article; zbMATH DE number 3204690 (Why is no real title available?)
• Lowest common ancestors in trees and directed acyclic graphs
• On the structure of the tight-span of a totally split-decomposable metric
• Reconstructing gene trees from Fitch's xenology relation
• Representing partitions on trees

Cited in

(6)

• Combining tree partitioning, precedence, and incomparability constraints
• Convex tree realizations of partitions
• Representing partitions on trees
• Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees
• The space of equidistant phylogenetic cactuses
• Can you tell a tree from its branches?

This page was built for publication: Compatibility of partitions with trees, hierarchies, and split systems

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