Best match graphs arise naturally as the first processing intermediate in algorithms for orthology detection. Let T be a phylogenetic (gene) tree T and \(\sigma \) an assignment of leaves of T to species. The best match graph \((G,\sigma )\) is a digraph that contains an arc from x to y if the genes x and y reside in different species and y is one of possibly many (evolutionary) closest relatives of x compared to all other genes contained in the species \(\sigma (y)\). Here, we characterize best match graphs and show that it can be decided in cubic time and quadratic space whether \((G,\sigma )\) derived from a tree in this manner. If the answer is affirmative, there is a unique least resolved tree that explains \((G,\sigma )\), which can also be constructed in cubic time.

Genome-scale orthology assignments are usually based on reciprocal best matches. In the absence of horizontal gene transfer (HGT), every pair of orthologs forms a reciprocal best match. Incorrect orthology assignments therefore are always false positives in the reciprocal best match graph. We consider duplication/loss scenarios and characterize unambiguous false-positive (u-fp) orthology assignments, that is, edges in the best match graphs (BMGs) that cannot correspond to orthologs for any gene tree that explains the BMG. Moreover, we provide a polynomial-time algorithm to identify allu-fporthology assignments in a BMG. Simulations show that at least $$75\%$$75% of all incorrect orthology assignments can be detected in this manner. All results rely only on the structure of the BMGs andnoton anya prioriknowledge about underlying gene or species trees.

A wide variety of problems in computational biology, most notably the assessment of orthology, are solved with the help of reciprocal best matches. Using an evolutionary definition of best matches that captures the intuition behind the concept we clarify rigorously the relationships between reciprocal best matches, orthology, and evolutionary events under the assumption of duplication/loss scenarios. We show that the orthology graph is a subgraph of the reciprocal best match graph (RBMG). We furthermore give conditions under which an RBMG that is a cograph identifies the correct orthlogy relation. Using computer simulations we find that most false positive orthology assignments can be identified as so-called good quartets—and thus corrected—in the absence of horizontal transfer. Horizontal transfer, however, may introduce also false-negative orthology assignments.

Fitch graphs have been introduced as a model of xenology relationships in phylogenomics. Directed Fitch graphs G = (X, E) are di-graphs that are explained by {0, 1}-edge-labeled rooted trees with leaf set X: there is an arc xy ∈ E if and only if the unique path in T that connects the least common ancestor lca(x, y) of x and y with y contains at least one edge with label 1. In this contribution, we consider the undirected version of Fitch’s xenology relation, in which x and y are xenologs if and only if the unique path between x and y in T contains an edge with label 1. We show that symmetric Fitch relations coincide with class of complete multipartite graph and thus cannot convey any non-trivial phylogenetic information.