| 1. |
- Bruckmann, Carmen, et al.
(författare)
-
From modular decomposition trees to rooted median graphs
- 2022
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 310, s. 1-9
-
Tidskriftsartikel (refereegranskat)abstract
- The modular decomposition of a symmetric map δ:X×X→Υ (or, equivalently, a set of pairwise-disjoint symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of δ in terms of a labeled tree. A map δ is explained by a vertex-labeled rooted tree (T,t) if the label δ(x,y) coincides with the label of the lowest 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 explained in this manner. Here we consider rooted median graphs as a generalization of (modular decomposition) trees to explain symmetric maps. We derive 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 δ.
|
|
| 2. |
- Hartman, Tom, et al.
(författare)
-
Complete edge-colored permutation graphs
- 2022
-
Ingår i: Advances in Applied Mathematics. - : Elsevier BV. - 0196-8858 .- 1090-2074. ; 139
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce the concept of complete edge-colored permutation graphs as complete graphs that are the edge-disjoint union of classical permutation graphs. We show that a graph G = (V, E) is a complete edge-colored permutation graph if and only if each monochromatic subgraph of G is a classical permutation graph and G does not contain a triangle with 3 different colors. Using the modular decomposition as a framework we demonstrate that complete edge-colored permutation graphs are characterized in terms of their strong prime modules, which induce also complete edge-colored permutation graphs. This leads to an O (|V|(2))-time recognition algoriyhm. We show, moreover, that complete edge-colored permutation graphs form a superclass of so-called symbolic ultrametrics and that the coloring of such graphs is always a Gallai coloring.
|
|
| 3. |
- Hellmuth, Marc, 1980-, et al.
(författare)
-
Clustering systems of phylogenetic networks
- 2023
-
Ingår i: Theory in biosciences. - 1431-7613 .- 1611-7530. ; :142, s. 301-358
-
Tidskriftsartikel (refereegranskat)abstract
- Rooted acyclic graphs appear naturally when the phylogenetic relationship of a set X of taxa involves not only speciations but also recombination, horizontal transfer, or hybridization that cannot be captured by trees. A variety of classes of such networks have been discussed in the literature, including phylogenetic, level-1, tree-child, tree-based, galled tree, regular, or normal networks as models of different types of evolutionary processes. Clusters arise in models of phylogeny as the sets C(v) of descendant taxa of a vertex v. The clustering system CN comprising the clusters of a network N conveys key information on N itself. In the special case of rooted phylogenetic trees, T is uniquely determined by its clustering system CT. Although this is no longer true for networks in general, it is of interest to relate properties of N and CN. Here, we systematically investigate the relationships of several well-studied classes of networks and their clustering systems. The main results are correspondences of classes of networks and clustering systems of the following form: If N is a network of type X, then CN satisfies Y, and conversely if C is a clustering system satisfying Y, then there is network N of type X such that C⊆CN.This, in turn, allows us to investigate the mutual dependencies between the distinct types of networks in much detail.
|
|
| 4. |
- Hellmuth, Marc, et al.
(författare)
-
Combining Orthology and Xenology Data in a Common Phylogenetic Tree
- 2021
-
Ingår i: Advances in Bioinformatics and Computational Biology. - Cham : Springer. - 9783030918132 - 9783030918149 ; , s. 53-64
-
Konferensbidrag (refereegranskat)abstract
- In mathematical phylogenetics, types of events in a gene tree T are formalized by vertex labels t(v) and set-valued edge labels λ(e). The orthology and paralogy relations between genes are a special case of a map δ on the pairs of leaves of T defined by δ(x,y)=q if the last common ancestor lca(x,y) of x and y is labeled by an event type q, e.g., speciation or duplication. Similarly, a map εε with m∈ε(x,y) if m∈λ(e) for at least one edge e along the path from lca(x,y) to y generalizes xenology, i.e., horizontal gene transfer. We show that a pair of maps (δ,ε) derives from a tree (T,t,λ) in this manner if and only if there exists a common refinement of the (unique) least-resolved vertex labeled tree (Tδ,tδ) that explains δ and the (unique) least-resolved edge labeled tree (Tε,λε) that explains ε (provided both trees exist). This result remains true if certain combinations of labels at incident vertices and edges are forbidden.
|
|
| 5. |
- Hellmuth, Marc, et al.
(författare)
-
Compatibility of partitions with trees, hierarchies, and split systems
- 2022
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 314, s. 265-283
-
Tidskriftsartikel (refereegranskat)abstract
- The question whether a partition P and a hierarchy H or a tree-like split system S are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether the sets of P coincide with leaf sets of connected components obtained by deleting some edges from the tree T that represents H or S, respectively. More generally, we ask whether a refinement T∗ of T exists such that T∗ and P are compatible in this sense. The latter is closely related to the question as to whether there exists a tree at all that is compatible with P. We report several characterizations for (refinements of) hierarchies and split systems that are compatible with (systems of) partitions. In addition, we provide a linear-time algorithm to check whether refinements of trees and a given partition are compatible. The latter problem becomes NP-complete but fixed-parameter tractable if a system of partitions is considered instead of a single partition. In this context, we also explore the close relationship of the concept of compatibility and so-called Fitch maps.
|
|
| 6. |
- Hellmuth, Marc, et al.
(författare)
-
Fitch Graph Completion
- 2023
-
Ingår i: Lecture Notes in Computer Science. - 0302-9743 .- 1611-3349. ; , s. 225-237
-
Tidskriftsartikel (refereegranskat)
|
|
| 7. |
- Hellmuth, Marc, et al.
(författare)
-
From modular decomposition trees to level-1 networks : Pseudo-cographs, polar-cats and prime polar-cats
- 2022
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 321, s. 179-219
-
Tidskriftsartikel (refereegranskat)abstract
- The modular decomposition of a graph G is a natural construction to capture key features of G in terms of a labeled tree (T, t) whose vertices are labeled as series(1), parallel(0) or prime. However, full information of G is provided by its modular decomposition tree (T, t) only, if G does not contain prime modules. In this case, (T, t) explains G, i.e., {x, y} is an element of E(G) if and only if the lowest common ancestor lca(T)(x, y) of x and y has label 1. This information, however, gets lost whenever (T, t) contains vertices with label prime. In this contribution, we aim at replacing prime vertices in (T, t) by simple 0/1-labeled cycles, which leads to the concept of rooted labeled level-1 networks (N, t).We characterize graphs that can be explained by such level-1 networks (N, t), which generalizes the concept of graphs that can be explained by labeled trees, that is, cographs. We provide three novel graph classes: polar-cats are a proper subclass of pseudo-cographs which forms a proper subclass of prime polar-cats. In particular, every cograph is a pseudo-cograph and prime polar-cats are precisely those graphs that can be explained by a labeled level-1 network. The class of prime polar-cats is defined in terms of the modular decomposition of graphs and the property that all prime modules induce polar-cats. We provide a plethora of structural results and characterizations for graphs of these new classes.In particular, Polar-cats are precisely those graphs that can be explained by an elementary level-1 network (N, t), i.e., (N, t) contains exactly one cycle C that is rooted at the root rho(N) of N and where rho(N) has exactly two children while every vertex distinct from rho(N) has a unique child that is not located in C. Pseudo-cographs are less restrictive and those graphs that can be explained by particular level-1 networks (N, t) that contain at most one cycle. These findings, eventually, help us to characterize the class of all graphs that can be explained by labeled level-1 networks, namely prime polar-cats. Moreover, we show under which conditions there is a unique least-resolved labeled level-1 network that explains a given graph. In addition, we provide linear-time algorithms to recognize all these types of graphs and to construct level-1 networks to explain them.
|
|
| 8. |
- Hellmuth, Marc, et al.
(författare)
-
Generalized Fitch Graphs III : Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edge-labeled Trees
- 2021
-
Ingår i: Discrete Mathematics & Theoretical Computer Science. - : Centre pour la Communication Scientifique Directe (CCSD). - 1462-7264 .- 1365-8050. ; 23:1
-
Tidskriftsartikel (refereegranskat)abstract
- Binary relations derived from labeled rooted trees play an import role in mathematical biology as formal models of evolutionary relationships. The (symmetrized) Fitch relation formalizes xenology as the pairs of genes separated by at least one horizontal transfer event. As a natural generalization, we consider symmetrized Fitch maps, that is, symmetric maps epsilon that assign a subset of colors to each pair of vertices in X and that can be explained by a tree T with edges that are labeled with subsets of colors in the sense that the color m appears in epsilon(x, y) if and only if m appears in a label along the unique path between x and y in T. We first give an alternative characterization of the monochromatic case and then give a characterization of symmetrized Fitch maps in terms of compatibility of a certain set of quartets. We show that recognition of symmetrized Fitch maps is NP-complete. In the restricted case where vertical bar epsilon(x, y)vertical bar <= 1 the problem becomes polynomial, since such maps coincide with class of monochromatic Fitch maps whose graph-representations form precisely the class of complete multi-partite graphs.
|
|
| 9. |
- Hellmuth, Marc, 1980-, et al.
(författare)
-
Injective Split Systems
- 2023
-
Ingår i: Graphs and Combinatorics. - 0911-0119 .- 1435-5914. ; 39:4
-
Tidskriftsartikel (refereegranskat)abstract
- A split system S on a finite set X, |X|≥3, is a set of bipartitions or splits of X which contains all splits of the form {x,X−{x}}, x∈X. To any such split system S we can associate the Buneman graph B(S) which is essentially a median graph with leaf-set X that displays the splits in S. In this paper, we consider properties of injective split systems, that is, split systems S with the property that medB(S)(Y)≠medB(S)(Y′) for any 3-subsets Y,Y′ in X, where medB(S)(Y)med denotes the median in B(S) of the three elements in Y considered as leaves in B(S). In particular, we show that for any set X there always exists an injective split system on X, and we also give a characterization for when a split system is injective. We also consider how complex the Buneman graph B(S) needs to become in order for a split system S on X to be injective. We do this by introducing a quantity for |X| which we call the injective dimension for |X|, as well as two related quantities, called the injective 2-split and the rooted-injective dimension. We derive some upper and lower bounds for all three of these dimensions and also prove that some of these bounds are tight. An underlying motivation for studying injective split systems is that they can be used to obtain a natural generalization of symbolic tree maps. An important consequence of our results is that any three-way symbolic map on X can be represented using Buneman graphs.
|
|
| 10. |
|
|
