{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:34:21Z","timestamp":1772138061703,"version":"3.50.1"},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T00:00:00Z","timestamp":1683763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R01HG010086"],"award-info":[{"award-number":["R01HG010086"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R56HG011509"],"award-info":[{"award-number":["R56HG011509"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,6,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Due to the rapid growth of the genetic database size, genealogical search, a process of inferring familial relatedness by identifying DNA matches, has become a viable approach to help individuals finding missing family members or law enforcement agencies locating suspects. A fast and accurate method is needed to search an out-of-database individual against millions of individuals. Most existing approaches only offer all-versus-all within panel match. Some prototype algorithms offer one-versus-all query from out-of-panel individual, but they do not tolerate errors.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>A new method, random projection-based identity-by-descent (IBD) detection (RaPID) query, is introduced to make fast genealogical search possible. RaPID-Query identifies IBD segments between a query haplotype and a panel of haplotypes. By integrating matches over multiple PBWT indexes, RaPID-Query manages to locate IBD segments quickly with a given cutoff length while allowing mismatched sites. A single query against all UK biobank autosomal chromosomes was completed within 2.76\u2009seconds on average, with the minimum length 7 cM and 700 markers. RaPID-Query achieved a 0.016 false negative rate and a 0.012 false positive rate simultaneously on a chromosome 20 sequencing panel having 86\u00a0265 sites. This is comparable to the state-of-the-art IBD detection method TPBWT(out-of-sample) and Hap-IBD. The high-quality IBD segments yielded by RaPID-Query were able to distinguish up to fourth degree of the familial relatedness for a given individual pair, and the area under the receiver operating characteristic curve values are at least 97.28%.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>The RaPID-Query program is available at https:\/\/github.com\/ucfcbb\/RaPID-Query.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btad312","type":"journal-article","created":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T10:51:17Z","timestamp":1683802277000},"source":"Crossref","is-referenced-by-count":4,"title":["RaPID-Query for fast identity by descent search and genealogical analysis"],"prefix":"10.1093","volume":"39","author":[{"given":"Yuan","family":"Wei","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Central Florida , Orlando, FL 32816, United States"}]},{"given":"Ardalan","family":"Naseri","sequence":"additional","affiliation":[{"name":"School of Biomedical Informatics, University of Texas Health Science Center at Houston , Houston, TX 77030, United States"}]},{"given":"Degui","family":"Zhi","sequence":"additional","affiliation":[{"name":"School of Biomedical Informatics, University of Texas Health Science Center at Houston , Houston, TX 77030, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4051-5549","authenticated-orcid":false,"given":"Shaojie","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Central Florida , Orlando, FL 32816, United States"}]}],"member":"286","published-online":{"date-parts":[[2023,5,11]]},"reference":[{"key":"2023060914211265800_btad312-B1","doi-asserted-by":"crossref","first-page":"e54967","DOI":"10.7554\/eLife.54967","article-title":"A community-maintained standard library of population genetic models","volume":"9","author":"Adrion","year":"2020","journal-title":"eLife"},{"key":"2023060914211265800_btad312-B2","doi-asserted-by":"crossref","first-page":"iyab229","DOI":"10.1093\/genetics\/iyab229","article-title":"Efficient ancestry and mutation simulation with msprime 1.0","volume":"220","author":"Baumdicker","year":"2022","journal-title":"Genetics"},{"key":"2023060914211265800_btad312-B3","doi-asserted-by":"crossref","first-page":"840","DOI":"10.1016\/j.ajhg.2013.09.014","article-title":"Detecting identity by descent and estimating genotype error rates in sequence data","volume":"93","author":"Browning","year":"2013","journal-title":"Am J Hum Genet"},{"key":"2023060914211265800_btad312-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":"2023060914211265800_btad312-B5","doi-asserted-by":"crossref","first-page":"2156","DOI":"10.1093\/bioinformatics\/btr330","article-title":"The variant call format and VCFtools","volume":"27","author":"Danecek","year":"2011","journal-title":"Bioinformatics"},{"key":"2023060914211265800_btad312-B6","doi-asserted-by":"crossref","first-page":"5436","DOI":"10.1038\/s41467-019-13225-y","article-title":"Accurate, scalable and integrative haplotype estimation","volume":"10","author":"Delaneau","year":"2019","journal-title":"Nat Commun"},{"key":"2023060914211265800_btad312-B7","doi-asserted-by":"crossref","first-page":"1266","DOI":"10.1093\/bioinformatics\/btu014","article-title":"Efficient haplotype matching and storage using the positional Burrows-Wheeler transform (PBWT)","volume":"30","author":"Durbin","year":"2014","journal-title":"Bioinformatics"},{"key":"2023060914211265800_btad312-B8","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1126\/science.aau4832","article-title":"Identity inference of genomic data using long-range familial searches","volume":"362","author":"Erlich","year":"2018","journal-title":"Science"},{"key":"2023060914211265800_btad312-B9","doi-asserted-by":"crossref","first-page":"2131","DOI":"10.1093\/molbev\/msaa328","article-title":"Fast and robust identity-by-descent inference with the templated positional Burrows\u2013Wheeler transform","volume":"38","author":"Freyman","year":"2021","journal-title":"Mol Biol Evol"},{"key":"2023060914211265800_btad312-B10","doi-asserted-by":"crossref","first-page":"e1000695","DOI":"10.1371\/journal.pgen.1000695","article-title":"Inferring the joint demographic history of multiple populations from multidimensional SNP frequency data","volume":"5","author":"Gutenkunst","year":"2009","journal-title":"PLoS Genet"},{"key":"2023060914211265800_btad312-B11","doi-asserted-by":"crossref","first-page":"eaau1043","DOI":"10.1126\/science.aau1043","article-title":"Characterizing mutagenic effects of recombination through a sequence-level genetic map","volume":"363","author":"Halldorsson","year":"2019","journal-title":"Science"},{"key":"2023060914211265800_btad312-B12","doi-asserted-by":"crossref","first-page":"e34267","DOI":"10.1371\/journal.pone.0034267","article-title":"Cryptic distant relatives are common in both isolated and cosmopolitan genetic samples","volume":"7","author":"Henn","year":"2012","journal-title":"PLoS ONE"},{"key":"2023060914211265800_btad312-B13","doi-asserted-by":"crossref","first-page":"e1004842","DOI":"10.1371\/journal.pcbi.1004842","article-title":"Efficient coalescent simulation and genealogical analysis for large sample sizes","volume":"12","author":"Kelleher","year":"2016","journal-title":"PLoS Comput Biol"},{"key":"2023060914211265800_btad312-B14","doi-asserted-by":"crossref","first-page":"e1004144","DOI":"10.1371\/journal.pgen.1004144","article-title":"Relationship estimation from whole-genome sequence data","volume":"10","author":"Li","year":"2014","journal-title":"PLoS Genet"},{"key":"2023060914211265800_btad312-B15","doi-asserted-by":"crossref","first-page":"2867","DOI":"10.1093\/bioinformatics\/btq559","article-title":"Robust relationship inference in genome-wide association studies","volume":"26","author":"Manichaikul","year":"2010","journal-title":"Bioinformatics"},{"key":"2023060914211265800_btad312-B16","doi-asserted-by":"crossref","first-page":"6130","DOI":"10.1038\/s41467-020-19588-x","article-title":"Identity-by-descent detection across 487,409 British samples reveals fine scale population structure and ultra-rare variant associations","volume":"11","author":"Nait Saada","year":"2020","journal-title":"Nat Commun"},{"key":"2023060914211265800_btad312-B17","doi-asserted-by":"crossref","first-page":"i233","DOI":"10.1093\/bioinformatics\/btz347","article-title":"Efficient haplotype matching between a query and a panel for genealogical search","volume":"35","author":"Naseri","year":"2019","journal-title":"Bioinformatics"},{"key":"2023060914211265800_btad312-B18","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1186\/s13059-019-1754-8","article-title":"RaPID: ultra-fast, powerful, and accurate detection of segments identical by descent (IBD) in biobank-scale cohorts","volume":"20","author":"Naseri","year":"2019","journal-title":"Genome Biol"},{"key":"2023060914211265800_btad312-B19","doi-asserted-by":"crossref","first-page":"e1008619","DOI":"10.1371\/journal.pgen.1008619","article-title":"Accounting for long-range correlations in genome-wide simulations of large cohorts","volume":"16","author":"Nelson","year":"2020","journal-title":"PLoS Genet"},{"key":"2023060914211265800_btad312-B20","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.ajhg.2020.12.004","article-title":"Distinguishing pedigree relationships via multi-way identity by descent sharing and sex-specific genetic maps","volume":"108","author":"Qiao","year":"2021","journal-title":"Am J Hum Genet"},{"key":"2023060914211265800_btad312-B21","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.ajhg.2018.05.008","article-title":"Inferring identical-by-descent sharing of sample ancestors promotes high-resolution relative detection","volume":"103","author":"Ramstetter","year":"2018","journal-title":"Am J Hum Genet"},{"key":"2023060914211265800_btad312-B22","doi-asserted-by":"crossref","first-page":"2390","DOI":"10.1093\/bioinformatics\/btab117","article-title":"d-PBWT: dynamic positional burrows\u2013wheeler transform","volume":"37","author":"Sanaullah","year":"2021","journal-title":"Bioinformatics"},{"key":"2023060914211265800_btad312-B23","doi-asserted-by":"crossref","first-page":"3546","DOI":"10.1038\/s41467-021-22910-w","article-title":"Rapid detection of identity-by-descent tracts for mega-scale datasets","volume":"12","author":"Shemirani","year":"2021","journal-title":"Nat Commun"},{"key":"2023060914211265800_btad312-B24","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1038\/nrg3821","article-title":"Relatedness in the post-genomic era: is it still useful?","volume":"16","author":"Speed","year":"2015","journal-title":"Nat Rev Genet"},{"key":"2023060914211265800_btad312-B25","doi-asserted-by":"crossref","first-page":"1725","DOI":"10.3389\/fgene.2021.722602","article-title":"Current developments in detection of identity-by-descent methods and applications","volume":"12","author":"Sticca","year":"2021","journal-title":"Front Genet"},{"key":"2023060914211265800_btad312-B26","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1038\/s41586-021-03205-y","article-title":"Sequencing of 53,831 diverse genomes from the NHLBI TOPMed program","volume":"590","author":"Taliun","year":"2021","journal-title":"Nature"},{"key":"2023060914211265800_btad312-B27","doi-asserted-by":"crossref","first-page":"giac111","DOI":"10.1093\/gigascience\/giac111","article-title":"Open-source benchmarking of IBD segment detection methods for biobank-scale cohorts","volume":"11","author":"Tang","year":"2022","journal-title":"GigaScience"},{"key":"2023060914211265800_btad312-B28","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1038\/nature06258","article-title":"A second generation human haplotype map of over 3.1 million SNPs","volume":"449","author":"The International HapMap Consortium","year":"2007","journal-title":"Nature"},{"key":"2023060914211265800_btad312-B29","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1016\/j.ajhg.2019.09.012","article-title":"Estimating the genome-wide mutation rate with three-way identity by descent","volume":"105","author":"Tian","year":"2019","journal-title":"Am J Hum Genet"},{"key":"2023060914211265800_btad312-B30","author":"Williams","year":"2020"},{"key":"2023060914211265800_btad312-B31","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1016\/j.ajhg.2020.02.010","article-title":"A fast and simple method for detecting identity-by-descent segments in large-scale data","volume":"106","author":"Zhou","year":"2020","journal-title":"Am J Hum Genet"},{"key":"2023060914211265800_btad312-B32","doi-asserted-by":"crossref","first-page":"4519","DOI":"10.1093\/bioinformatics\/btaa569","article-title":"IBDkin: fast estimation of kinship coefficients from identity by descent segments","volume":"36","author":"Zhou","year":"2020","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btad312\/50278158\/btad312.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/6\/btad312\/50526020\/btad312.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/6\/btad312\/50526020\/btad312.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T12:38:40Z","timestamp":1686314320000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btad312\/7160137"}},"subtitle":[],"editor":[{"given":"Russell","family":"Schwartz","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2023,5,11]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,6,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btad312","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2022.02.03.478907","asserted-by":"object"}]},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,6,1]]},"published":{"date-parts":[[2023,5,11]]},"article-number":"btad312"}}