Abstract. Horizontal gene transfer (HGT) events partition a gene tree [Formula: see text], and thus its leaf set [Formula: see text], into subsets of genes whose evolutionary history is described by speciation and duplication events alone. Two genes thus are xenologs if and only if they belong to two different sets of this partition [Formula: see text]. Indirect phylogenetic methods can be used to infer the partition [Formula: see text] of [Formula: see text] from sequence similarity or evolutionary distances without any a priori knowledge about the underlying tree [Formula: see text]. In this contribution, we assume that a partition [Formula: see text] of the gene set [Formula: see text] and a usually incompletely resolved estimate [Formula: see text] of the original gene tree on [Formula: see text] are known. We then ask to what extent [Formula: see text] and [Formula: see text] can be combined to determine the horizontal transfer edges in [Formula: see text] and thus the orientation of the HGT events that separate the sets of [Formula: see text]. If [Formula: see text] and [Formula: see text] are compatible, it can be decided for each pair of genes [Formula: see text] and [Formula: see text] whether there always exists or never exists a horizontal gene transfer in [Formula: see text] along the path connecting [Formula: see text] and the most recent common ancestor of [Formula: see text] and [Formula: see text], and thus a directed edge [Formula: see text] in the so-called Fitch graph of the gene family. We generalize this result to insufficiently resolved gene trees. We show that the classification of a gene pair [Formula: see text] can be computed in constant time after linear-time preprocessing. Using simulated gene family histories, we observe empirically that the vast majority of horizontal transfer edges in the gene tree [Formula: see text] can be recovered unambiguously from the knowledge of the partition [Formula: see text]. All algorithms developed here are implemented and freely available within the Python package AsymmeTree hosted at https://github.com/david-schaller/AsymmeTree .

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.

Best match graphs (BMGs) are vertex-colored directed graphs that were introduced to model the relationships of genes (vertices) from different species (colors) given an underlying evolutionary tree that is assumed to be unknown. In real-life applications, BMGs are estimated from sequence similarity data. Measurement noise and approximation errors usually result in empirically determined graphs that in general violate characteristic properties of BMGs. The arc modification problems for BMGs aim at correcting such violations and thus provide a means to improve the initial estimates of best match data. We show here that the arc deletion, arc completion and arc editing problems for BMGs are NP-complete and that they can be formulated and solved as integer linear programs. To this end, we provide a novel characterization of BMGs in terms of triples (binary trees on three leaves) and a characterization of BMGs with two colors in terms of forbidden subgraphs.