5 papers · 1 filter
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…