Title: Species tree estimation using ASTRAL: how many genes are enough?,
Abstract: Species tree reconstruction from genomic data is increasingly performed using
methods that account for sources of gene tree discordance such as incomplete
lineage sorting. One popular method for reconstructing species trees from
unrooted gene tree topologies is ASTRAL. In this paper, we derive theoretical
sample complexity results for the number of genes required by ASTRAL to
guarantee reconstruction of the correct species tree with high probability. We
also validate those theoretical bounds in a simulation study. Our results
indicate that ASTRAL requires $\mathcal{O}(f^{-2} \log n)$ gene trees to
reconstruct the species tree correctly with high probability where n is the
number of species and f is the length of the shortest branch in the species
tree. Our simulations, which are the first to test ASTRAL explicitly under the
anomaly zone, show trends consistent with the theoretical bounds and also
provide some practical insights on the conditions where ASTRAL works well.