The question whether a partition $\mathcal\P\$ and a hierarchy $\mathcal\H\$ or a tree-like split system $\mathfrak\S\$ are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether the sets of $\mathcal\P\$coincide with leaf sets of connected components obtained by deleting some edges from the tree $T$ that represents $\mathcal\H\$ or $\mathfrak\S\$, respectively. More generally, we ask whether a refinement $T^*$ of $T$ exists such that $T^*$ and $\mathcal\P\$ 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 $\mathcal\P\$. 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.
%0 Journal Article
%1 Hellmuth2021-nd
%A Hellmuth, Marc
%A Schaller, David
%A Stadler, Peter F
%D 2021
%I arXiv
%K
%T Compatibility of partitions with trees, hierarchies, and split systems
%X The question whether a partition $\mathcal\P\$ and a hierarchy $\mathcal\H\$ or a tree-like split system $\mathfrak\S\$ are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether the sets of $\mathcal\P\$coincide with leaf sets of connected components obtained by deleting some edges from the tree $T$ that represents $\mathcal\H\$ or $\mathfrak\S\$, respectively. More generally, we ask whether a refinement $T^*$ of $T$ exists such that $T^*$ and $\mathcal\P\$ 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 $\mathcal\P\$. 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.
@article{Hellmuth2021-nd,
abstract = {The question whether a partition $\mathcal\{P\}$ and a hierarchy $\mathcal\{H\}$ or a tree-like split system $\mathfrak\{S\}$ are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether the sets of $\mathcal\{P\}$coincide with leaf sets of connected components obtained by deleting some edges from the tree $T$ that represents $\mathcal\{H\}$ or $\mathfrak\{S\}$, respectively. More generally, we ask whether a refinement $T^*$ of $T$ exists such that $T^*$ and $\mathcal\{P\}$ 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 $\mathcal\{P\}$. 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.},
added-at = {2024-09-10T11:56:37.000+0200},
author = {Hellmuth, Marc and Schaller, David and Stadler, Peter F},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/2d75d052eea612ed0bcab6a23a9f14214/scadsfct},
interhash = {108d97c37f5cddcbb423b31b5b60a657},
intrahash = {d75d052eea612ed0bcab6a23a9f14214},
keywords = {},
publisher = {arXiv},
timestamp = {2024-09-10T15:15:57.000+0200},
title = {Compatibility of partitions with trees, hierarchies, and split systems},
year = 2021
}
