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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:84898 |
| Date | 24 April 2023 |
| Creators | Schaller, David, Geiß, Manuela, Hellmuth, Marc, Stadler, Peter F. |
| Publisher | MDPI |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:article, info:eu-repo/semantics/article, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 1999-4893, 110 |
Page generated in 0.0021 seconds