Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs

D. Schaller, M. Geiß, M. Hellmuth, P. Stadler. Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs. Algorithms, volume 14, number 4, pages 110, DOI 10.3390/a14040110, 3, 2021.

Autoren
  • David Schaller
  • Manuela Geiß
  • Marc Hellmuth
  • Peter F. Stadler
TypArtikel
JournalAlgorithms
Nummer4
Band14
DOI10.3390/a14040110
Monat3
Jahr2021
Seiten110
Abstract

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 unknown phylogenetic tree. BMGs are explained by unique least resolved trees. We prove that the property of a rooted, leaf-colored tree to be least resolved for some BMG is preserved by the contraction of inner edges. For the special case of two-colored BMGs, this leads to a characterization of the least resolved trees (LRTs) of binary-explainable trees and a simple, polynomial-time algorithm for the minimum cardinality completion of the arc set of a BMG to reach a BMG that can be explained by a binary tree.