ASTRAL-III: polynomial time species tree reconstruction from partially resolved gene trees
Open accessAbstract
BACKGROUND: 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. RESULTS: 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 [Formula: see text] 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. CONCLUSIONS: 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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Comparative genomics analyses (species-tree inference, comparative annotation, selection detection) require genome alignments.
“Comparative genomics analyses, including species-tree inference7,8, comparative annotation9,10, and selection detection11,12, require genome alignments.”
From Progressive Cactus is a multiple-genome aligner for the thousand-genome era (2020) · cites this paper as [8]
The Background (page unavailable) describes species-tree inference from gene trees drawn from different parts of the genome, and the Results discuss gene alignments. But the Methods define ASTRAL’s input as gene trees, not genome alignments, so the paper does not establish the claimed requirement for genome alignments. This citation is attached to species-tree inference, not comparative annotation or selection detection. (LLM, conf=0.82)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738 · see citing works
Genome-scale approaches to resolving incongruence in molecular phylogenies.
Rokas, A., Williams, B. L., King, N., & Carroll, S. B. (2003) · Nature · doi:10.1038/nature02053 · Cited by 1,512 · see citing works
Phylotranscriptomic analysis of the origin and early diversification of land plants
Wickett, N. J., Mirarab, S., Nguyen, N., Warnow, T., Carpenter, E., Matasci, N., Ayyampalayam, S., Barker, M. S., Burleigh, J. G., Gitzendanner, M. A., et al. (2014) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1323926111 · Cited by 1,252 · see citing works
Self-citationContentious relationships in phylogenomic studies can be driven by a handful of genes
Shen, X.-X., Hittinger, C. T., & Rokas, A. (2017) · Nature Ecology & Evolution · doi:10.1038/s41559-017-0126 · Cited by 520 · see citing works
Statistical binning enables an accurate coalescent-based estimation of the avian tree
Mirarab, S., Bayzid, M. S., Boussau, B., & Warnow, T. (2014) · Science · doi:10.1126/science.1250463 · Cited by 257 · see citing works
Self-citation
Flagged first, then by citations
Research works printed but not linked: 40
- [1]Maddison WP Gene trees in species trees Syst Biol 1997 46 3 523 36 10.1093/sysbio/46.3.523 · DOI
- [2]Degnan JH Rosenberg NA Gene tree discordance, phylogenetic inference and the multispecies coalescent Trends Ecol Evol 2009 24 6 332 40 10.1016/j.tree.2009.01.009 19307040 · DOI
- [3]Song S Liu L Edwards SV Wu S Resolving conflict in eutherian mammal phylogeny using phylogenomics and the multispecies coalescent model Proc Natl Acad Sci 2012 109 37 14942 7 10.1073/pnas.1211733109 22930817 PMC3443116 · DOI
- [5]Jarvis ED Mirarab S Aberer AJ Li B Houde P Li C Ho SYW Faircloth BC Nabholz B Howard JT Suh A Weber CC da Fonseca RR Li J Zhang F Li H Zhou L Narula N Liu L Ganapathy G Boussau B Bayzid MS Zavidovych V Subramanian S Gabaldón T Capella-Gutiérrez S Huerta-Cepas J Rekepalli B Munch K Schierup MH Lindow B Warren WC Ray D Green RE Bruford MW Zhan X Dixon A Li S Li N Huang Y Derryberry EP Bertelsen MF Sheldon FH Brumfield RT Mello CV Lovell PV Wirthlin M Schneider MPC Prosdocimi F Samaniego JA Velazquez AMV Alfaro-Núñez A Campos PF Petersen B Sicheritz-Ponten T Pas A Bailey T Scofield P Bunce M Lambert DM Zhou Q Perelman P Driskell AC Shapiro B Xiong Z Zeng Y Liu S Li Z Liu B Wu K Xiao J Yinqi X Zheng Q Zhang Y Yang H Wang J Smeds L Rheindt FE Braun MJ Fjeldså J Orlando L Barker FK Jønsson KA Johnson W Koepfli K-P O’Brien S Haussler D Ryder OA Rahbek C Willerslev E Graves GR Glenn TC McCormack JE Burt DW Ellegren H Alström P Edwards SV Stamatakis A Mindell DP Cracraft J Braun EL Warnow T Jun W Gilbert MTP Zhang G Whole-genome analyses resolve early branches in the tree of life of modern birds Science 2014 346 6215 1320 31 10.1126/science.1253451 25504713 PMC4405904 · DOI · Paper page
- [6]Laumer CE, Hejnol A, Giribet G. Nuclear genomic signals of the ’microturbellarian’ roots of platyhelminth evolutionary innovation. eLife. 2015;4. https://doi.org/10.7554/eLife.05503. PMC4398949 25764302 · DOI
- [7]Tarver JE dos Reis M Mirarab S Moran RJ Parker S O’Reilly JE King BL O’Connell MJ Asher RJ Warnow T Peterson KJ Donoghue PCJ Pisani D The Interrelationships of Placental Mammals and the Limits of Phylogenetic Inference Genome Biol Evol 2016 8 2 330 44 10.1093/gbe/evv261 26733575 PMC4779606 · DOI
- [9]Springer MS Gatesy J The gene tree delusion Mol Phylogenet Evol 2016 94 Part A 1 33 10.1016/j.ympev.2015.07.018 26238460 · DOI
- [10]Meiklejohn KA Faircloth BC Glenn TC Kimball RT Braun EL Analysis of a Rapid Evolutionary Radiation Using Ultraconserved Elements: Evidence for a Bias in Some Multispecies Coalescent Methods Syst Biol 2016 65 4 612 27 10.1093/sysbio/syw014 26865273 · DOI
- [11]Edwards SV Xi Z Janke A Faircloth BC McCormack JE Glenn TC Zhong B Wu S Lemmon EM Lemmon AR Leaché AD Liu L Davis CC Implementing and testing the multispecies coalescent model: A valuable paradigm for phylogenomics Mol Phylogenet Evol 2016 94 447 62 10.1016/j.ympev.2015.10.027 26518740 · DOI
- [13]Heled J Drummond AJ Bayesian inference of species trees from multilocus data Mol Biol Evol 2010 27 3 570 580 10.1093/molbev/msp274 19906793 PMC2822290 · DOI · Paper page
- [14]Edwards SV Is a new and general theory of molecular systematics emerging? Evolution 2009 63 1 1 19 10.1111/j.1558-5646.2008.00549.x 19146594 · DOI · Paper page
- [15]Pamilo P Nei M Relationships between gene trees and species trees Mol Biol Evol 1988 5 5 568 83 3193878
- [16]Rannala B Yang Z Bayes estimation of species divergence times and ancestral population sizes using DNA sequences from multiple loci Genetics 2003 164 4 1645 56 12930768 PMC1462670
- [17]Liu L Yu L Edwards SV A maximum pseudo-likelihood approach for estimating species trees under the coalescent model BMC Evol Bioly 2010 10 1 302 10.1186/1471-2148-10-302 PMC2976751 20937096 · DOI · Paper page
- [18]Liu L Yu L Estimating species trees from unrooted gene trees Syst Biol 2011 60 661 7 10.1093/sysbio/syr027 21447481 · DOI
- [19]Vachaspati P Warnow T ASTRID: Accurate Species TRees from Internode Distances BMC Genomics 2015 16 Suppl 10 3 10.1186/1471-2164-16-S10-S3 26449326 PMC4602181 · DOI
- [20]Sayyari E Mirarab S Anchoring quartet-based phylogenetic distances and applications to species tree reconstruction BMC Genomics 2016 17 S10 101 13 10.1186/s12864-016-3098-z 28185574 PMC5123309 · DOI
- [21]Mirarab S Reaz R Bayzid MS Zimmermann T Swenson MS Warnow T ASTRAL: genome-scale coalescent-based species tree estimation Bioinformatics 2014 30 17 541 8 10.1093/bioinformatics/btu462 PMC4147915 25161245 · DOI
- [22]Mirarab S Warnow T ASTRAL-II: coalescent-based species tree estimation with many hundreds of taxa and thousands of genes Bioinformatics 2015 31 12 44 52 10.1093/bioinformatics/btv234 PMC4765870 26072508 · DOI
- [23]Liu L Yu L Pearl DK Edwards SV Estimating species phylogenies using coalescence times among sequences Syst Biol 2009 58 5 468 77 10.1093/sysbio/syp031 20525601 · DOI
- [24]Mossel E Roch S Incomplete lineage sorting: consistent phylogeny estimation from multiple loci IEEE/ACM Trans Comput Biol Bioinformatics (TCBB) 2010 7 1 166 71 10.1109/TCBB.2008.66 20150678 · DOI
- [25]Roch S Warnow T On the robustness to gene tree estimation error (or lack thereof) of coalescent-based species tree methods Syst Biol 2015 64 4 663 76 10.1093/sysbio/syv016 25813358 · DOI
- [26]Lafond M, Scornavacca C. On the Weighted Quartet Consensus problem. arXiv 610.00505. 2016.
- [27]Allman ES Degnan JH Rhodes JA Determining species tree topologies from clade probabilities under the coalescent J Theor Biol 2011 289 1 96 106 10.1016/j.jtbi.2011.08.006 21867714 · DOI
- [29]Shekhar S Roch S Mirarab S Species tree estimation using ASTRAL: how many genes are enough? IEEE/ACM Trans Comput Biol Bioinform 2017 99 1 1 10.1109/TCBB.2017.2757930 28976320 · DOI
- [30]Davidson R Vachaspati P Mirarab S Warnow T Phylogenomic species tree estimation in the presence of incomplete lineage sorting and horizontal gene transfer BMC Genomics 2015 16 Suppl 10 1 10.1186/1471-2164-16-S10-S1 26450506 PMC4603753 · DOI
- [31]Sayyari E Mirarab S Fast Coalescent-Based Computation of Local Branch Support from Quartet Frequencies Mol Biol Evol 2016 33 7 1654 68 10.1093/molbev/msw079 27189547 PMC4915361 · DOI
- [32]Price MN Dehal PS Arkin AP FastTree-2 – Approximately Maximum-Likelihood Trees for Large Alignments PLoS ONE 2010 5 3 9490 10.1371/journal.pone.0009490 PMC2835736 20224823 · DOI · Paper page
- [34]Bayzid M. S Mirarab S Boussau B Warnow T Weighted statistical binning: enabling statistically consistent genome-scale phylogenetic analyses PLoS ONE 2015 10 6 0129183 10.1371/journal.pone.0129183 PMC4472720 26086579 · DOI
- [35]Mirarab S Bayzid MS Warnow T Evaluating Summary Methods for Multilocus Species Tree Estimation in the Presence of Incomplete Lineage Sorting Syst Biol 2016 65 3 366 80 10.1093/sysbio/syu063 25164915 · DOI
- [36]Patel S Error in phylogenetic estimation for bushes in the tree of life J Phylogenet Evol Biol 2013 01 02 110 10.4172/2329-9002.1000110 · DOI
- [37]Gatesy J Springer MS Phylogenetic analysis at deep timescales: unreliable gene trees, bypassed hidden support, and the coalescence/concatalescence conundrum Mol Phylogenet Evol 2014 80 231 66 10.1016/j.ympev.2014.08.013 25152276 · DOI
- [38]Yu Y Warnow T Nakhleh L Algorithms for MDC-based multi-locus phylogeny inference: beyond rooted binary gene trees on single alleles J Comput Biol 2011 18 11 1543 59 10.1089/cmb.2011.0174 22035329 PMC3216099 · DOI
- [40]Zhang C Sayyari E Mirarab S Meidanis J Nakhleh L ASTRAL-III: Increased Scalability and Impacts of Contracting Low Support Branches Lecture Notes in Computer Science. vol. 10562 LNBI 2017 Cham Springer
- [41]Stamatakis A RAxML version 8: A tool for phylogenetic analysis and post-analysis of large phylogenies Bioinformatics 2014 30 9 1312 3 10.1093/bioinformatics/btu033 24451623 PMC3998144 · DOI · Paper page
- [42]Mallo D De Oliveira Martins L Posada D SimPhy: Phylogenomic Simulation of Gene, Locus, and Species Trees Syst Biol 2016 65 2 334 44 10.1093/sysbio/syv082 26526427 PMC4748750 · DOI
- [43]Fletcher W Yang Z INDELible: A flexible simulator of biological sequence evolution Mol Biol Evol 2009 26 8 1879 88 10.1093/molbev/msp098 19423664 PMC2712615 · DOI
- [45]Junier T Zdobnov EM The Newick utilities: high-throughput phylogenetic tree processing in the UNIX shell Bioinformatics 2010 26 13 1669 70 10.1093/bioinformatics/btq243 20472542 PMC2887050 · DOI
- [46]Robinson D Foulds L Comparison of phylogenetic trees Math Biosci 1981 53 1-2 131 47 10.1016/0025-5564(81)90043-2 · DOI
- [47]Kozlov AM Aberer AJ Stamatakis A ExaML version 3: a tool for phylogenomic analyses on supercomputers Bioinformatics 2015 31 15 2577 9 10.1093/bioinformatics/btv184 25819675 PMC4514929 · DOI
Cited by
Sorted by citations
Progressive Cactus is a multiple-genome aligner for the thousand-genome era
Armstrong, J., Hickey, G., Diekhans, M., Fiddes, I. T., Novak, A. M., Deran, A., Fang, Q., Xie, D., Feng, S., Stiller, J., et al. (2020) · Nature · doi:10.1038/s41586-020-2871-y · Cited by 586 · see citing works
“'!)("$') $/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 6%#&%) 3!' " ! #)%#…”
Large-scale ruminant genome sequencing provides insights into their evolution and distinct traits
Chen, L., Qiu, Q., Jiang, Y., Wang, K., Lin, Z., Li, Z., Bibi, F., Yang, Y., Wang, J., Nie, W., et al. (2019) · Science · doi:10.1126/science.aav6202 · Cited by 441 · see citing works
Self-citationStrassert, J. F. H., Irisarri, I., Williams, T. A., & Burki, F. (2021) · Nature Communications · doi:10.1038/s41467-021-22044-z · Cited by 298 · see citing works
Harris, B. J., Clark, J. W., Schrempf, D., Szöllősi, G. J., Donoghue, P. C. J., Hetherington, A. M., & Williams, T. A. (2022) · Nature Ecology & Evolution · doi:10.1038/s41559-022-01885-x · Cited by 187 · see citing works
Non-photosynthetic predators are sister to red algae
Gawryluk, R. M. R., Tikhonenkov, D. V., Hehenberger, E., Husnik, F., Mylnikov, A. P., & Keeling, P. J. (2019) · Nature · doi:10.1038/s41586-019-1398-6 · Cited by 148 · see citing works
Genomic factors shape carbon and nitrogen metabolic niche breadth across Saccharomycotina yeasts
Opulente, D. A., LaBella, A. L., Harrison, M.-C., Wolters, J. F., Liu, C., Li, Y., Kominek, J., Steenwyk, J. L., Stoneman, H. R., VanDenAvond, J., et al. (2024) · Science · doi:10.1126/science.adj4503 · Cited by 121 · see citing works
Adaptive evolution of the enigmatic Takakia now facing climate change in Tibet
Hu, R., Li, X., Hu, Y., Zhang, R., Lv, Q., Zhang, M., Sheng, X., Zhao, F., Chen, Z., Ding, Y., et al. (2023) · Cell · doi:10.1016/j.cell.2023.07.003 · Cited by 55 · see citing works
- Authors
- Zhang, C., Rabiee, M., Sayyari, E., & Mirarab, S.
- Affiliations
- University of California San Diego (US)
- Corresponding author
- Mirarab, Siavash
- Venue
- BMC Bioinformatics
- Published
- 2018-05
- Volume
- 19
- Issue
- S6
- Pages
- 153-153
- ISSN
- 1471-2105 (ISSN-L)
- PMC
- PMC5998893
- OpenAlex
- W2801361050
- Cited by
- 2,471
- References
- 5
- Citations by year
- 2026: 352 · 2025: 408 · 2024: 408 · 2023: 329 · 2022: 327 · 2021: 309 · 2020: 218 · 2019: 101 · 2018: 15 · 2014: 1 · 2013: 1
- FWCI
- 56.94
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- Locations
- BMC Bioinformatics (publishedVersion, cc-by)
- Europe PMC (PubMed Central) (publishedVersion, other-oa)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
- Funders
- National Science Foundation (1565862, 1053575)
- San Diego Supercomputer Center
- Topics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
- Physical Sciences › Earth and Planetary Sciences › Paleontology › Evolution and Paleontology Studies
- Life Sciences › Agricultural and Biological Sciences › Ecology, Evolution, Behavior and Systematics › Plant Diversity and Evolution
- Keywords
- species tree reconstruction, gene tree discordance, polynomial-time algorithms, polytomies
- MeSH terms
- Algorithms, Animals, Birds, Computer Simulation, Models, Genetic, Phylogeny, Species Specificity, Time Factors, Databases, Genetic
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
