Name
Abstract | ||
|---|---|---|
The question whether a partition P and a hierarchy H or a tree-like split system S are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether the sets of P coincide with leaf sets of connected components obtained by deleting some edges from the tree T that represents H or S, respectively. More generally, we ask whether a refinement T* of T exists such that T* and 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 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. (C) 2022 The Author(s). Published by Elsevier B.V. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.dam.2022.03.014 | DISCRETE APPLIED MATHEMATICS |
Keywords | DocType | Volume |
Hierarchy, Split system, Phylogenetic tree, Partition, Compatibility, Recognition algorithm, Fitch map | Journal | 314 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marc Hellmuth | 1 | 0 | 1.01 |
| David Schaller | 2 | 0 | 0.34 |
| Peter F. Stadler | 3 | 256 | 62.77 |