2018/02/10 by Hellmuth, Marc
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1802.03657
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 \textrmlca(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 \textrmlca(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 the unique least resolved phylogenetic tree that explains (K|X|,ε).