EUVIMEDEUVIMED entdecken
Open Access

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

Yunheng Han iD, Erin K Molloy iD

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

AlgorithmsGenomePhylogenyComputer SimulationModels, Genetic

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}
}
Kostenlos starten →