{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T18:08:34Z","timestamp":1764785314386,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T00:00:00Z","timestamp":1706140800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T00:00:00Z","timestamp":1706140800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100007625","name":"Cure Alzheimer's Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007625","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["1R01 AI 154470-01","2U01 HG 008685","R21 HD 095228 008976","U01 HL 089856","U01 HL 089897","P01 HL 120839","P01 HL 132825","2U01 HG 008685","R21 HD 095228","P01HL132825"],"award-info":[{"award-number":["1R01 AI 154470-01","2U01 HG 008685","R21 HD 095228 008976","U01 HL 089856","U01 HL 089897","P01 HL 120839","P01 HL 132825","2U01 HG 008685","R21 HD 095228","P01HL132825"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["NSF PHY 2033046","NSF GRFP 1745302"],"award-info":[{"award-number":["NSF PHY 2033046","NSF GRFP 1745302"]}]},{"name":"NIH Center grant","award":["P30-ES002109"],"award-info":[{"award-number":["P30-ES002109"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The computation of a similarity measure for genomic data is a standard tool in computational genetics. The principal components of such matrices are routinely used to correct for biases due to confounding by population stratification, for instance in linear regressions. However, the calculation of both a similarity matrix and its singular value decomposition (SVD) are computationally intensive. The contribution of this article is threefold. First, we demonstrate that the calculation of three matrices (called the covariance matrix, the weighted Jaccard matrix, and the genomic relationship matrix) can be reformulated in a unified way which allows for the application of a randomized SVD algorithm, which is faster than the traditional computation. The fast SVD algorithm we present is adapted from an existing randomized SVD algorithm and ensures that all computations are carried out in sparse matrix algebra. The algorithm only assumes that row-wise and column-wise subtraction and multiplication of a vector with a sparse matrix is available, an operation that is efficiently implemented in common sparse matrix packages. An exception is the so-called Jaccard matrix, which does not have a structure applicable for the fast SVD algorithm. Second, an approximate Jaccard matrix is introduced to which the fast SVD computation is applicable. Third, we establish guaranteed theoretical bounds on the accuracy (in <jats:inline-formula><jats:alternatives><jats:tex-math>$$L_2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>L<\/mml:mi>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> norm and angle) between the principal components of the Jaccard matrix and the ones of our proposed approximation, thus putting the proposed Jaccard approximation on a solid mathematical foundation, and derive the theoretical runtime of our algorithm. We illustrate that the approximation error is low in practice and empirically verify the theoretical runtime scalings on both simulated data and data of the 1000 Genome Project.<\/jats:p>","DOI":"10.1186\/s12859-024-05650-8","type":"journal-article","created":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T19:02:46Z","timestamp":1706209366000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fast computation of the eigensystem of genomic similarity matrices"],"prefix":"10.1186","volume":"25","author":[{"given":"Georg","family":"Hahn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharon M.","family":"Lutz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julian","family":"Hecker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dmitry","family":"Prokopenko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael H.","family":"Cho","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edwin K.","family":"Silverman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Scott T.","family":"Weiss","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Lange","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,25]]},"reference":[{"issue":"4","key":"5650_CR1","doi-asserted-by":"publisher","first-page":"e93766","DOI":"10.1371\/journal.pone.0093766","volume":"9","author":"G Abraham","year":"2014","unstructured":"Abraham G, Inouye M. Fast principal component analysis of large-scale genome-wide data. PLoS ONE. 2014;9(4):e93766.","journal-title":"PLoS ONE"},{"key":"5650_CR2","unstructured":"Bates D, Maechler M, Jagan M, Davis TA, Oehlschl\u00e4gel J, and Riedy J. Matrix: sparse and dense matrix classes and methods, 2023. R-package version 1.5-4.1: https:\/\/cran.r-project.org\/package=Matrix."},{"issue":"8","key":"5650_CR3","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1038\/ng1607","volume":"37","author":"CD Campbell","year":"2005","unstructured":"Campbell CD, Ogburn EL, Lunetta KL, Lyon HN, Freedman ML, Groop LC, Altshuler D, Ardlie KG, Hirschhorn JN. Demonstrating stratification in a European American population. Nat Genet. 2005;37(8):868\u201372.","journal-title":"Nat Genet"},{"issue":"1","key":"5650_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0707001","volume":"7","author":"C Davis","year":"1970","unstructured":"Davis C, Kahan WM. The rotation of eigenvectors by a perturbation. III SIAM J Numer Anal. 1970;7(1):1\u201346.","journal-title":"III. SIAM J Numer Anal"},{"issue":"5","key":"5650_CR5","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1086\/516842","volume":"80","author":"MP Epstein","year":"2007","unstructured":"Epstein MP, Allen AS, Satten GA. A simple and improved correction for population stratification in case-control studies. Am J Hum Genet. 2007;80(5):921\u201330.","journal-title":"Am J Hum Genet"},{"key":"5650_CR6","first-page":"749","volume":"6","author":"S Gerschgorin","year":"1931","unstructured":"Gerschgorin S. \u00dcber die abgrenzung der eigenwerte einer matrix. Izv Akad Nauk USSR Otd Fiz-Mat Nauk. 1931;6:749\u201354.","journal-title":"Izv Akad Nauk USSR Otd Fiz-Mat Nauk"},{"key":"5650_CR7","unstructured":"Golub GH, Van Loan CF. Matrix computations. 3rd ed. Johns Hopkins Studies in Mathematical Sciences; 1996."},{"issue":"1","key":"5650_CR8","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1002\/gepi.22356","volume":"45","author":"G Hahn","year":"2021","unstructured":"Hahn G, Lutz SM, Hecker J, Prokopenko D, Cho MH, Silverman EK, Weiss ST. Christ langeoph and The NHLBI trans-omics for precision medicine (TOPMed) consortium. locStra: fast analysis of regional\/global stratification in whole-genome sequencing studies. Genet Epidemiol. 2021;45(1):82\u201398.","journal-title":"Genet Epidemiol"},{"issue":"7","key":"5650_CR9","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1002\/gepi.22421","volume":"45","author":"G Hahn","year":"2021","unstructured":"Hahn G, Wu C, Lee S, Lutz S, Khurana S, Baden L, Haneuse S, Qiao D, Hecker J, DeMeo D, Tanzi R, Choudhary M, Etemad B, Mohammadi A, Esmaeilzadeh E, Cho M, Li J, Randolph A, Laird N, Weiss S, Silverman E, Ribbeck K, Lange C. Genome-wide association analysis of COVID-19 mortality risk in SARS-CoV-2 genomes identifies mutation in the SARS-CoV-2 spike protein that colocalizes with P.1 of the Brazilian strain. Genet Epidemiol. 2021;45(7):685\u201393.","journal-title":"Genet Epidemiol"},{"key":"5650_CR10","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1186\/s12859-022-05105-y","volume":"23","author":"G Hahn","year":"2022","unstructured":"Hahn G, Lee S, Prokopenko D, Abraham J, Novak T, Hecker J, Cho M, Khurana S, Baden L, Randolph A, Weiss S, Lange C. Unsupervised outlier detection applied to SARS-CoV-2 nucleotide sequences can identify sequences of common variants and other variants of interest. BMC Bioinf. 2022;23:547.","journal-title":"BMC Bioinf."},{"key":"5650_CR11","unstructured":"Hahn G, Lutz SM, Lange C. locStra: fast implementation of (Local) population stratification methods; 2022. R-package version 1.9: https:\/\/cran.r-project.org\/package=locStra."},{"issue":"2","key":"5650_CR12","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1137\/090771806","volume":"53","author":"N Halko","year":"2011","unstructured":"Halko N, Martinsson P-G, Tropp JA. Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 2011;53(2):217\u201388.","journal-title":"SIAM Rev"},{"key":"5650_CR13","first-page":"547","volume":"37","author":"P Jaccard","year":"1901","unstructured":"Jaccard P. \u00c9tude comparative de la distribution florale dans une portion des Alpes et des Jura. Bull Soc Vaud Des Sci Nat. 1901;37:547\u201379.","journal-title":"Bull Soc Vaud Des Sci Nat"},{"issue":"4","key":"5650_CR14","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1002\/gepi.21621","volume":"36","author":"S Lee","year":"2012","unstructured":"Lee S, Epstein MP, Duncan R, Lin X. Sparse principal component analysis for identifying ancestry-informative markers in genome-wide association studies. Genet Epidemiol. 2012;36(4):293\u2013302.","journal-title":"Genet Epidemiol"},{"key":"5650_CR15","doi-asserted-by":"crossref","unstructured":"Lee S, Hahn G, Hecker J, Lutz S, Mullin K, Hide W, Bertram L, DeMeo D, Tanzi R, Lange C, Prokopenko D, Alzheimer\u2019s Disease Neuroimaging Initiative (ADNI). A comparison between similarity matrices for principal component analysis to assess population stratification in sequenced genetic data sets. Brief Bioinf. 2023;24(1):bbac611.","DOI":"10.1093\/bib\/bbac611"},{"issue":"3","key":"5650_CR16","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1002\/gepi.20296","volume":"32","author":"Q Li","year":"2008","unstructured":"Li Q, Yu K. Improved correction for population stratification in genomewide association studies by identifying hidden population structures. Genet Epidemiol. 2008;32(3):215\u201326.","journal-title":"Genet Epidemiol"},{"issue":"12","key":"5650_CR17","doi-asserted-by":"publisher","first-page":"e190","DOI":"10.1371\/journal.pgen.0020190","volume":"2","author":"N Patterson","year":"2006","unstructured":"Patterson N, Price AL, Reich D. Population structure and eigenanalysis. PLoS Genet. 2006;2(12):e190.","journal-title":"PLoS Genet"},{"key":"5650_CR18","doi-asserted-by":"publisher","first-page":"904","DOI":"10.1038\/ng1847","volume":"38","author":"AL Price","year":"2006","unstructured":"Price AL, Patterson NJ, Plenge RM, Weinblatt ME, Shadick NA, Reich D. Principal components analysis corrects for stratification in genome-wide association studies. Nat Genet. 2006;38:904\u20139.","journal-title":"Nat Genet"},{"issue":"9","key":"5650_CR19","doi-asserted-by":"publisher","first-page":"1366","DOI":"10.1093\/bioinformatics\/btv752","volume":"32","author":"D Prokopenko","year":"2016","unstructured":"Prokopenko D, Hecker J, Silverman EK, Pagano M, N\u00f6then MM, Dina C, Lange C, Fier HL. Utilizing the Jaccard index to reveal population stratification in sequencing data: a simulation study and an application to the 1000 genomes project. Bioinformatics. 2016;32(9):1366\u201372.","journal-title":"Bioinformatics"},{"key":"5650_CR20","unstructured":"Qiu Y, Mei J, Guennebaud G, Niesen J. RSpectra: solvers for large-scale eigenvalue and SVD problems, 2022. R-package version 0.16-1: https:\/\/cran.r-project.org\/package=RSpectra."},{"key":"5650_CR21","unstructured":"R Core Team. R: a language and environment for statistical computing. R Foundation for Stat Comp, Vienna, Austria; 2014."},{"issue":"1","key":"5650_CR22","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1002\/1098-2272(200101)20:1<4::AID-GEPI2>3.0.CO;2-T","volume":"20","author":"D Reich","year":"2001","unstructured":"Reich D, Goldstein D. Detecting association in a case-control study while correcting for population stratification. Genet Epidemiol. 2001;20(1):4\u201316.","journal-title":"Genet Epidemiol"},{"key":"5650_CR23","unstructured":"Rigollet P. IDS.160 - mathematical statistics: a non-asymptotic approach, 2020. MIT lecture: https:\/\/math.mit.edu\/~rigollet\/IDS160\/."},{"issue":"32","key":"5650_CR24","first-page":"1","volume":"4","author":"J Sch\u00e4fer","year":"2005","unstructured":"Sch\u00e4fer J, Strimmer K. A shrinkage approach to large-scale covariance matrix estimation and implications for functional genomics. Stat Appl Genet Mol Biol. 2005;4(32):1\u201330.","journal-title":"Stat Appl Genet Mol Biol"},{"issue":"13","key":"5650_CR25","doi-asserted-by":"publisher","first-page":"1972","DOI":"10.1093\/bioinformatics\/btx109","volume":"33","author":"D Schlauch","year":"2017","unstructured":"Schlauch D, Fier H, Lange C. Identification of genetic outliers due to sub-structure and cryptic relationships. Bioinformatics. 2017;33(13):1972\u20139.","journal-title":"Bioinformatics"},{"key":"5650_CR26","unstructured":"Shaun Purcell and Christopher Chang. PLINK2, 2019. Version 2.0: www.cog-genomics.org\/plink\/2.0\/."},{"issue":"3","key":"5650_CR27","doi-asserted-by":"publisher","first-page":"e1001779","DOI":"10.1371\/journal.pmed.1001779","volume":"12","author":"C Sudlow","year":"2015","unstructured":"Sudlow C, Gallacher J, Allen N, Beral V, Burton P, Danesh J, Downey P, Elliott P, Green J, Landray M, Liu B, Matthews P, Ong G, Pell J, Silman A, Young A, Sprosen T, Peakman T, Collins R. UK biobank: an open access resource for identifying the causes of a wide range of complex diseases of middle and old age. PLoS Med. 2015;12(3):e1001779.","journal-title":"PLoS Med"},{"key":"5650_CR28","unstructured":"The 1000 Genomes Project Consortium. A global reference for human genetic variation. Nature 2015;526(68\u201374)."},{"key":"5650_CR29","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1002\/zamm.19290090206","volume":"9","author":"R von Mises","year":"1929","unstructured":"von Mises R, Pollaczek-Geiringer H. Praktische verfahren der gleichungsaufloesung. ZAMM Z Angew Math Mech. 1929;9:152\u201364.","journal-title":"ZAMM Z Angew Math Mech"},{"issue":"1","key":"5650_CR30","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.ajhg.2010.11.011","volume":"88","author":"J Yang","year":"2011","unstructured":"Yang J, Lee SH, Goddard ME, Visscher PM. GCTA: a tool for genome-wide complex trait analysis. Am J Hum Genet. 2011;88(1):76\u201382.","journal-title":"Am J Hum Genet"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-024-05650-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-024-05650-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-024-05650-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T19:02:58Z","timestamp":1706209378000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-024-05650-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,25]]},"references-count":30,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["5650"],"URL":"https:\/\/doi.org\/10.1186\/s12859-024-05650-8","relation":{},"ISSN":["1471-2105"],"issn-type":[{"type":"electronic","value":"1471-2105"}],"subject":[],"published":{"date-parts":[[2024,1,25]]},"assertion":[{"value":"7 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"43"}}