In:
Algorithms, MDPI AG, Vol. 14, No. 4 ( 2021-03-29), p. 110-
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.
Type of Medium:
Online Resource
ISSN:
1999-4893
Language:
English
Publisher:
MDPI AG
Publication Date:
2021
detail.hit.zdb_id:
2455149-1