Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
Least resolved trees for two-colored best match graphs
Vol. 25, no. 1, pp. 397-416, 2021. Regular paper.
Abstract In phylogenetic combinatorics, 2-colored best match graphs (2-BMGs) form a subclass of sink-free bi-transitive digraphs that describe the most closely related genes between a pair of species in an evolutionary scenario. They are explained by a unique least resolved tree (LRT). In this paper, the concept of support vertices is introduced and used to derive an $O(|V|+|E|\log^2|V|)$-time algorithm that recognizes a 2-BMG and constructs its LRT. The approach can be extended to allow the recognition of binary-explainable 2-BMGs with the same complexity. An empirical comparison emphasizes the efficiency of the new algorithm.
This work is licensed under the terms of the CC-BY license.
Submitted: January 2021.
Reviewed: June 2021.
Revised: June 2021.
Accepted: July 2021.
Final: July 2021.
Published: September 2021.
Communicated by Fabio Vandin