Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00564
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
|
Journal Supporters
|