Constructing the Tree of Life requires statistical estimation methods that have high accuracy on genome-scale data. These estimations are challenging, since nearly all statistical estimation methods are attempts to solve NP-hard optimization problems, and the heuristics that are used may not have good accuracy on large datasets. Equally troubling, many statistical estimation methods assume that the input data are high quality, and have poor accuracy on low quality data that are typical of many genome-scale evolutionary datasets. In this talk, I will present new computational methods we have developed that enable large-scale phylogeny estimation to be highly accurate and computationally efficient. I will also show how we used these techniques to estimate the avian tree of life (Jarvis et al., Science 2014) and the land plant tree of life (Wickett et al., PNAS 2014).