Improving quartet graph construction for scalable and accurate species tree estimation from gene trees

Area of Science:

• Phylogenomics
• Computational Biology
• Evolutionary Biology

Background:

• Estimating species trees from genome-scale data is crucial but challenging due to gene tree discordance from estimation errors and incomplete lineage sorting.
• Existing summary methods may falter under high gene tree discordance, impacting phylogenetic accuracy.

Purpose of the Study:

• Introduce TREE-QMC, a new summary method designed for accurate and scalable species tree estimation.
• Address limitations of current methods in handling highly discordant gene trees.
• Improve upon the weighted Quartet Max Cut (wQMC) approach for phylogenetic inference.

Main Methods:

• TREE-QMC utilizes a divide-and-conquer strategy based on weighted Quartet Max Cut.
• Novelty lies in normalizing quartet weights to manage artificial taxa during subproblem combination.
• Introduced an efficient algorithm for direct graph construction from gene trees, achieving a time complexity of O(nk).

Main Results:

• TREE-QMC demonstrates competitive accuracy and scalability compared to leading quartet-based methods.
• The method outperforms existing approaches under specific simulation conditions.
• Empirical runtime analysis shows TREE-QMC's efficiency.

Conclusions:

• TREE-QMC offers a robust solution for species tree estimation in the presence of significant gene tree discordance.
• The method's accuracy and scalability make it suitable for large-scale phylogenomic analyses.
• Demonstrated practical utility through application to an avian phylogenomics dataset.