8 papers
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…