{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,26]],"date-time":"2026-04-26T11:33:58Z","timestamp":1777203238824,"version":"3.51.4"},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"15","license":[{"start":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T00:00:00Z","timestamp":1615420800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000025","name":"National Institute of Mental Health","doi-asserted-by":"publisher","award":["2R01 MH100141"],"award-info":[{"award-number":["2R01 MH100141"]}],"id":[{"id":"10.13039\/100000025","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,8,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Pairwise comparison problems arise in many areas of science. In genomics, datasets are already large and getting larger, and so operations that require pairwise comparisons\u2014either on pairs of SNPs or pairs of individuals\u2014are extremely computationally challenging. We propose a generic algorithm for addressing pairwise comparison problems that breaks a large problem (of order n2 comparisons) into multiple smaller ones (each of order n comparisons), allowing for massive parallelization.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We demonstrated that this approach is very efficient for calling identical by descent (IBD) segments between all pairs of individuals in the UK Biobank dataset, with a 250-fold savings in time and 750-fold savings in memory over the standard approach to detecting such segments across the full dataset. This efficiency should extend to other methods of IBD calling and, more generally, to other pairwise comparison tasks in genomics or other areas of science.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and Implementation<\/jats:title>\n                    <jats:p>A GitHub page is available at https:\/\/github.com\/emmanuelsapin with the code to generate data needed for the implementation<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btab084","type":"journal-article","created":{"date-parts":[[2021,3,9]],"date-time":"2021-03-09T07:53:00Z","timestamp":1615276380000},"page":"2121-2125","source":"Crossref","is-referenced-by-count":4,"title":["Novel approach for parallelizing pairwise comparison problems as applied to detecting segments identical by decent in whole-genome data"],"prefix":"10.1093","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7188-3715","authenticated-orcid":false,"given":"Emmanuel","family":"Sapin","sequence":"first","affiliation":[{"name":"Institute for Behavioral Genetics, University of Colorado Boulder , Boulder, CO 80309, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew C","family":"Keller","sequence":"additional","affiliation":[{"name":"Institute for Behavioral Genetics, University of Colorado Boulder , Boulder, CO 80309, USA"},{"name":"Psychology & Neuroscience Department, University of Colorado Boulder , Boulder, CO, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,3,11]]},"reference":[{"key":"2023061310443484000_btab084-B1","first-page":"1","author":"Ali","year":"2009"},{"key":"2023061310443484000_btab084-B2","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1038\/ejhg.2017.6","article-title":"A fast and accurate method for detection of IBD shared haplotypes in genome-wide SNP data","volume":"25","author":"Bjelland","year":"2017","journal-title":"Eur. J. Hum. Genet"},{"key":"2023061310443484000_btab084-B3","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1146\/annurev-genet-110711-155534","article-title":"Identity by descent between distant relatives: detection and applications","volume":"46","author":"Browning","year":"2012","journal-title":"Annu. Rev. Genet"},{"key":"2023061310443484000_btab084-B4","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1038\/s41586-018-0579-z","article-title":"The UK Biobank resource with deep phenotyping and genomic data","volume":"562","author":"Bycroft","year":"2018","journal-title":"Nature"},{"key":"2023061310443484000_btab084-B5","first-page":"278","author":"Chang","year":"2008"},{"key":"2023061310443484000_btab084-B6"},{"key":"2023061310443484000_btab084-B7","first-page":"570","author":"Cormen","year":"1990"},{"key":"2023061310443484000_btab084-B8","doi-asserted-by":"crossref","first-page":"e33531","DOI":"10.1371\/journal.pone.0033531","article-title":"High-order SNP combinations associated with complex diseases: efficient discovery, statistical power and functional interactions","volume":"7","author":"Fang","year":"2012","journal-title":"PLoS One"},{"key":"2023061310443484000_btab084-B9","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1101\/gr.081398.108","article-title":"Whole population, genome-wide mapping of hidden relatedness","volume":"19","author":"Gusev","year":"2009","journal-title":"Genome Res"},{"key":"2023061310443484000_btab084-B10","doi-asserted-by":"crossref","first-page":"706","DOI":"10.1016\/j.ajhg.2011.04.023","article-title":"DASH: a method for identical-by-descent haplotype mapping uncovers association with recent variation","volume":"88","author":"Gusev","year":"2011","journal-title":"Am. J. Hum. Genet"},{"key":"2023061310443484000_btab084-B12","volume-title":"Projective Planes","author":"Hughes","year":"1973"},{"key":"2023061310443484000_btab084-B13","author":"Kiefer"},{"key":"2023061310443484000_btab084-B14","author":"Kleinheksel"},{"key":"2023061310443484000_btab084-B15","first-page":"235","author":"Krej\u010d\u00ed","year":"2018"},{"key":"2023061310443484000_btab084-B16","author":"Lee","year":"2004"},{"key":"2023061310443484000_btab084-B17","volume-title":"Dynamics and Nonlinear Mechanics","author":"Leimanis","year":"1958"},{"key":"2023061310443484000_btab084-B0486203","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1038\/ng.3571","article-title":"Fast and accurate long-range phasing in a UK Biobank cohort","volume":"48","author":"Loh","year":"2016","journal-title":"Nature Genetics"},{"key":"2023061310443484000_btab084-B18","first-page":"1527","volume-title":"Advances in Neural Information Processing Systems 22","author":"Parikshit","year":"2009"},{"key":"2023061310443484000_btab084-B19","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1038\/nrg2865","article-title":"Reconciling the analysis of IBD and IBS in 702 complex trait studies","volume":"11","author":"Powell","year":"2010","journal-title":"Nat. Rev. Genet"},{"key":"2023061310443484000_btab084-B20","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/j.cmpb.2008.11.003","article-title":"Fast calculation of pairwise mutual information for gene regulatory network reconstruction","volume":"94","author":"Qiu","year":"2009","journal-title":"Comput. Methods Programs Biomed"},{"key":"2023061310443484000_btab084-B21","first-page":"57","author":"Sapin","year":"2014"},{"key":"2023061310443484000_btab084-B22","first-page":"85","author":"Sapin","year":"2016"},{"key":"2023061310443484000_btab084-B23","author":"Wauthier","year":"2013"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btab084\/36613437\/btab084.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/15\/2121\/50579124\/btab084.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/15\/2121\/50579124\/btab084.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T06:44:59Z","timestamp":1686638699000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/15\/2121\/6168420"}},"subtitle":[],"editor":[{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2021,3,11]]},"references-count":23,"journal-issue":{"issue":"15","published-print":{"date-parts":[[2021,8,9]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btab084","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2020.07.07.191999","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,8,1]]},"published":{"date-parts":[[2021,3,11]]}}}