Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees

DOI10.1016/J.DAM.2020.01.036zbMATH Open1442.05031arXiv1911.07469OpenAlexW3007983209MaRDI QIDQ2192103FDOQ2192103

Marc Hellmuth, Peter F. Stadler, Carsten R. Seemann

Publication date: 29 June 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Fitch graphs $G=(X,E)$ are digraphs that are explained by $emptyset,1$-edge-labeled rooted trees $T$ with leaf set $X$: there is an arc $(x,y)inE$ if and only if the unique path in $T$ that connects the last common ancestor $mathrmlca(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 $mathrmlca(x,y)$ to $y$. In this contribution, we generalize the concept of Fitch graphs and consider trees $T$ that are equipped with edge-labeling $lambda:EomathcalP(M)$ that assigns to each edge a subset $M^{\prime }subseteqM$ of colors. Given such a tree, we can derive a map $varepsilo{n}_{(T,lambda)}$ (or equivalently a set of not necessarily disjoint binary relations), such that $iinvarepsilo{n}_{(T,lambda)}(x,y)$ (or equivalently $(x,y)in{R}_i$) with $x,yinX$, if and only if there is at least one edge with color $i$ from $mathrmlca(x,y)$ to $y$. The central question considered here: Is a given map $varepsilon$ a Fitch map, i.e., is there there an edge-labeled tree $(T,lambda)$ with $varepsilo{n}_{(T,lambda)}=varepsilon$, and thus explains $varepsilon$? 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 $varepsilon$ is a Fitch map and, in the affirmative case, to construct the (up to isomorphism) unique least-resolved tree $(T^{*},lambd{a}^{*})$ that explains $varepsilon$.

Full work available at URL: https://arxiv.org/abs/1911.07469

Recommendations

• Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees
• Generalized Fitch graphs. III: Symmetrized Fitch maps and sets of symmetric binary relations that are explained by unrooted edge-labeled trees
• A short note on undirected Fitch graphs
• Reconstructing gene trees from Fitch's xenology relation
• Alternative characterizations of Fitch's xenology relation

zbMATH Keywords

phylogeneticsforbidden subgraphsrecognition algorithmlabeled treesFitch map

Mathematics Subject Classification ID

Applications of graph theory (05C90) Genetics and epigenetics (92D10) Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Title not available (Why is that?)
• Complement reducible graphs
• Extension operations on sets of leaf-labelled trees
• Fully dynamic recognition algorithm and certificate for directed cographs
• On a class of posets and the corresponding comparability graphs
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Linear-time modular decomposition of directed graphs
• Theory of 2-structures. II: Representation through labeled tree families
• Closure operations in phylogenetics
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Beyond representing orthology relations by trees
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• Orthology relations, symbolic ultrametrics, and cographs
• Leaf Powers and Their Properties: Using the Trees
• Reconstructing unrooted phylogenetic trees from symbolic ternary metrics
• The matroid structure of representative triple sets and triple-closure computation
• Reconstructing gene trees from Fitch's xenology relation
• Inferring phylogenetic trees from the knowledge of rare evolutionary events
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• Pairwise Compatibility Graphs: A Survey
• A short note on undirected Fitch graphs
• Best match graphs
• Alternative characterizations of Fitch's xenology relation
• Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees
• Three-way symbolic tree-maps and ultrametrics

Cited In (2)

• Compatibility of partitions with trees, hierarchies, and split systems
• From modular decomposition trees to rooted median graphs

This page was built for publication: Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2192103)