title: Fast spatial ancestry via flexible allele frequency surfaces.
abstract: BACKGROUND
  Unique modeling and computational challenges arise in locating the geographic origin of individuals based on their genetic backgrounds. Single-nucleotide polymorphisms (SNPs) vary widely in informativeness, allele frequencies change non-linearly with geography and reliable localization requires evidence to be integrated across a multitude of SNPs. These problems become even more acute for individuals of mixed ancestry. It is hardly surprising that matching genetic models to computational constraints has limited the development of methods for estimating geographic origins. We attack these related problems by borrowing ideas from image processing and optimization theory. Our proposed model divides the region of interest into pixels and operates SNP by SNP. We estimate allele frequencies across the landscape by maximizing a product of binomial likelihoods penalized by nearest neighbor interactions. Penalization smooths allele frequency estimates and promotes estimation at pixels with no data. Maximization is accomplished by a minorize-maximize (MM) algorithm. Once allele frequency surfaces are available, one can apply Bayes' rule to compute the posterior probability that each pixel is the pixel of origin of a given person. Placement of admixed individuals on the landscape is more complicated and requires estimation of the fractional contribution of each pixel to a person's genome. This estimation problem also succumbs to a penalized MM algorithm.
  
  
  RESULTS
  We applied the model to the Population Reference Sample (POPRES) data. The model gives better localization for both unmixed and admixed individuals than existing methods despite using just a small fraction of the available SNPs. Computing times are comparable with the best competing software.
  
  
  METHODS
  Software will be freely available as the OriGen package in R.
  
  
  BACKGROUND
  ranolaj@uw.edu or klange@ucla.edu
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Statistics, University of Washington, Seattle, WA 98195, Department of Human Genetics, University of Chicago, Chicago, IL 60637 and Department of Biomathematics, Human Genetics, and Statistics, University of California Los Angeles, Los Angeles, CA 90095, USA.
authors.forename: John Michael
authors.initials: JM
authors.lastname: Rañola
authors.affiliation: Department of Statistics, University of Washington, Seattle, WA 98195, Department of Human Genetics, University of Chicago, Chicago, IL 60637 and Department of Biomathematics, Human Genetics, and Statistics, University of California Los Angeles, Los Angeles, CA 90095, USA.
authors.forename: John
authors.initials: J
authors.lastname: Novembre
authors.affiliation: Department of Statistics, University of Washington, Seattle, WA 98195, Department of Human Genetics, University of Chicago, Chicago, IL 60637 and Department of Biomathematics, Human Genetics, and Statistics, University of California Los Angeles, Los Angeles, CA 90095, USA.
authors.forename: Kenneth
authors.initials: K
authors.lastname: Lange
mesh_terms: D000465:Algorithms; D001499:Bayes Theorem; D005787:Gene Frequency; D015894:Genome, Human / Q000235:genetics; D006801:Humans; D058974:Phylogeography / Q000379:methods*; D020641:Polymorphism, Single Nucleotide / Q000235:genetics; D012984:Software; D013997:Time Factors