19 papers
Arboreal Networks and Ultrametrics
Katharina T. Huber, Vincent Moulton, Guillaume E. Scholz
Ultametrics are an important class of distances used in applications such as phylogenetics, clustering and classification theory. Ultrametrics are essentially distances that can be…
Inferring DAGs and Phylogenetic Networks from Least Common Ancestors
Anna Lindeberg, Anton Alfonsson, Vincent Moulton +2
A least common ancestor (LCA) of two leaves in a directed acyclic graph (DAG) is a vertex that is an ancestor of both leaves and has no proper descendant that is also their common…
Orthology and Near-Cographs in the Context of Phylogenetic Networks
Anna Lindeberg, Guillaume E. Scholz, Nicolas Wieseke +1
Orthologous genes, which arise through speciation, play a key role in comparative genomics and functional inference. In particular, graph-based methods allow for the inference of o…
Representing distance-hereditary graphs with multi-rooted trees
Guillaume E. Scholz
Arboreal networks are a generalization of rooted trees, defined by keeping the tree-like structure, but dropping the requirement for a single root. Just as the class of cographs is…
Network Representation and Modular Decomposition of Combinatorial Structures: A Galled-Tree Perspective
Anna Lindeberg, Guillaume E. Scholz, Marc Hellmuth
In phylogenetics, reconstructing rooted trees from distances between taxa is a common task. Böcker and Dress generalized this concept by introducing symbolic dated maps $δ:X \times…
The Complement of the Djokovic-Winkler Relation
Marc Hellmuth, Bruno J. Schmidt, Guillaume E. Scholz +1
The Djoković-Winkler relation is a binary relation defined on the edge set of a given graph that is based on the distances of certain vertices and which plays a prominent role…
Is this network proper forest-based?
Katharina T. Huber, Leo van Iersel, Vincent Moulton +1
In evolutionary biology, networks are becoming increasingly used to represent evolutionary histories for species that have undergone non-treelike or reticulate evolution. Such netw…
Shared ancestry graphs and symbolic arboreal maps
Katharina T. Huber, Vincent Moulton, Guillaume E. Scholz
A network on a finite set , , is a connected directed acyclic graph with leaf set in which every root in has outdegree at least 2 and no vertex in has…
Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
Marc Hellmuth, Guillaume E. Scholz
The class of lled-ree plainable () graphs has recently been discovered as a natural generalization of cographs. Cographs are p…
Injective split systems
M. Hellmuth, K. T. Huber, V. Moulton +2
A split system on a finite set , , is a set of bipartitions or splits of which contains all splits of the form , . To any such…
Resolving Prime Modules: The Structure of Pseudo-cographs and Galled-Tree Explainable Graphs
Marc Hellmuth, Guillaume E. Scholz
The modular decomposition of a graph is a natural construction to capture key features of in terms of a labeled tree whose vertices are labeled as "series" (), "…
Compatible split systems on a multiset
Vincent Moulton, Guillaume E. Scholz
A split system on a multiset is a set of bipartitions of . Such a split system is compatible if it can be represented by a tree in such a way…
Forest-based networks
Katharina T. Huber, Vincent Moulton, Guillaume E. Scholz
In evolutionary studies it is common to use phylogenetic trees to represent the evolutionary history of a set of species. However, in case the transfer of genes or other genetic in…
From Modular Decomposition Trees to Level-1 Networks: Pseudo-Cographs, Polar-Cats and Prime Polar-Cats
Marc Hellmuth, Guillaume E. Scholz
The modular decomposition of a graph is a natural construction to capture key features of in terms of a labeled tree whose vertices are labeled as "series" (), "…
Overlaid species forests
K. T. Huber, V. Moulton, G. E. Scholz
Introgression is an evolutionary process in which genes or other types of genetic material are introduced into a genome. It is an important evolutionary process that can, for examp…
Phylogenetic networks that are their own fold-ups
Katharina T. Huber, Guillaume E. Scholz
Phylogenetic networks are becoming of increasing interest to evolutionary biologists due to their ability to capture complex non-treelike evolutionary processes. From a combinatori…
Three-way symbolic tree-maps and ultrametrics
Katharina T. Huber, Vincent Moulton, Guillaume E. Scholz
Three-way dissimilarities are a generalization of (two-way) dissimilarities which can be used to indicate the lack of homogeneity or resemblance between any three objects. Such map…
Beyond representing orthology relations by trees
K. T. Huber, G. E. Scholz
Reconstructing the evolutionary past of a family of genes is an important aspect of many genomic studies. To help with this, simple operations on a set of sequences called ortholog…
Bridging the gap between rooted and unrooted phylogenetic networks
Philippe Gambette, Katharina T. Huber, Guillaume E. Scholz
The need for structures capable of accommodating complex evolutionary signals such as those found in, for example, wheat has fueled research into phylogenetic networks. Such struct…