ASTRAL-III: polynomial time species tree reconstruction from partially resolved gene trees

By Maryam Rabiee, Erfan Sayyari, Siavash Mirarab. BMC Bioinformatics, 2018

2,144 citations recorded by the source corpus.

Evolutionary histories can be discordant across the genome, and such discordances need to be considered in reconstructing the species phylogeny. ASTRAL is one of the leading methods for inferring species trees from gene trees while accounting for gene tree discordance. ASTRAL uses dynamic programming to search for the tree that shares the maximum number of quartet topologies with input gene trees, restricting itself to a predefined set of bipartitions. We introduce ASTRAL-III, which substantially improves the running time of ASTRAL-II and guarantees polynomial running time as a function of both the number of species (n) and the number of genes (k). ASTRAL-III limits the bipartition constraint set (X) to grow at most linearly with n and k. Moreover, it handles polytomies more efficiently than ASTRAL-II, exploits similarities between gene trees better, and uses several techniques to avoid searching parts of the search space that are mathematically guaranteed not to include the optimal tree. The asymptotic running time of ASTRAL-III in the presence of polytomies is O(nk)1.726D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O\left ((nk)^{1.726} D \right)$\end{document} where D=O(nk) is the sum of degrees of all unique nodes in input trees. The running time improvements enable us to test whether contracting low support branches in gene trees improves the accuracy by reducing noise. In extensive simulations, we show that removing branches with very low support (e.g., below 10%) improves accuracy while overly aggressive filtering is harmful. We observe on a biological avian phylogenomic dataset of 14K genes that contracting low support branches greatly improve results. ASTRAL-III is a faster version of the ASTRAL method for phylogenetic reconstruction and can scale up to 10,000 species. With ASTRAL-III, low support branches can be removed, resulting in improved accuracy.

Subfields: Genetics, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/a20f41c64e1defb55261dae1d67dba012bf446ea

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Genetics

1. Guangchuang Yu
2. Shuangbing Xu
3. Katharina Steinke
4. Xiuqun Liu
5. Zhi‐Yao Ma
6. Jun Wen
7. Yi Guan
8. Bin‐Bin Liu

In Molecular Biology

1. Guangchuang Yu
2. Zehan Dai
3. Yi Guan
4. Shuangbing Xu
5. Tingze Feng
6. Pingfan Guo
7. Lang Zhou
8. T. T. Lam

Citations in the corpus

• Capturing single-copy nuclear genes, organellar genomes, and nuclear ribosomal DNA from deep genome skimming data for plant phylogenetics: A case study in Vitaceae (2021, methodology): “Each of the gene trees was rooted and low support branches (≤ 10) were contracted by Newick Utilities (Junier & Zdobnov, 2010), since collapsing gene tree nodes with BS support less than a certain value will help to improve accuracy (Zhang et al., 2018).”
• treeio: an R package for phylogenetic tree input and output with richly annotated and associated data. (2019, methodology): “Currently, treeio can read the following file formats: Newick, NEXUS (Maddison et al. 1997), New Hampshire eXtended format (NHX), jplace (Matsen et al. 2012), and phylip as well as the data outputs from the following analysis programs: ASTRAL (Zhang et al. 2018), BEAST (Bouckaert et al. 2014), EPA (”
• Progressive Cactus is a multiple-genome aligner for the thousand-genome era (2020, neutral): “'!)("$') $/0'()* +!,1 " )%#&2(33' 0 4')( 1 ! ' 5*6%!* !) %3" 7 )* " $(5%/%8%)0 9)* 6 :)*')6 "(/8%!*;<*%!9 3" 7%$ !!) (5)( 9 5 #!%!) #50'#$) '#!"' #50 %# " )%#&;= 9( )* %#9 3')% # #4')( 1 ! ' 5*" 8%5% !>! ?()* !@1 9 !'#$)* A$%) %'8B 8%50 * 5:8%!); 2)')%!)%5! = '8!)')%!)%5'8'#'80! !>5 #9% 3)*'))* 9 8 ”
• AutoMLST: an automated web server for generating multi-locus species trees highlighting natural product potential (2019, methodology): “Placement mode leverages pre-built DNA alignments of all selected single copy genes and their subsequent trees which are combined using ASTRAL-III (38) to infer species trees.”