{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T09:14:03Z","timestamp":1774170843086,"version":"3.50.1"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T00:00:00Z","timestamp":1581292800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T00:00:00Z","timestamp":1581292800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"JSPS KASKENHI","award":["JP16H02783"],"award-info":[{"award-number":["JP16H02783"]}]},{"name":"ANR Hydrogen","award":["ANR-14-CE23-0001"],"award-info":[{"award-number":["ANR-14-CE23-0001"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Recent large-scale community sequencing efforts allow at an unprecedented level of detail the identification of genomic regions that show signatures of natural selection. Traditional methods for identifying such regions from individuals\u2019 haplotype data, however, require excessive computing times and therefore are not applicable to current datasets. In 2019, Cunha et al. (Advances in bioinformatics and computational biology: 11th Brazilian symposium on bioinformatics, BSB 2018, Niter\u00f3i, Brazil, October 30 - November 1, 2018, Proceedings, 2018. <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"doi\" xlink:href=\"https:\/\/doi.org\/10.1007\/978-3-030-01722-4_3\">10.1007\/978-3-030-01722-4_3<\/jats:ext-link>) suggested the <jats:italic>maximal perfect haplotype block<\/jats:italic> as a very simple combinatorial pattern, forming the basis of a new method to perform rapid genome-wide selection scans. The algorithm they presented for identifying these blocks, however, had a worst-case running time quadratic in the genome length. It was posed as an open problem whether an optimal, linear-time algorithm exists. In this paper we give two algorithms that achieve this time bound, one conceptually very simple one using suffix trees and a second one using the positional Burrows\u2013Wheeler Transform, that is very efficient also in practice.<\/jats:p>","DOI":"10.1186\/s13015-020-0163-6","type":"journal-article","created":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T09:03:02Z","timestamp":1581325382000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Finding all maximal perfect haplotype blocks in linear time"],"prefix":"10.1186","volume":"15","author":[{"given":"Jarno","family":"Alanko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hideo","family":"Bannai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bastien","family":"Cazaux","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Peterlongo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4656-7155","authenticated-orcid":false,"given":"Jens","family":"Stoye","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,10]]},"reference":[{"issue":"D1","key":"163_CR1","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1093\/nar\/gky1120","volume":"47","author":"A Buniello","year":"2018","unstructured":"Buniello A, MacArthur JAL, Cerezo M, Harris LW, Hayhurst J, Malangone C, McMahon A, Morales J, Mountjoy E, Sollis E, Suveges D, Vrousgou O, Whetzel PL, Amode R, Guillen JA, Riat HS, Trevanion SJ, Hall P, Junkins H, Flicek P, Burdett T, Hindorff LA, Cunningham F, Parkinson H. The NHGRI-EBI GWAS catalog of published genome-wide association studies, targeted arrays and summary statistics 2019. Nucl Acids Res. 2018;47(D1):1005\u201312. https:\/\/doi.org\/10.1093\/nar\/gky1120.","journal-title":"Nucl Acids Res"},{"issue":"7571","key":"163_CR2","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1038\/nature15393","volume":"526","author":"A Auton","year":"2015","unstructured":"Auton A, Brooks LD, Durbin RM, Garrison EP, Min Kang H, Korbel JO, Marchini JL, McCarthy S, McVean GA, Abecasis GR, 1000 Genomes Project Consortium. A global reference for human genetic variation. Nature. 2015;526(7571):68\u201374. https:\/\/doi.org\/10.1038\/nature15393.","journal-title":"Nature"},{"issue":"7571","key":"163_CR3","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1038\/nature15394","volume":"526","author":"PH Sudmant","year":"2015","unstructured":"Sudmant PH, Rausch T, Gardner EJ, Handsaker RE, Abyzov A, Huddleston J, Zhang Y, Ye K, Jun G, Hsi-Yang Fritz M, Konkel MK, Malhotra A, St\u00fctz AM, Shi X, Paolo Casale F, Chen J, Hormozdiari F, Dayama G, Chen K, Malig M, Chaisson MJP, Walter K, Meiers S, Kashin S, Garrison E, Auton A, Lam HYK, Jasmine MuX, Alkan C, Antaki D, Bae T, Cerveira E, Chines P, Chong Z, Clarke L, Dal E, Ding L, Emery S, Fan X, Gujral M, Kahveci F, Kidd JM, Kong Y, Lameijer E-W, McCarthy S, Flicek P, Gibbs RA, Marth G, Mason CE, Menelaou A, Muzny DM, Nelson BJ, Noor A, Parrish NF, Pendleton M, Quitadamo A, Raeder B, Schadt EE, Romanovitch M, Schlattl A, Sebra R, Shabalin AA, Untergasser A, Walker JA, Wang M, Yu F, Zhang C, Zhang J, Zheng-Bradley X, Zhou W, Zichner T, Sebat J, Batzer MA, McCarroll SA, Mills RE, Gerstein MB, Bashir A, Stegle O, Devine SE, Lee C, Eichler EE, Korbel JO, The 1000 Genomes Project Consortium. An integrated map of structural variation in 2504 human genomes. Nature. 2015;526(7571):75\u201381. https:\/\/doi.org\/10.1038\/nature15394.","journal-title":"Nature"},{"key":"163_CR4","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1038\/ng.3247","volume":"47","author":"DF Gudbjartsson","year":"2015","unstructured":"Gudbjartsson DF, Helgason H, Gudjonsson SA, Zink F, Oddson A, Gylfason A, Besenbacher S, Magnusson G, Halldorsson BV, Hjartarson E, Sigurdsson GT, Stacey SN, Frigge ML, Holm H, Saemundsdottir J, Helgadottir HT, Johannsdottir H, Sigfusson G, Thorgeirsson G, Sverrisson JT, Gretarsdottir S, Walters GB, Rafnar T, Thjodleifsson B, Bjornsson ES, Olafsson S, Thorarinsdottir H, Steingrimsdottir T, Gudmundsdottir TS, Theodors A, Jonasson JG, Sigurdsson A, Bjornsdottir G, Jonsson JJ, Thorarensen O, Ludvigsson P, Gudbjartsson H, Eyjolfsson GI, Sigurdardottir O, Olafsson I, Arnar DO, Magnusson OT, Kong A, Masson G, Thorsteinsdottir U, Helgason A, Sulem P, Stefansson K. Large-scale whole-genome sequencing of the Icelandic population. Nat Genet. 2015;47:435\u201344. https:\/\/doi.org\/10.1038\/ng.3247.","journal-title":"Nat Genet"},{"key":"163_CR5","doi-asserted-by":"publisher","first-page":"12989","DOI":"10.1038\/ncomms12989","volume":"7","author":"JY Hehir-Kwa","year":"2016","unstructured":"Hehir-Kwa JY, Marschall T, Kloosterman WP, Francioli LC, Baaijens JA, Dijkstra LJ, Abdellaoui A, Koval V, Thung DT, Wardenaar R, Renkens I, Coe BP, Deelen P, de Ligt J, Lameijer E-W, van Dijk F, Hormozdiari F, Consortium TGotN, Bovenberg JA, de Craen AJM, Beekman M, Hofman A, Willemsen G, Wolffenbuttel B, Platteel M, Du Y, Chen R, Cao H, Cao R, Sun Y, Cao JS, Neerincx PBT, Dijkstra M, Byelas G, Kanterakis A, Bot J, Vermaat M, Laros JFJ, den Dunnen JT, de Knijff P, Karssen LC, van Leeuwen EM, Amin N, Rivadeneira F, Estrada K, Hottenga J-J, Kattenberg VM, van Enckevort D, Mei H, Santcroos M, van Schaik BDC, Handsaker RE, McCarroll SA, Ko A, Sudmant P, Nijman IJ, Uitterlinden AG, van Duijn CM, Eichler EE, de Bakker PIW, Swertz MA, Wijmenga C, van Ommen G-JB, Slagboom PE, Boomsma DI, Sch\u00f6nhuth A, Ye K, Guryev V. A high-quality human reference panel reveals the complexity and distribution of genomic structural variants. Nat Commun. 2016;7:12989. https:\/\/doi.org\/10.1038\/ncomms12989.","journal-title":"Nat Commun"},{"key":"163_CR6","doi-asserted-by":"publisher","first-page":"1687","DOI":"10.1136\/bmj.k1687","volume":"361","author":"C Turnbull","year":"2018","unstructured":"Turnbull C, Scott RH, Thomas E, Jones L, Murugaesu N, Pretty FB, Halai D, Baple E, Craig C, Hamblin A, Henderson S, Patch C, O\u2019Neill A, Devereau A, Smith K, Martin AR, Sosinsky A, McDonagh EM, Sultana R, Mueller M, Smedley D, Toms A, Dinh L, Fowler T, Bale M, Hubbard TJP, Rendon A, Hill S, Caulfield MJ. 100 000 Genomes Project: the 100 000 genomes project: bringing whole genome sequencing to the NHS. BMJ. 2018;361:1687. https:\/\/doi.org\/10.1136\/bmj.k1687.","journal-title":"BMJ"},{"key":"163_CR7","doi-asserted-by":"publisher","DOI":"10.2307\/2533705","volume-title":"Population genetics\u2014a concise guide","author":"JH Gillespie","year":"1998","unstructured":"Gillespie JH. Population genetics\u2014a concise guide. Baltimore: The Johns Hopkins University Press; 1998."},{"key":"163_CR8","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-030-01722-4_3","volume-title":"Advances in Bioinformatics and Computational Biology","author":"Lu\u00eds Cunha","year":"2018","unstructured":"Cunha L, Diekmann Y, Kowada LAB, Stoye J Identifying maximal perfect haplotype blocks. In: Advances in bioinformatics and computational biology: 11th Brazilian symposium on bioinformatics, BSB 2018, Niter\u00f3i, Brazil, October 30 - November 1, 2018, Proceedings; 2018. p. 26\u201337. https:\/\/doi.org\/10.1007\/978-3-030-01722-4_3."},{"key":"163_CR9","doi-asserted-by":"publisher","unstructured":"Alanko J, Bannai H, Cazaux B, Peterlongo P, Stoye J Finding all maximal perfect haplotype blocks in linear time. In: Huber, K.T., Gusfield, D. (eds.) 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). LIPIcs, vol. 143:8, p. 1\u20139 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2019.8","DOI":"10.4230\/LIPIcs.WABI.2019.8"},{"key":"163_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees, and sequences: computer science and computational biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield D. Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge: Cambridge University Press; 1997."},{"issue":"5","key":"163_CR11","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1093\/bioinformatics\/bty735","volume":"35","author":"G Lunter","year":"2019","unstructured":"Lunter G. Haplotype matching in large cohorts using the Li and Stephens model. Bioinformatics. 2019;35(5):798\u2013806. https:\/\/doi.org\/10.1093\/bioinformatics\/bty735.","journal-title":"Bioinformatics"},{"key":"163_CR12","unstructured":"Farach M Optimal suffix tree construction with large alphabets. In: Proceedings 38th annual symposium on foundations of computer science. New York: IEEE; 1997. p. 137\u2013143."},{"issue":"9","key":"163_CR13","doi-asserted-by":"publisher","first-page":"1266","DOI":"10.1093\/bioinformatics\/btu014","volume":"30","author":"R Durbin","year":"2014","unstructured":"Durbin R. Efficient haplotype matching and storage using the positional Burrows\u2013Wheeler transform (PBWT). Bioinformatics. 2014;30(9):1266\u201372. https:\/\/doi.org\/10.1093\/bioinformatics\/btu014.","journal-title":"Bioinformatics"},{"issue":"1","key":"163_CR14","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","volume":"2","author":"MI Abouelhoda","year":"2004","unstructured":"Abouelhoda MI, Kurtz S, Ohlebusch E. Replacing suffix trees with enhanced suffix arrays. J Discret Algorithms. 2004;2(1):53\u201386. https:\/\/doi.org\/10.1016\/S1570-8667(03)00065-0.","journal-title":"J Discret Algorithms"},{"key":"163_CR15","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.tpb.2014.11.001","volume":"99","author":"H Chen","year":"2015","unstructured":"Chen H, Hey J, Slatkin M. A hidden Markov model for investigating recent positive selection through haplotype structure. Theor Popul Biol. 2015;99:18\u201330. https:\/\/doi.org\/10.1016\/j.tpb.2014.11.001.","journal-title":"Theor Popul Biol."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-020-0163-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13015-020-0163-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-020-0163-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T01:21:35Z","timestamp":1612833695000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-020-0163-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,10]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["163"],"URL":"https:\/\/doi.org\/10.1186\/s13015-020-0163-6","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,10]]},"assertion":[{"value":"18 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"2"}}