Improving quartet graph construction for scalable and accurate species tree estimation from gene trees
Open Access
- 17 May 2023
- journal article
- research article
- Published by Cold Spring Harbor Laboratory in Genome Research
Abstract
Summary methods are widely used to estimate species trees from genome-scale data. However, they can fail to produce accurate species trees when the input gene trees are highly discordant because of estimation error and biological processes, such as incomplete lineage sorting. Here, we introduce TREE-QMC, a new summary method that offers accuracy and scalability under these challenging scenarios. TREE-QMC builds upon weighted Quartet Max Cut, which takes weighted quartets as input and then constructs a species tree in a divide-and-conquer fashion, at each step forming a graph and seeking its max cut. The wQMC method has been successfully leveraged in the context of species tree estimation by weighting quartets by their frequencies in the gene trees; we improve upon this approach in two ways. First, we address accuracy by normalizing the quartet weights to account for “artificial taxa” introduced during the divide phase so subproblem solutions can be combined during the conquer phase. Second, we address scalability by introducing an algorithm to construct the graph directly from the gene trees; this gives TREE-QMC a time complexity ofO(n3k), wherenis the number of species andkis the number of gene trees, assuming the subproblem decomposition is perfectly balanced. These contributions enable TREE-QMC to be highly competitive in terms of species tree accuracy and empirical runtime with the leading quartet-based methods, even outperforming them on some model conditions explored in our simulation study. We also present the application of these methods to an avian phylogenomics data set.Keywords
All Related Versions
Funding Information
- State of Maryland
This publication has 37 references indexed in Scilit:
- Polynomial-Time Statistical Estimation of Species Trees Under Gene Duplication and LossJournal of Computational Biology, 2021
- On the Weighted Quartet Consensus problemTheoretical Computer Science, 2019
- Multi-allele species reconstruction using ASTRALMolecular Phylogenetics and Evolution, 2019
- Genes with minimal phylogenetic information are problematic for coalescent analyses when gene tree estimation is biasedMolecular Phylogenetics and Evolution, 2015
- Likelihood-based tree reconstruction on a concatenation of aligned sequence data sets can be statistically inconsistentTheoretical Population Biology, 2015
- Phylotranscriptomic analysis of the origin and early diversification of land plantsProceedings of the National Academy of Sciences, 2014
- Resolving conflict in eutherian mammal phylogeny using phylogenomics and the multispecies coalescent modelProceedings of the National Academy of Sciences, 2012
- Quartet MaxCut: A fast algorithm for amalgamating quartet treesMolecular Phylogenetics and Evolution, 2012
- Inconsistency of Phylogenetic Estimates from Concatenated Data under CoalescenceSystematic Biology, 2007
- The Probability of Topological Concordance of Gene Trees and Species TreesTheoretical Population Biology, 2002