research
∙
06/12/2023
Fitch Graph Completion
Horizontal gene transfer is an important contributor to evolution. Accor...
share
research
∙
06/07/2023
Linear Time Algorithms for NP-hard Problems restricted to GaTEx Graphs
The class of Galled-Tree Explainable (GaTEx) graphs has just recently be...
research
∙
04/24/2023
The Theory of Gene Family Histories
Most genes are part of larger families of evolutionary related genes. Th...
research
∙
04/13/2023
On a generalization of median graphs: k-median graphs
Median graphs are connected graphs in which for all three vertices there...
research
∙
12/05/2022
Relative Timing Information and Orthology in Evolutionary Scenarios
Evolutionary scenarios describing the evolution of a family of genes wit...
research
∙
11/30/2022
Resolving Prime Modules: The Structure of Pseudo-cographs and Galled-Tree Explainable Graphs
The modular decomposition of a graph G is a natural construction to capt...
research
∙
04/28/2022
Clustering Systems of Phylogenetic Networks
Rooted acyclic graphs appear naturally when the phylogenetic relationshi...
research
∙
12/10/2021
From Modular Decomposition Trees to Level-1 Networks: Pseudo-Cographs, Polar-Cats and Prime Polar-Cats
We characterize graphs G that can be explained by rooted labeled level-1...
research
∙
12/01/2021
Orientation of Fitch Graphs and Detection of Horizontal Gene Transfer in Gene Trees
Horizontal gene transfer events partition a gene tree T and thus, its le...
research
∙
10/18/2021
Planar Median Graphs and Cubesquare-Graphs
Median graphs are connected graphs in which for all three vertices there...
research
∙
09/14/2021
Construction of k-matchings and k-regular subgraphs in graph products
A k-matching M of a graph G=(V,E) is a subset M⊆ E such that each connec...
research
∙
08/09/2021
Cayley Graphs of Semigroups Applied to Atom Tracking in Chemistry
While atom tracking with isotope-labeled compounds is an essential and s...
research
∙
07/05/2021
Combining Orthology and Xenology Data in a Common Phylogenetic Tree
A rooted tree T with vertex labels t(v) and set-valued edge labels λ(e) ...
research
∙
06/30/2021
A Simple Linear-Time Algorithm for the Common Refinement of Rooted Phylogenetic Trees on a Common Leaf Set
Background. The supertree problem, i.e., the task of finding a common re...
research
∙
04/29/2021
Compatibility of Partitions, Hierarchies, and Split Systems
The question whether a partition 𝒫 and a hierarchy ℋ or a tree-like spli...
research
∙
03/11/2021
From Modular Decomposition Trees to Rooted Median Graphs
The modular decomposition of a symmetric map δ X× X →Υ (or, equivalently...
research
∙
03/11/2021
Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs
Best match graphs (BMGs) are vertex-colored digraphs that naturally aris...
research
∙
03/10/2021
Heuristic Algorithms for Best Match Graph Editing
Best match graphs (BMGs) are a class of colored digraphs that naturally ...
research
∙
01/18/2021
Least resolved trees for two-colored best match graphs
2-colored best match graphs (2-BMGs) form a subclass of sink-free bi-tra...
research
∙
12/16/2020
Indirect Identification of Horizontal Gene Transfer
Several implicit methods to infer Horizontal Gene Transfer (HGT) focus o...
research
∙
11/01/2020
Best Match Graphs with Binary Trees
Best match graphs (BMG) are a key intermediate in graph-based orthology ...
research
∙
06/30/2020
Complexity of Modification Problems for Best Match Graphs
Best match graphs (BMGs) are vertex-colored directed graphs that were in...
research
∙
06/03/2020
Complete Characterization of Incorrect Orthology Assignments in Best Match Graphs
Genome-scale orthology assignments are usually based on reciprocal best ...
research
∙
04/15/2020
Complete Edge-Colored Permutation Graphs
We introduce the concept of complete edge-colored permutation graphs as ...
research
∙
04/14/2020
Hierarchical and Modularly-Minimal Vertex Colorings
Cographs are exactly the hereditarily well-colored graphs, i.e., the gra...
research
∙
01/16/2020
Generalized Fitch Graphs III: Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edge-labeled Trees
Binary relations derived from labeled rooted trees play an import role i...
research
∙
11/18/2019
Generalized Fitch Graphs II: Sets of Binary Relations that are explained by Edge-labeled Trees
Fitch graphs G=(X,E) are digraphs that are explained by {∅, 1}-edge-labe...
research
∙
11/18/2019
Generalized Fitch Relations II: Sets of Binary Relations that are explained by Edge-labeled Trees
Fitch graphs G=(X,E) are digraphs that are explained by {∅, 1}-edge-labe...
research
∙
10/29/2019
A Graph-Based Tool to Embed the π-Calculus into a Computational DPO Framework
Graph transformation approaches have been successfully used to analyse a...
research
∙
10/29/2019
Reconstruction of time-consistent species trees
The history of gene families – which are equivalent to event-labeled gen...
research
∙
07/20/2019
Complexity of Modification Problems for Reciprocal Best Match Graphs
Reciprocal best match graphs (RBMGs) are vertex colored graphs whose ver...
research
∙
04/26/2019
Best Match Graphs and Reconciliation of Gene Trees with Species Trees
A wide variety of problems in computational biology, most notably the as...
research
∙
02/10/2018
Generalized Fitch Graphs: Edge-labeled Graphs that are explained by Edge-labeled Trees
Fitch graphs G=(X,E) are di-graphs that are explained by {⊗,1}-edge-labe...
research
∙
12/18/2017
Phylogenomics with Paralogs
Phylogenomics heavily relies on well-curated sequence data sets that con...
research
∙
12/05/2017
A Short Note on Undirected Fitch Graphs
The symmetric version of Fitch's xenology relation coincides with class ...
research
∙
11/06/2017
Reconstructing Gene Trees From Fitch's Xenology Relation
Two genes are xenologs in the sense of Fitch if they are separated by at...
research
∙
11/01/2017