The sample complexity of species tree estimation: How many genes does it take to infer a species tree?

In this talk, I will discuss the problem of inferring an evolutionary tree from DNA sequence data. The main focus will be on the sample complexity of this problem---i.e., the question of how much data is required to achieve high probability of correct inference. After introducing a standard stochastic model of gene and DNA evolution, I will highlight some surprising features of DNA sequence data that complicate inference. Finally, I will present an impossibility result which takes the form of an information-theoretic lower bound on the minimum amount of data needed for accurate inference when genes exhibit variation in mutation rates. No prior knowledge of phylogenetics or information theory is assumed. Based on joint work with Sebastien Roch.