{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,23]],"date-time":"2025-05-23T04:12:29Z","timestamp":1747973549116,"version":"3.37.3"},"reference-count":14,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2018,8,25]],"date-time":"2018-08-25T00:00:00Z","timestamp":1535155200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100004440","name":"Wellcome Trust","doi-asserted-by":"publisher","award":["090532\/Z\/09\/Z"],"award-info":[{"award-number":["090532\/Z\/09\/Z"]}],"id":[{"id":"10.13039\/100004440","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>The Li and Stephens model, which approximates the coalescent describing the pattern of variation in a population, underpins a range of key tools and results in genetics. Although highly efficient compared to the coalescent, standard implementations of this model still cannot deal with the very large reference cohorts that are starting to become available, and practical implementations use heuristics to achieve reasonable runtimes.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>Here I describe a new, exact algorithm (\u2018fastLS\u2019) that implements the Li and Stephens model and achieves runtimes independent of the size of the reference cohort. Key to achieving this runtime is the use of the Burrows-Wheeler transform, allowing the algorithm to efficiently identify partial haplotype matches across a cohort. I show that the proposed data structure is very similar to, and generalizes, Durbin\u2019s positional Burrows-Wheeler transform.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/bty735","type":"journal-article","created":{"date-parts":[[2018,8,23]],"date-time":"2018-08-23T11:26:53Z","timestamp":1535023613000},"page":"798-806","source":"Crossref","is-referenced-by-count":14,"title":["Haplotype matching in large cohorts using the Li and Stephens model"],"prefix":"10.1093","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3798-2058","authenticated-orcid":false,"given":"Gerton","family":"Lunter","sequence":"first","affiliation":[{"name":"University of Oxford, Wellcome Centre for Human Genetics, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2018,8,25]]},"reference":[{"key":"2023013107254751400_bty735-B1","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1146\/annurev-ecolsys-102209-144621","article-title":"Approximate Bayesian Computation in evolution and ecology","volume":"41","author":"Beaumont","year":"2010","journal-title":"Ann. Rev. Ecol. Evol. Syst"},{"volume-title":"A Block Sorting Lossless Data Compression Algorithm. Technical Report 12","year":"1994","author":"Burrows","key":"2023013107254751400_bty735-B2"},{"key":"2023013107254751400_bty735-B3","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"},{"volume-title":"Progress in Population Genetics and Human Evolution, Volume 87 of IMA Volumes in Mathematics and Its Applications","year":"1997","author":"Griffiths","key":"2023013107254751400_bty735-B4"},{"key":"2023013107254751400_bty735-B5","doi-asserted-by":"crossref","first-page":"e1000529","DOI":"10.1371\/journal.pgen.1000529","article-title":"A flexible and accurate genotype imputation method for the next generation of genome-wide association studies","volume":"5","author":"Howie","year":"2009","journal-title":"PLoS Genet"},{"key":"2023013107254751400_bty735-B6","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0040-5809(83)90013-8","article-title":"Properties of a neutral allele model with intragenic recombination","volume":"23","author":"Hudson","year":"1983","journal-title":"Theor. Pop. Biol"},{"key":"2023013107254751400_bty735-B7","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1017\/S0021900200034446","article-title":"On the genealogy of large populations","volume":"19","author":"Kingman","year":"1982","journal-title":"J. Appl. Probab"},{"key":"2023013107254751400_bty735-B8","doi-asserted-by":"crossref","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short dna sequences to the human genome","volume":"10","author":"Langmead","year":"2009","journal-title":"Genome Biol"},{"key":"2023013107254751400_bty735-B9","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows-Wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023013107254751400_bty735-B10","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1038\/nature10231","article-title":"Inference of human population history from individual whole-genome sequences","volume":"475","author":"Li","year":"2011","journal-title":"Nature"},{"key":"2023013107254751400_bty735-B11","doi-asserted-by":"crossref","first-page":"2213","DOI":"10.1093\/genetics\/165.4.2213","article-title":"Modeling linkage disequilibrium and identifying recombination hotspots using single-nucleotide polymorphism data","volume":"165","author":"Li","year":"2003","journal-title":"Genetics"},{"key":"2023013107254751400_bty735-B12","doi-asserted-by":"crossref","first-page":"1680","DOI":"10.1093\/bioinformatics\/btu861","article-title":"scrm: efficiently simulating long sequences using the approximated coalescent with recombination","volume":"31","author":"Staab","year":"2015","journal-title":"Bioinformatics"},{"key":"2023013107254751400_bty735-B13","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1038\/nature04226","article-title":"A haplotype map of the human genome","volume":"437","year":"2005","journal-title":"Nature"},{"key":"2023013107254751400_bty735-B14","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1038\/nature05911","article-title":"Genome-wide association study of 14 000 cases of seven common diseases and 3000 shared controls","volume":"447","year":"2007","journal-title":"Nature"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/5\/798\/48966042\/bioinformatics_35_5_798.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/5\/798\/48966042\/bioinformatics_35_5_798.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T10:21:09Z","timestamp":1675160469000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/35\/5\/798\/5079326"}},"subtitle":[],"editor":[{"given":"Oliver","family":"Stegle","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2018,8,25]]},"references-count":14,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bty735","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2019,3,1]]},"published":{"date-parts":[[2018,8,25]]}}}