Generalized Fitch Graphs: Edge-labeled Graphs that are explained by Edge-labeled Trees
share
Fitch graphs G=(X,E) are di-graphs that are explained by {⊗,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 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 xenology and Fitch graphs and consider complete di-graphs K_|X| with vertex set X and a map ϵ that assigns to each arc xy a unique label ϵ(x,y)∈ M∪{⊗}, where M denotes an arbitrary set of symbols. A di-graph (K_|X|,ϵ) is a generalized Fitch graph if there is an M∪{⊗}-edge-labeled tree (T,λ) that can explain (K_|X|,ϵ). We provide a simple characterization of generalized Fitch graphs (K_|X|,ϵ) and give an O(|X|^2)-time algorithm for their recognition as well as for the reconstruction of a least resolved phylogenetic tree that explains (K_|X|,ϵ).
READ FULL TEXT