Improving quartet graph construction for scalable and accurate species tree estimation from gene trees
Genome Research · 17.05.2023
DOI: 10.1101/gr.277629.122 ↗Kurz gefasst
Fachartikel in der Zeitschrift Genome Research, online erschienen am 17.05.2023. Verfasst von Yunheng Han und 1 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Science, University of Maryland, College Park, Maryland 20742, USA. Hauptthemen laut MEDLINE: Algorithms, Genome. Die Arbeit wurde bisher 16-mal zitiert (Crossref). Der Volltext ist frei in PubMed Central verfügbar. Gefördert von: State of Maryland.
Abstract (Originalsprache)
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 of O ( n 3 k ), where n is the number of species and k is 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.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- Department of Computer Science, University of Maryland, College Park, Maryland 20742, USA.
- University of Maryland Institute for Advanced Computer Studies, College Park, Maryland 20742, USA.
- Department of Computer Science, University of Maryland, College Park, Maryland 20742, USA; ekmolloy@umd.edu.
ORCID-Profile: Yunheng Han, Erin K Molloy
Förderung
- State of Maryland
Zitieren
APA
Han, Y., & Molloy, E. K. (2023). Improving quartet graph construction for scalable and accurate species tree estimation from gene trees. Genome Research. https://doi.org/10.1101/gr.277629.122
Vancouver
Han Y, Molloy EK. Improving quartet graph construction for scalable and accurate species tree estimation from gene trees. Genome Research. 2023. doi:10.1101/gr.277629.122
BibTeX
@article{Han2023,
author = {Han, Yunheng and Molloy, Erin K},
title = {Improving quartet graph construction for scalable and accurate species tree estimation from gene trees},
journal = {Genome Research},
year = {2023},
doi = {10.1101/gr.277629.122}
}
EUVIMED