Generalized Fitch Graphs II: Sets of Binary Relations that are explained by Edge-labeled Trees
share
Fitch graphs G=(X,E) are digraphs that are explained by {∅, 1}-edge-labeled rooted trees T with leaf set X: there is an arc (x,y) ∈ E if and only if the unique path in T that connects the last common ancestor lca(x,y) of x and y with y contains at least one edge with label "1". In practice, Fitch graphs represent xenology relations, i.e., pairs of genes x and y for which a horizontal gene transfer happened along the path from lca(x,y) to y. In this contribution, we generalize the concept of Fitch graphs and consider trees T that are equipped with edge-labeling λ: E→P(M) that assigns to each edge a subset M'⊆ M of colors. Given such a tree, we can derive a map ε_(T,λ) (or equivalently a set of not necessarily disjoint binary relations), such that i∈ε_(T,λ)(x,y) (or equivalently (x,y)∈ R_i) with x,y∈ X, if and only if there is at least one edge with color i from lca(x,y) to y. The central question considered here: Is a given map ε a Fitch map, i.e., is there there an edge-labeled tree (T,λ) with ε_(T,λ) = ε, and thus explains ε? Here, we provide a characterization of Fitch maps in terms of certain neighborhoods and forbidden submaps. Further restrictions of Fitch maps are considered. Moreover, we show that the least-resolved tree explaining a Fitch map is unique (up to isomorphism). In addition, we provide a polynomial-time algorithm to decide whether ε is a Fitch map and, in the affirmative case, to construct the (up to isomorphism) unique least-resolved tree (T^*,λ^*) that explains ε.
READ FULL TEXT