From Modular Decomposition Trees to Rooted Median Graphs

03/11/2021
by   Carmen Bruckmann, et al.
0

The modular decomposition of a symmetric map δ X× X →Υ (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 δ in labeled trees. A map δ is explained by a vertex-labeled rooted tree (T,t) if the label δ(x,y) coincides with the label of the last common ancestor of x and y in T, i.e., if δ(x,y)=t(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 δ. We argue that the resulting "tree-like" median graphs may be of use in phylogenetics as a model of evolutionary relationships.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset