15 papers
Relative Timing Information and Orthology in Evolutionary Scenarios
David Schaller, Tom Hartmann, Manuel Lafond +3
Evolutionary scenarios describing the evolution of a family of genes within a collection of species comprise the mapping of the vertices of a gene tree to vertices and edges of…
Clustering Systems of Phylogenetic Networks
Marc Hellmuth, David Schaller, Peter F. Stadler
Rooted acyclic graphs appear naturally when the phylogenetic relationship of a set of taxa involves not only speciations but also recombination, horizontal transfer, or hybridi…
Orientation of Fitch Graphs and Detection of Horizontal Gene Transfer in Gene Trees
David Schaller, Marc Hellmuth, Peter F. Stadler
Horizontal gene transfer events partition a gene tree and thus, its leaf set into subsets of genes whose evolutionary history is described by speciation and duplication events…
Quasi-Best Match Graphs
Annachiara Korchmaros, David Schaller, Marc Hellmuth +1
Quasi-best match graphs (qBMGs) are a hereditary class of directed, properly vertex-colored graphs. They arise naturally in mathematical phylogenetics as a generalization of best m…
Combining Orthology and Xenology Data in a Common Phylogenetic Tree
Marc Hellmuth, Mira Michel, Nikolai N. Nøjgaard +2
A rooted tree with vertex labels and set-valued edge labels defines maps and on the pairs of leaves of by setting if the last com…
A Simple Linear-Time Algorithm for the Common Refinement of Rooted Phylogenetic Trees on a Common Leaf Set
David Schaller, Marc Hellmuth, Peter F. Stadler
Background. The supertree problem, i.e., the task of finding a common refinement of a set of rooted trees is an important topic in mathematical phylogenetics. The special case of a…
Compatibility of Partitions with Trees, Hierarchies, and Split Systems
Marc Hellmuth, David Schaller, Peter F. Stadler
The question whether a partition and a hierarchy or a tree-like split system are compatible naturally arises in a wide range of classific…
Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs
David Schaller, Manuela Geiß, Marc Hellmuth +1
Best match graphs (BMGs) are vertex-colored digraphs that naturally arise in mathematical phylogenetics to formalize the notion of evolutionary closest genes w.r.t. an a priori unk…
Heuristic Algorithms for Best Match Graph Editing
David Schaller, Manuela Geiß, Marc Hellmuth +1
Best match graphs (BMGs) are a class of colored digraphs that naturally appear in mathematical phylogenetics and can be approximated with the help of similarity measures between ge…
Least resolved trees for two-colored best match graphs
David Schaller, Manuela Geiß, Marc Hellmuth +1
2-colored best match graphs (2-BMGs) form a subclass of sink-free bi-transitive graphs that appears in phylogenetic combinatorics. There, 2-BMGs describe evolutionarily most closel…
Indirect Identification of Horizontal Gene Transfer
David Schaller, Manuel Lafond, Peter F. Stadler +2
Several implicit methods to infer Horizontal Gene Transfer (HGT) focus on pairs of genes that have diverged only after the divergence of the two species in which the genes reside.…
Best Match Graphs with Binary Trees
David Schaller, Manuela Geiß, Marc Hellmuth +1
Best match graphs (BMG) are a key intermediate in graph-based orthology detection and contain a large amount of information on the gene tree. We provide a near-cubic algorithm to d…
Complexity of modification problems for best match graphs
David Schaller, Peter F. Stadler, Marc Hellmuth
Best match graphs (BMGs) are vertex-colored directed graphs that were introduced to model the relationships of genes (vertices) from different species (colors) given an underlying…
Complete Characterization of Incorrect Orthology Assignments in Best Match Graphs
David Schaller, Manuela Geiß, Peter F. Stadler +1
Genome-scale orthology assignments are usually based on reciprocal best matches. In the absence of horizontal gene transfer (HGT), every pair of orthologs forms a reciprocal best m…
From Best Hits to Best Matches
Peter F. Stadler, Manuela Geiß, David Schaller +5
Many of the commonly used methods for orthology detection start from mutually most similar pairs of genes (reciprocal best hits) as an approximation for evolutionary most closely r…