The modular decomposition of a symmetric map $\deltaXX \Upsilon$ (or, equivalently, a set of symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of $\delta$ in labeled trees. A map $\delta$ is explained by a vertex-labeled rooted tree $(T,t)$ if the label $\delta(x,y)$ coincides with the label of the last common ancestor of $x$ and $y$ in $T$, i.e., if $\delta(x,y)=t(\mathrmłca\(x,y))$. Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be exaplained in this manner. Here we consider rooted median graphs as a generalization to (modular decomposition) trees to explain symmetric maps. We first show that every symmetric map can be explained by ``extended'' hypercubes and half-grids. We then derive a a linear-time algorithm that stepwisely resolves prime vertices in the modular decomposition tree to obtain a rooted and labeled median graph that explains a given symmetric map $\delta$. We argue that the resulting ``tree-like'' median graphs may be of use in phylogenetics as a model of evolutionary relationships.
%0 Journal Article
%1 Bruckmann2021-qg
%A Bruckmann, Carmen
%A Stadler, Peter F
%A Hellmuth, Marc
%D 2021
%I arXiv
%K
%T From modular decomposition trees to rooted median graphs
%X The modular decomposition of a symmetric map $\deltaXX \Upsilon$ (or, equivalently, a set of symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of $\delta$ in labeled trees. A map $\delta$ is explained by a vertex-labeled rooted tree $(T,t)$ if the label $\delta(x,y)$ coincides with the label of the last common ancestor of $x$ and $y$ in $T$, i.e., if $\delta(x,y)=t(\mathrmłca\(x,y))$. Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be exaplained in this manner. Here we consider rooted median graphs as a generalization to (modular decomposition) trees to explain symmetric maps. We first show that every symmetric map can be explained by ``extended'' hypercubes and half-grids. We then derive a a linear-time algorithm that stepwisely resolves prime vertices in the modular decomposition tree to obtain a rooted and labeled median graph that explains a given symmetric map $\delta$. We argue that the resulting ``tree-like'' median graphs may be of use in phylogenetics as a model of evolutionary relationships.
@article{Bruckmann2021-qg,
abstract = {The modular decomposition of a symmetric map $\delta{}\colon X\times X \to \Upsilon$ (or, equivalently, a set of symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of $\delta$ in labeled trees. A map $\delta$ is explained by a vertex-labeled rooted tree $(T,t)$ if the label $\delta{}(x,y)$ coincides with the label of the last common ancestor of $x$ and $y$ in $T$, i.e., if $\delta{}(x,y)=t(\mathrm\{lca\}(x,y))$. Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be exaplained in this manner. Here we consider rooted median graphs as a generalization to (modular decomposition) trees to explain symmetric maps. We first show that every symmetric map can be explained by ``extended'' hypercubes and half-grids. We then derive a a linear-time algorithm that stepwisely resolves prime vertices in the modular decomposition tree to obtain a rooted and labeled median graph that explains a given symmetric map $\delta$. We argue that the resulting ``tree-like'' median graphs may be of use in phylogenetics as a model of evolutionary relationships.},
added-at = {2024-09-10T12:10:36.000+0200},
author = {Bruckmann, Carmen and Stadler, Peter F and Hellmuth, Marc},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/29ba475d45a4e96db825638e50d0be023/scadsfct},
interhash = {90541f058d367918a61c0b7f2629ed90},
intrahash = {9ba475d45a4e96db825638e50d0be023},
keywords = {},
publisher = {arXiv},
timestamp = {2024-09-10T15:15:57.000+0200},
title = {From modular decomposition trees to rooted median graphs},
year = 2021
}
