Variational Inference of Population Structure in Large SNP Datasets
Anil Raj, Matthew Stephens, Jonathan K Pritchard

Tools for estimating population structure from genetic data are now used in a wide variety of applications in population genetics. However, inferring population structure in large modern data sets imposes severe computational challenges. Here, we develop efficient algorithms for approximate inference of the model underlying the STRUCTURE program using a variational Bayesian framework. Variational methods pose the problem of computing relevant posterior distributions as an optimization problem, allowing us to build on recent advances in optimization theory to develop fast inference tools. In addition, we propose useful heuristic scores to identify the number of populations represented in a dataset and a new hierarchical prior to detect weak population structure in the data. We test the variational algorithms on simulated data, and illustrate using genotype data from the CEPH-Human Genome Diversity Panel. The variational algorithms are almost two orders of magnitude faster than STRUCTURE and achieve accuracies comparable to those of ADMIXTURE. Furthermore, our results show that the heuristic scores for choosing model complexity provide a reasonable range of values for the number of populations represented in the data, with minimal bias towards detecting structure when it is very weak. Our algorithm, fastSTRUCTURE, is freely available online at http://pritchardlab.stanford.edu/structure.html.

Calibrated birth-death phylogenetic time-tree priors for Bayesian inference
Joseph Heled, Alexei J.Drummond
(Submitted on 19 Nov 2013)

Here we introduce a general class of multiple calibration birth-death tree priors for use in Bayesian phylogenetic inference. All tree priors in this class separate ancestral node heights into a set of “calibrated nodes” and “uncalibrated nodes” such that the marginal distribution of the calibrated nodes is user-specified whereas the density ratio of the birth-death prior is retained for trees with equal values for the calibrated nodes. We describe two formulations, one in which the calibration information informs the prior on ranked tree topologies, through the (conditional) prior, and the other which factorizes the prior on divergence times and ranked topologies, thus allowing uniform, or any arbitrary prior distribution on ranked topologies. While the first of these formulations has some attractive properties the algorithm we present for computing its prior density is computationally intensive. On the other hand, the second formulation is always computationally efficient. We demonstrate the utility of the new class of multiple-calibration tree priors using both small simulations and a real-world analysis and compare the results to existing schemes. The two new calibrated tree priors described in this paper offer greater flexibility and control of prior specification in calibrated time-tree inference and divergence time dating, and will remove the need for indirect approaches to the assessment of the combined effect of calibration densities and tree process priors in Bayesian phylogenetic inference.

An HMM-based Comparative Genomic Framework for Detecting Introgression in Eukaryotes
Kevin J. Liu, Jingxuan Dai, Kathy Truong, Ying Song, Michael H. Kohn, Luay Nakhleh
(Submitted on 30 Oct 2013)

One outcome of interspecific hybridization and subsequent effects of evolutionary forces is introgression, which is the integration of genetic material from one species into the genome of an individual in another species. The evolution of several groups of eukaryotic species has involved hybridization, and cases of adaptation through introgression have been already established. In this work, we report on a new comparative genomic framework for detecting introgression in genomes, called PhyloNet-HMM, which combines phylogenetic networks, that capture reticulate evolutionary relationships among genomes, with hidden Markov models (HMMs), that capture dependencies within genomes. A novel aspect of our work is that it also accounts for incomplete lineage sorting and dependence across loci.
Application of our model to variation data from chromosome 7 in the mouse (Mus musculus domesticus) genome detects a recently reported adaptive introgression event involving the rodent poison resistance gene Vkorc1, in addition to other newly detected introgression regions. Based on our analysis, it is estimated that about 12% of all sites withinchromosome 7 are of introgressive origin (these cover about 18 Mbp of chromosome 7, and over 300 genes). Further, our model detects no introgression in two negative control data sets. Our work provides a powerful framework for systematic analysis of introgression while simultaneously accounting for dependence across sites, point mutations, recombination, and ancestral polymorphism.

Fast Inference of Admixture Coefficients Using Sparse Non-negative Matrix Factorization Algorithms
Eric Frichot, François Mathieu, Théo Trouillon, Guillaume Bouchard, Olivier François
(Submitted on 24 Sep 2013)

Inference of individual admixture coefficients, which is important for population genetic and association studies, is commonly performed using compute-intensive likelihood algorithms. With the availability of large population genomic data sets, fast versions of likelihood algorithms have attracted considerable attention. Reducing the computational burden of estimation algorithms remains, however, a major challenge. Here, we present a fast and efficient method for estimating individual admixture coefficients based on sparse non-negative matrix factorization algorithms. We implemented our method in the computer program sNMF, and applied it to human and plant genomic data sets. The performances of sNMF were then compared to the likelihood algorithm implemented in the computer program ADMIXTURE. Without loss of accuracy, sNMF computed estimates of admixture coefficients within run-times approximately 10 to 30 times faster than those of ADMIXTURE.

Watterson estimators for Next Generation Sequencing: from trios to autopolyploids
Luca Ferretti, Sebástian E. Ramos-Onsins
(Submitted on 17 Sep 2013)

Several variation of the Watterson estimator of variability for Next Generation Sequencing (NGS) data have been proposed in the literature. We present a unified framework for generalized Watterson estimators based on Maximum Composite Likelihood, which encompasses most of the existing estimators. We propose this class of unbiased estimators as generalized Watterson estimators for a large class of NGS data, including pools and trios. We also discuss the relation with the estimators that have been proposed in the literature and show that they admit two equivalent but seemingly different forms, deriving a set of combinatorial identities as a byproduct. Finally, we give a detailed treatment of Watterson estimators for single or multiple autopolyploid individuals.