{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:26:39Z","timestamp":1773271599921,"version":"3.50.1"},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"20","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,10,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: 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\u2013maximize (MM) algorithm. Once allele frequency surfaces are available, one can apply Bayes\u2019 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\u2019s genome. This estimation problem also succumbs to a penalized MM algorithm.<\/jats:p><jats:p>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.<\/jats:p><jats:p>Availability and implementation: Software will be freely available as the OriGen package in R.<\/jats:p><jats:p>Contact: \u00a0ranolaj@uw.edu or klange@ucla.edu<\/jats:p><jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu418","type":"journal-article","created":{"date-parts":[[2014,7,11]],"date-time":"2014-07-11T01:11:54Z","timestamp":1405041114000},"page":"2915-2922","source":"Crossref","is-referenced-by-count":20,"title":["Fast spatial ancestry via flexible allele frequency surfaces"],"prefix":"10.1093","volume":"30","author":[{"given":"John Michael","family":"Ra\u00f1ola","sequence":"first","affiliation":[{"name":"1 Department of Statistics, University of Washington, Seattle, WA 98195, 2 Department of Human Genetics, University of Chicago, Chicago, IL 60637 and 3 Department of Biomathematics, Human Genetics, and Statistics, University of California Los Angeles, Los Angeles, CA 90095, USA"}]},{"given":"John","family":"Novembre","sequence":"additional","affiliation":[{"name":"1 Department of Statistics, University of Washington, Seattle, WA 98195, 2 Department of Human Genetics, University of Chicago, Chicago, IL 60637 and 3 Department of Biomathematics, Human Genetics, and Statistics, University of California Los Angeles, Los Angeles, CA 90095, USA"}]},{"given":"Kenneth","family":"Lange","sequence":"additional","affiliation":[{"name":"1 Department of Statistics, University of Washington, Seattle, WA 98195, 2 Department of Human Genetics, University of Chicago, Chicago, IL 60637 and 3 Department of Biomathematics, Human Genetics, and Statistics, University of California Los Angeles, Los Angeles, CA 90095, USA"}]}],"member":"286","published-online":{"date-parts":[[2014,7,9]]},"reference":[{"key":"2023012711561781500_btu418-B1","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1186\/1471-2105-12-246","article-title":"Enhancements to the admixture algorithm for individual ancestry estimation","volume":"12","author":"Alexander","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023012711561781500_btu418-B2","doi-asserted-by":"crossref","first-page":"1655","DOI":"10.1101\/gr.094052.109","article-title":"Fast model-based estimation of ancestry in unrelated individuals","volume":"19","author":"Alexander","year":"2009","journal-title":"Genome Res."},{"key":"2023012711561781500_btu418-B3","doi-asserted-by":"crossref","first-page":"1596","DOI":"10.1093\/bioinformatics\/btn236","article-title":"Penalized estimation of haplotype frequencies","volume":"24","author":"Ayers","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012711561781500_btu418-B4","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898717877","volume-title":"Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods","author":"Chan","year":"2005"},{"key":"2023012711561781500_btu418-B5","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1111\/j.1469-1809.1937.tb02153.x","article-title":"The wave of advance of advantageous genes","volume":"7","author":"Fisher","year":"1937","journal-title":"Ann. Eugen."},{"key":"2023012711561781500_btu418-B6","volume-title":"The Genetical Theory of Natural Selection","author":"Fisher","year":"2000","edition":"1st edn"},{"key":"2023012711561781500_btu418-B7","doi-asserted-by":"crossref","first-page":"4734","DOI":"10.1111\/j.1365-294X.2009.04410.x","article-title":"Statistical methods in spatial genetics","volume":"18","author":"Guillot","year":"2009","journal-title":"Mol. Ecol."},{"key":"2023012711561781500_btu418-B8","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1198\/0003130042836","article-title":"A tutorial on mm algorithms","volume":"58","author":"Hunter","year":"2004","journal-title":"Am. Stat."},{"key":"2023012711561781500_btu418-B9","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1093\/genetics\/49.4.561","article-title":"The stepping stone model of population structure and the decrease of genetic correlation with distance","volume":"49","author":"Kimura","year":"1964","journal-title":"Genetics"},{"key":"2023012711561781500_btu418-B10","first-page":"1","article-title":"A study of the equation of diffusion with increase in the quantity of matter, and its application to a biological problem","volume":"1","author":"Kolmogorov","year":"1937","journal-title":"Byul. Moskovskogo Gos. Univ."},{"key":"2023012711561781500_btu418-B11","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1109\/42.61759","article-title":"Convergence of EM image reconstruction algorithms with Gibbs smoothing","volume":"9","author":"Lange","year":"1990","journal-title":"IEEE Trans. Med. Imaging"},{"key":"2023012711561781500_btu418-B12","volume-title":"Numerical Analysis for Statisticians. Statistics and Computing","author":"Lange","year":"2012"},{"key":"2023012711561781500_btu418-B13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/10618600.2000.10474858","article-title":"Optimization transfer using surrogate objective functions","volume":"9","author":"Lange","year":"2000","journal-title":"J. Comput. Graph. Stat."},{"key":"2023012711561781500_btu418-B14","doi-asserted-by":"crossref","first-page":"1241","DOI":"10.1016\/j.cub.2008.07.049","article-title":"Correlation between genetic and geographic structure in Europe","volume":"18","author":"Lao","year":"2008","journal-title":"Cur. Biol."},{"key":"2023012711561781500_btu418-B15","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/j.ajhg.2008.08.005","article-title":"The Population Reference Sample, POPRES: a resource for population, disease, and pharmacological genetics research","volume":"83","author":"Nelson","year":"2008","journal-title":"Am. J. Hum. Genet."},{"key":"2023012711561781500_btu418-B16","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1038\/nature07331","article-title":"Genes mirror geography within Europe","volume":"456","author":"Novembre","year":"2008","journal-title":"Nature"},{"key":"2023012711561781500_btu418-B17","doi-asserted-by":"crossref","first-page":"1402","DOI":"10.1086\/380416","article-title":"Informativeness of genetic markers for inference of ancestry","volume":"73","author":"Rosenberg","year":"2003","journal-title":"Am. J. Hum. Genet."},{"key":"2023012711561781500_btu418-B18","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1111\/j.1095-8312.1978.tb00014.x","article-title":"Spatial autocorrelation in biology: 2. Some biological implications and 4 applications of evolutionary and ecological interest","volume":"10","author":"Sokal","year":"1978","journal-title":"Biol. J. Linn. Soc."},{"key":"2023012711561781500_btu418-B19","doi-asserted-by":"crossref","first-page":"234","DOI":"10.2307\/143141","article-title":"A computer movie simulating urban growth in the Detroit region","volume":"46","author":"Tobler","year":"1970","journal-title":"Econ. Geogr."},{"key":"2023012711561781500_btu418-B20","doi-asserted-by":"crossref","first-page":"14847","DOI":"10.1073\/pnas.0403170101","article-title":"Assigning African elephant DNA to geographic region of origin: applications to the ivory trade","volume":"101","author":"Wasser","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012711561781500_btu418-B21","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1093\/genetics\/161.2.873","article-title":"The coalescent in a continuous, finite, linear population","volume":"161","author":"Wilkins","year":"2002","journal-title":"Genetics"},{"key":"2023012711561781500_btu418-B22","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1038\/ng.2285","article-title":"A model-based approach for analysis of spatial structure in genetic data","volume":"44","author":"Yang","year":"2012","journal-title":"Nat. Genet."},{"key":"2023012711561781500_btu418-B23","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/s11222-009-9166-3","article-title":"A quasi-Newton acceleration for high-dimensional optimization algorithms","volume":"21","author":"Zhou","year":"2011","journal-title":"Stat. Comput."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/20\/2915\/48929906\/bioinformatics_30_20_2915.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/20\/2915\/48929906\/bioinformatics_30_20_2915.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T21:46:01Z","timestamp":1717019161000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/20\/2915\/2422247"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,9]]},"references-count":23,"journal-issue":{"issue":"20","published-print":{"date-parts":[[2014,10,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu418","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,10,15]]},"published":{"date-parts":[[2014,7,9]]}}}