A Heuristic for Maximum Greedy Consensus Tree Problem
A phylogenetic tree represents evolutionary relationships among species. The maximum greedy consensus tree (MGCT) problem seeks a consensus tree with the maximum internal nodes from $k$ conflicting phylogenetic trees and is NP-hard for $k≥3$. This paper presents a heuristic solution with $O(k^3n^5)$ complexity, achieving a consensus tree size of 23.4/26 of a binary tree in experiments. Additionally, the heuristic outperforms random selection in certain tree classes by more effectively handling cluster frequency ties.
Jan 1, 2022
