A Heuristic for Maximum Greedy Consensus Tree Problem

A phylogenetic tree is a tree that represents the evolutionary history of a set of species. Given a set of k conflicting phylogenetic trees whose leaves are labeled by n species, a greedy consensus tree is a tree formed by choosing clusters according to their decreasing order of counts. The maximum greedy consensus tree (MGCT) problem asks to find the greedy consensus tree with the maximum number of internal nodes. It is known that the MGCT problem is NP-hard for $k ≥ 3$. In this paper, we have proposed and implemented a heuristic that runs in $O(k^3n^5)$-time. The experimental result using our dataset shows that the heuristic constructs a greedy consensus tree whose size is 23.4/26 of the binary tree. We also identified a class of phylogenetic trees where our algorithm performs better than a non-deterministic approach like random selection which breaks ties of cluster frequencies randomly.