Showing cs.DSShow all
3 papers · 1 filter
cs.DS2021
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…
cs.DS2021
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…
cs.DS2020
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…