TREE-QMC

TREE-QMC improves species tree estimation from genome-scale gene trees by normalizing quartet weights, constructing graphs directly from gene trees, and applying a divide-and-conquer weighted Quartet Max Cut (wQMC) approach to handle discordance such as incomplete lineage sorting.

Key Features:

• Accuracy Enhancement: Normalizes quartet weights to correct inaccuracies introduced by "artificial taxa" during the divide phase, enabling effective combination of subproblem solutions in the conquer phase.
• Scalability Improvement: Constructs graphs directly from gene trees to achieve time complexity O(n·k), where n is the number of species and k is the number of gene trees, under the assumption of perfectly balanced subproblem decomposition.
• Divide-and-Conquer Strategy: Processes weighted quartets in staged subproblems, forming graphs and seeking their max cut at each step as part of the wQMC-based pipeline.

Scientific Applications:

• Phylogenomics: Species tree estimation from discordant gene trees, including scenarios with high incomplete lineage sorting.
• Empirical benchmarking and real datasets: Demonstrated improved runtime and accuracy in simulation studies and applied to an avian phylogenomics dataset.

Methodology:

Normalize quartet weights; construct graphs directly from gene trees; apply a divide-and-conquer scheme that forms graphs for subproblems and seeks their max cut using the weighted Quartet Max Cut (wQMC) framework, with overall time complexity reported as O(n·k) assuming balanced decomposition.