Yunheng Han
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Yunheng Han has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Erin Katherine Molloy
Department of Computer Science, University of Maryland, College Park, MD, USA
6 shared publications - Christina Boucher
University of Florida
3 shared publications - Junyan Dai
Department of Computer Science, University of Maryland, College Park, MD 20742, USA
2 shared publications - Aaron Hong
University of Florida
1 shared publication - Adam R. Rivers
United States Department of Agriculture, Agricultural Research Service
1 shared publication - Alan Kuhnle
University of Florida
1 shared publication
Latest Publications
- 28 August 2026
- Published by Cold Spring Harbor Laboratory in Genome Research
Quartet-based species tree methods enable fast and consistent tree of blobs reconstruction under the network multispecies coalescent
Hybridization between species is an important force in evolution, commonly modeled by the network multispecies coalescent. Reconstructing evolutionary histories under this model is computationally challenging, even for level-1 networks where hybridization events are isolated. Divide-and-conquer is a promising path forward, but current methods with statistical guarantees rely on an estimated tree of blobs (TOB) for the network, which compresses each nontree-like part into a single vertex. TOB reconstruction is itself challenging, with the only available method TINNiK having time complexity O ( n 5 + n 4 k ) for k genes and n species. Here, we present a new framework for scalable TOB reconstruction with statistical guarantees. Our approach operates by (1) seeking a refinement of the TOB and then (2) contracting edges in it. For step (1), we show that any optimal solution to Weighted Quartet Consensus is a TOB refinement almost surely, as the number of genes goes to infinity, motivating the use of methods, such as ASTRAL or TREE-QMC. For step (2), we show that applying the same hypothesis tests as TINNiK to just O ( n ) four-taxon subsets around each edge is sufficient for statistically consistent TOB reconstruction when the underlying network is level-1. Leveraging TREE-QMC for the first step gives our method time complexity O ( n 3 k ) and its name: TOB-QMC. On simulated data, TOB-QMC typically matches or exceeds TINNiK in accuracy while being more scalable. TOB-QMC also enables fast exploration of nontreelike evolution, as demonstrated through reanalysis of three phylogenomic data sets. Lastly, our study clarifies the theoretical utility of quartet-based species tree methods in the context of hybridization, which is critical given the recent result that ASTRAL can be misleading.
- 28 August 2026
- Published by Cold Spring Harbor Laboratory in Genome Research
Quartet-based species tree methods enable fast and consistent tree of blobs reconstruction under the network multispecies coalescent
Hybridization between species is an important force in evolution, commonly modeled by the network multispecies coalescent. Reconstructing evolutionary histories under this model is computationally challenging, even for level-1 networks where hybridization events are isolated. Divide-and-conquer is a promising path forward, but current methods with statistical guarantees rely on an estimated tree of blobs (TOB) for the network, which compresses each nontree-like part into a single vertex. TOB reconstruction is itself challenging, with the only available method TINNiK having time complexity O ( n 5 + n 4 k ) for k genes and n species. Here, we present a new framework for scalable TOB reconstruction with statistical guarantees. Our approach operates by (1) seeking a refinement of the TOB and then (2) contracting edges in it. For step (1), we show that any optimal solution to Weighted Quartet Consensus is a TOB refinement almost surely, as the number of genes goes to infinity, motivating the use of methods, such as ASTRAL or TREE-QMC. For step (2), we show that applying the same hypothesis tests as TINNiK to just O ( n ) four-taxon subsets around each edge is sufficient for statistically consistent TOB reconstruction when the underlying network is level-1. Leveraging TREE-QMC for the first step gives our method time complexity O ( n 3 k ) and its name: TOB-QMC. On simulated data, TOB-QMC typically matches or exceeds TINNiK in accuracy while being more scalable. TOB-QMC also enables fast exploration of nontreelike evolution, as demonstrated through reanalysis of three phylogenomic data sets. Lastly, our study clarifies the theoretical utility of quartet-based species tree methods in the context of hybridization, which is critical given the recent result that ASTRAL can be misleading.
- 30 June 2026
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 42 (7)
Primer Design through Submodular Function Estimation
Motivation: Multiplex PCR-based enrichment is widely used in viral genome sequencing and pathogen surveillance. However, designing large sets of primers that maximize genome coverage while minimizing primer–primer interactions remains a major computational challenge. Existing methods such as SADDLE and Olivar use heuristics to optimize a Badness score for primer dimers but lack theoretical guarantees on solution quality. Results: We introduce PRISM, a new framework that formulates multiplex primer design as a constrained submodular maximization problem. Our method defines an objective that balances genome coverage and dimer risk, and applies a local search algorithm with a constant-factor approximation guarantee. Evaluations on viral genome datasets demonstrate that PRISM consistently achieves lower Badness scores compared to PrimalScheme, Olivar, and primerJinn. These results highlight the scalability and theoretical rigor of submodular optimization in primer design. Availability: PRISM is open-source and available at https://github.com/yhhan19/PRISM-new. The experimental data, scripts, and results used in this paper are archived on Figshare at https://doi.org/10.6084/m9.figshare.32806499. Supplementary information: Supplementary information: Supplementary material, including proofs and figures, is available at Bioinformatics online and on Figshare at https://doi.org/10.6084/m9.figshare.32806499.
- 30 June 2026
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 42 (7)
Primer Design through Submodular Function Estimation
Motivation: Multiplex PCR-based enrichment is widely used in viral genome sequencing and pathogen surveillance. However, designing large sets of primers that maximize genome coverage while minimizing primer–primer interactions remains a major computational challenge. Existing methods such as SADDLE and Olivar use heuristics to optimize a Badness score for primer dimers but lack theoretical guarantees on solution quality. Results: We introduce PRISM, a new framework that formulates multiplex primer design as a constrained submodular maximization problem. Our method defines an objective that balances genome coverage and dimer risk, and applies a local search algorithm with a constant-factor approximation guarantee. Evaluations on viral genome datasets demonstrate that PRISM consistently achieves lower Badness scores compared to PrimalScheme, Olivar, and primerJinn. These results highlight the scalability and theoretical rigor of submodular optimization in primer design. Availability: PRISM is open-source and available at https://github.com/yhhan19/PRISM-new. The experimental data, scripts, and results used in this paper are archived on Figshare at https://doi.org/10.6084/m9.figshare.32806499. Supplementary information: Supplementary information: Supplementary material, including proofs and figures, is available at Bioinformatics online and on Figshare at https://doi.org/10.6084/m9.figshare.32806499.
- Open Access
Genomic Diagnostics for Drug-Resistant Mycobacterium tuberculosis: Computational Prediction of Antimicrobial Resistance
Tuberculosis remains a leading cause of infectious disease mortality, and the continued emergence of drug-resistant Mycobacterium tuberculosis strains threatens the effectiveness of standard treatment regimens. Culture-based antibiotic susceptibility testing remains the clinical reference standard for resistance determination but typically requires six to eight weeks, delaying initiation of optimized therapy for patients with drug-resistant disease. Whole-genome sequencing–based approaches provide a rapid alternative for predicting antimicrobial resistance directly from genomic data and are increasingly being incorporated into diagnostic workflows. This survey reviews computational approaches for genomic resistance prediction in Mycobacterium tuberculosis, focusing on two major classes of methods: catalog-based tools that identify established resistance-conferring variants, and de novo machine learning approaches that infer resistance from genome-wide sequence features. We examine the strengths and limitations of these approaches with respect to interpretability, scalability, computational requirements, and concordance with phenotypic testing. We further discuss emerging directions in quantitative minimum inhibitory concentration prediction, challenges in pyrazinamide susceptibility testing, and the limited availability of resistant isolates for newer and repurposed drugs used in multidrug-resistant tuberculosis and extensively drug-resistant tuberculosis treatment regimens. Continued expansion of paired phenotypic and genomic datasets, standardized minimum inhibitory concentration testing protocols, and rigorous lineage-aware evaluation frameworks will be essential for improving the clinical reliability and global deployment of genomic resistance prediction for tuberculosis diagnostics.
Open AccessGenomic Diagnostics for Drug-Resistant Mycobacterium tuberculosis: Computational Prediction of Antimicrobial Resistance
Tuberculosis remains a leading cause of infectious disease mortality, and the continued emergence of drug-resistant Mycobacterium tuberculosis strains threatens the effectiveness of standard treatment regimens. Culture-based antibiotic susceptibility testing remains the clinical reference standard for resistance determination but typically requires six to eight weeks, delaying initiation of optimized therapy for patients with drug-resistant disease. Whole-genome sequencing–based approaches provide a rapid alternative for predicting antimicrobial resistance directly from genomic data and are increasingly being incorporated into diagnostic workflows. This survey reviews computational approaches for genomic resistance prediction in Mycobacterium tuberculosis, focusing on two major classes of methods: catalog-based tools that identify established resistance-conferring variants, and de novo machine learning approaches that infer resistance from genome-wide sequence features. We examine the strengths and limitations of these approaches with respect to interpretability, scalability, computational requirements, and concordance with phenotypic testing. We further discuss emerging directions in quantitative minimum inhibitory concentration prediction, challenges in pyrazinamide susceptibility testing, and the limited availability of resistant isolates for newer and repurposed drugs used in multidrug-resistant tuberculosis and extensively drug-resistant tuberculosis treatment regimens. Continued expansion of paired phenotypic and genomic datasets, standardized minimum inhibitory concentration testing protocols, and rigorous lineage-aware evaluation frameworks will be essential for improving the clinical reliability and global deployment of genomic resistance prediction for tuberculosis diagnostics.
- Open Access
Scaling Variant-Aware Multiplex Primer Design
Motivation: Robust primer design is essential for reliable multiplex PCR in diverse and evolving pathogen, microbial, and host genomes. Traditional methods optimized for a single reference often fail on emerging variants, leading to reduced efficiency. Variant-aware design seeks primers that remain effective across diverse targets, but this introduces two key challenges: identifying robust candidates and selecting an optimal subset of primers. Although there are methods for the first challenge, namely the Primer Design Region (PDR) optimization problem, existing approaches lack optimality guarantees. Results: We introduce a near-linear algorithm with provable guarantees for efficient PDR optimization. Complementing this, we introduce a reference-free risk model based on Gini impurity that provides a stable, biologically interpretable measure of site-specific variation and yields PDRs that are robust to sequence diversity across datasets without ad hoc smoothing. For the second challenge related to thermodynamic stability, we optimize predicted Δ G and cast subset selection as a k -partite maximum-weight clique problem (NP-hard). We then design an efficient local-search heuristic with linear time updates. Together, these advances yield a principled, scalable framework for variant-aware primer design. Across Foot-and-Mouth Disease virus and Zika virus datasets, Δ-PRO produces more compact and robust PDR sets and multiplex panels with reduced predicted dimerization compared to existing tools, demonstrating the practical gains of principled and scalable variant-aware primer design for high-throughput multiplex PCR assays. Availability: The proposed methods are implemented in a software package. Our implementation and results are publicly available at https://github.com/yhhan19/variant-aware-primer-design . Supplementary information: Supplementary materials are available online.
Open AccessScaling Variant-Aware Multiplex Primer Design
Motivation: Robust primer design is essential for reliable multiplex PCR in diverse and evolving pathogen, microbial, and host genomes. Traditional methods optimized for a single reference often fail on emerging variants, leading to reduced efficiency. Variant-aware design seeks primers that remain effective across diverse targets, but this introduces two key challenges: identifying robust candidates and selecting an optimal subset of primers. Although there are methods for the first challenge, namely the Primer Design Region (PDR) optimization problem, existing approaches lack optimality guarantees. Results: We introduce a near-linear algorithm with provable guarantees for efficient PDR optimization. Complementing this, we introduce a reference-free risk model based on Gini impurity that provides a stable, biologically interpretable measure of site-specific variation and yields PDRs that are robust to sequence diversity across datasets without ad hoc smoothing. For the second challenge related to thermodynamic stability, we optimize predicted Δ G and cast subset selection as a k -partite maximum-weight clique problem (NP-hard). We then design an efficient local-search heuristic with linear time updates. Together, these advances yield a principled, scalable framework for variant-aware primer design. Across Foot-and-Mouth Disease virus and Zika virus datasets, Δ-PRO produces more compact and robust PDR sets and multiplex panels with reduced predicted dimerization compared to existing tools, demonstrating the practical gains of principled and scalable variant-aware primer design for high-throughput multiplex PCR assays. Availability: The proposed methods are implemented in a software package. Our implementation and results are publicly available at https://github.com/yhhan19/variant-aware-primer-design . Supplementary information: Supplementary materials are available online.
- Open Access
Quartet-based species tree methods enable fast and consistent tree of blobs reconstruction under the network multispecies coalescent
Hybridization between species is an important force in evolution, commonly modeled by the network multispecies coalescent. Reconstructing evolutionary histories under this model is computationally challenging, even for level-1 networks where hybridization events are isolated. Divide-and-conquer is a promising path forward, but current methods with statistical guarantees rely on an estimated tree of blobs (TOB) for the network, which compresses the non-tree-like parts into single vertices. TOB reconstruction is itself challenging, with the only available method TINNiK having time complexity O ( n 5 + n 4 k ) for k genes and n species. Here, we present a new framework for scalable TOB reconstruction with statistical guarantees. Our approach operates by (1) seeking a refinement of the TOB and then (2) contracting edges in it. For step (1), we show that any optimal solution to Weighted Quartet Consensus is a TOB refinement almost surely, as the number of genes goes to infinity, motivating the use of methods, such as ASTRAL or TREE-QMC. For step (2), we show that applying the same hypothesis tests as TINNiK to just O ( n ) four-taxon subsets around each edge is sufficient for statistical consistency when the underlying network is level-1. Leveraging TREE-QMC for the first step gives our method time complexity O ( n 3 k ) and its name: TOB-QMC. On simulated data, TOB-QMC typically matches or exceeds TINNiK in accuracy while being more scalable. TOB-QMC also enables fast exploration of non-tree-like evolution, as demonstrated through re-analysis of three phylogenomic data sets. Lastly, our study clarifies the theoretical utility of quartet-based species tree methods in the context of hybridization, which is critical given the recent result that ASTRAL can be misleading.
Open AccessQuartet-based species tree methods enable fast and consistent tree of blobs reconstruction under the network multispecies coalescent
Hybridization between species is an important force in evolution, commonly modeled by the network multispecies coalescent. Reconstructing evolutionary histories under this model is computationally challenging, even for level-1 networks where hybridization events are isolated. Divide-and-conquer is a promising path forward, but current methods with statistical guarantees rely on an estimated tree of blobs (TOB) for the network, which compresses the non-tree-like parts into single vertices. TOB reconstruction is itself challenging, with the only available method TINNiK having time complexity O ( n 5 + n 4 k ) for k genes and n species. Here, we present a new framework for scalable TOB reconstruction with statistical guarantees. Our approach operates by (1) seeking a refinement of the TOB and then (2) contracting edges in it. For step (1), we show that any optimal solution to Weighted Quartet Consensus is a TOB refinement almost surely, as the number of genes goes to infinity, motivating the use of methods, such as ASTRAL or TREE-QMC. For step (2), we show that applying the same hypothesis tests as TINNiK to just O ( n ) four-taxon subsets around each edge is sufficient for statistical consistency when the underlying network is level-1. Leveraging TREE-QMC for the first step gives our method time complexity O ( n 3 k ) and its name: TOB-QMC. On simulated data, TOB-QMC typically matches or exceeds TINNiK in accuracy while being more scalable. TOB-QMC also enables fast exploration of non-tree-like evolution, as demonstrated through re-analysis of three phylogenomic data sets. Lastly, our study clarifies the theoretical utility of quartet-based species tree methods in the context of hybridization, which is critical given the recent result that ASTRAL can be misleading.
- Open Access
Improved robustness to gene tree incompleteness, estimation errors, and systematic homology errors with weighted TREE-QMC
Summary methods are widely used to reconstruct species trees from gene trees while accounting for incomplete lineage sorting; however, it is increasingly recognized that their accuracy can be negatively impacted by incomplete and/or error-ridden gene trees. To address the latter, Zhang and Mirarab (2022) leverage gene tree branch lengths and support values to weight quartets within the popular summary method ASTRAL. Although these quartet weighting schemes improved the robustness of ASTRAL to gene tree estimation error, implementing the weighting schemes presented computational challenges, resulting in the authors abandoning ASTRAL’s original search algorithm (i.e., computing an exact solution within a constrained search space) in favor of search heuristics (i.e., hill climbing with nearest neighbor interchange moves from a starting tree constructed via randomized taxon addition). Here, we show that these quartet weighting schemes can be leveraged within the Quartet Max Cut framework of Snir and Rao (2010), with only a small increase in time complexity compared to the unweighted algorithm, which behaves more like a constant factor in our simulation study. Moreover, our new algorithm, implemented within the TREE-QMC software, was highly competitive with weighted ASTRAL, even outperforming it in terms of species tree accuracy on some challenging model conditions, such as large numbers of taxa. In comparing unweighted and weighted summary methods on two avian data sets, we found that weighting quartets by gene tree branch lengths improves their robustness to systematic homology errors and is as effective as removing the impacted taxa from individual gene trees or removing the impacted gene trees entirely. Lastly, our study revealed that TREE-QMC is highly robust to high rates of missing data and is promising as a supertree method. TREE-QMC is written in C++ and is publicly available on Github: https://github.com/molloy-lab/TREE-QMC
Open AccessImproved robustness to gene tree incompleteness, estimation errors, and systematic homology errors with weighted TREE-QMC
Summary methods are widely used to reconstruct species trees from gene trees while accounting for incomplete lineage sorting; however, it is increasingly recognized that their accuracy can be negatively impacted by incomplete and/or error-ridden gene trees. To address the latter, Zhang and Mirarab (2022) leverage gene tree branch lengths and support values to weight quartets within the popular summary method ASTRAL. Although these quartet weighting schemes improved the robustness of ASTRAL to gene tree estimation error, implementing the weighting schemes presented computational challenges, resulting in the authors abandoning ASTRAL’s original search algorithm (i.e., computing an exact solution within a constrained search space) in favor of search heuristics (i.e., hill climbing with nearest neighbor interchange moves from a starting tree constructed via randomized taxon addition). Here, we show that these quartet weighting schemes can be leveraged within the Quartet Max Cut framework of Snir and Rao (2010), with only a small increase in time complexity compared to the unweighted algorithm, which behaves more like a constant factor in our simulation study. Moreover, our new algorithm, implemented within the TREE-QMC software, was highly competitive with weighted ASTRAL, even outperforming it in terms of species tree accuracy on some challenging model conditions, such as large numbers of taxa. In comparing unweighted and weighted summary methods on two avian data sets, we found that weighting quartets by gene tree branch lengths improves their robustness to systematic homology errors and is as effective as removing the impacted taxa from individual gene trees or removing the impacted gene trees entirely. Lastly, our study revealed that TREE-QMC is highly robust to high rates of missing data and is promising as a supertree method. TREE-QMC is written in C++ and is publicly available on Github: https://github.com/molloy-lab/TREE-QMC
- Open Access
- 17 May 2023
- Published by Cold Spring Harbor Laboratory in Genome Research
Improving quartet graph construction for scalable and accurate species tree estimation from gene trees
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.
- 17 May 2023
- Published by Cold Spring Harbor Laboratory in Genome Research
Open AccessImproving quartet graph construction for scalable and accurate species tree estimation from gene trees
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.
- Open Access
Quartets enable statistically consistent estimation of cell lineage trees under an unbiased error and missingness model
Cancer progression and treatment can be informed by reconstructing its evolutionary history from tumor cells. However, traditional methods assume the input data are error-free and the output tree is fully resolved. These assumptions are challenged in tumor phylogenetics because single-cell sequencing produces sparse, error-ridden data and because tumors evolve clonally. Here, we find that methods based on quartets (four-leaf, unrooted trees) withstand these barriers. We consider a popular tumor phylogenetics model, in which mutations arise on a (highly unresolved) tree and then (unbiased) errors and missing values are introduced. Quartets are implied by mutations present in two cells and absent from two cells. Our main result is that the most probable quartet identifies the unrooted model tree on four cells. This motivates seeking a tree such that the number of quartets shared between it and the input mutations is maximized. We prove an optimal solution is a consistent estimator of the unrooted cell lineage tree; this guarantee includes the case where the model tree is highly unresolved, with error defined as the number of false negative branches. Lastly, we outline how quartet-based methods might be employed when there are copy number aberrations and other challenges specific to tumor phylogenetics.
Open AccessQuartets enable statistically consistent estimation of cell lineage trees under an unbiased error and missingness model
Cancer progression and treatment can be informed by reconstructing its evolutionary history from tumor cells. However, traditional methods assume the input data are error-free and the output tree is fully resolved. These assumptions are challenged in tumor phylogenetics because single-cell sequencing produces sparse, error-ridden data and because tumors evolve clonally. Here, we find that methods based on quartets (four-leaf, unrooted trees) withstand these barriers. We consider a popular tumor phylogenetics model, in which mutations arise on a (highly unresolved) tree and then (unbiased) errors and missing values are introduced. Quartets are implied by mutations present in two cells and absent from two cells. Our main result is that the most probable quartet identifies the unrooted model tree on four cells. This motivates seeking a tree such that the number of quartets shared between it and the input mutations is maximized. We prove an optimal solution is a consistent estimator of the unrooted cell lineage tree; this guarantee includes the case where the model tree is highly unresolved, with error defined as the number of false negative branches. Lastly, we outline how quartet-based methods might be employed when there are copy number aberrations and other challenges specific to tumor phylogenetics.
- Open Access
TREE-QMC: Improving quartet graph construction for scalable and accurate species tree estimation from gene trees
Summary methods are one of the dominant approaches for estimating species trees from genome-scale data. However, they can fail to produce accurate species trees when the input gene trees are highly discordant due to gene tree estimation error as well as biological processes, like incomplete lineage sorting. Here, we introduce a new summary method TREE-QMC that offers improved accuracy and scalability under these challenging scenarios. TREE-QMC builds upon the algorithmic framework of QMC (Snir and Rao 2010) and its weighted version wQMC (Avni et al. 2014). Their approach takes weighted quartets (four-leaf trees) as input and builds a species tree in a divide-and-conquer fashion, at each step constructing a graph and seeking its max cut. We improve upon this methodology in two ways. First, we address scalability by providing an algorithm to construct the graph directly from the input gene trees. By skipping the quartet weighting step, TREE-QMC has a time complexity of O ( n 3 k ) with some assumptions on subproblem sizes, where n is the number of species and k is the number of gene trees. Second, we address accuracy by normalizing the quartet weights to account for “artificial taxa,” which are introduced during the divide phase so that solutions on subproblems can be combined during the conquer phase. Together, these contributions enable TREE-QMC to outperform the leading methods (ASTRAL-III, FASTRAL, wQFM) in an extensive simulation study. We also present the application of these methods to an avian phylogenomics data set.
Open AccessTREE-QMC: Improving quartet graph construction for scalable and accurate species tree estimation from gene trees
Summary methods are one of the dominant approaches for estimating species trees from genome-scale data. However, they can fail to produce accurate species trees when the input gene trees are highly discordant due to gene tree estimation error as well as biological processes, like incomplete lineage sorting. Here, we introduce a new summary method TREE-QMC that offers improved accuracy and scalability under these challenging scenarios. TREE-QMC builds upon the algorithmic framework of QMC (Snir and Rao 2010) and its weighted version wQMC (Avni et al. 2014). Their approach takes weighted quartets (four-leaf trees) as input and builds a species tree in a divide-and-conquer fashion, at each step constructing a graph and seeking its max cut. We improve upon this methodology in two ways. First, we address scalability by providing an algorithm to construct the graph directly from the input gene trees. By skipping the quartet weighting step, TREE-QMC has a time complexity of O ( n 3 k ) with some assumptions on subproblem sizes, where n is the number of species and k is the number of gene trees. Second, we address accuracy by normalizing the quartet weights to account for “artificial taxa,” which are introduced during the divide phase so that solutions on subproblems can be combined during the conquer phase. Together, these contributions enable TREE-QMC to outperform the leading methods (ASTRAL-III, FASTRAL, wQFM) in an extensive simulation study. We also present the application of these methods to an avian phylogenomics data set.