{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:47Z","timestamp":1759639007555,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T00:00:00Z","timestamp":1558051200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T00:00:00Z","timestamp":1558051200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100005877","name":"Luonnontieteiden ja Tekniikan Tutkimuksen Toimikunta","doi-asserted-by":"publisher","award":["309048"],"award-info":[{"award-number":["309048"]}],"id":[{"id":"10.13039\/501100005877","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1186\/s13015-019-0147-6","type":"journal-article","created":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T18:04:38Z","timestamp":1558116278000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Linear time minimum segmentation enables scalable founder reconstruction"],"prefix":"10.1186","volume":"14","author":[{"given":"Tuukka","family":"Norri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bastien","family":"Cazaux","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dmitry","family":"Kosolobov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4454-1493","authenticated-orcid":false,"given":"Veli","family":"M\u00e4kinen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,17]]},"reference":[{"issue":"1","key":"147_CR1","first-page":"118","volume":"19","author":"Computational Pan-Genomics Consortium","year":"2018","unstructured":"Computational Pan-Genomics Consortium. Computational pan-genomics: status, promises and challenges. Brief Bioinform. 2018;19(1):118\u201335.","journal-title":"Brief Bioinform"},{"issue":"7571","key":"147_CR2","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1038\/nature15393","volume":"526","author":"The 1000 Genomes Project Consortium","year":"2015","unstructured":"The 1000 Genomes Project Consortium. A global reference for human genetic variation. Nature. 2015;526(7571):68\u201374.","journal-title":"Nature"},{"issue":"7616","key":"147_CR3","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1038\/nature19057","volume":"536","author":"Exome Aggregation Consortium","year":"2016","unstructured":"Exome Aggregation Consortium. Analysis of protein-coding genetic variation in 60,706 humans. Nature. 2016;536(7616):285\u201391.","journal-title":"Nature"},{"issue":"7571","key":"147_CR4","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1038\/nature14962","volume":"526","author":"The UK10K Consortium","year":"2015","unstructured":"The UK10K Consortium. The UK10K project identifies rare variants in health and disease. Nature. 2015;526(7571):82\u201390.","journal-title":"Nature"},{"key":"147_CR5","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1186\/gb-2009-10-9-r98","volume":"10","author":"K Schneeberger","year":"2009","unstructured":"Schneeberger K, Hagmann J, Ossowski S, Warthmann N, Gesing S, Kohlbacher O, Weigel D. Simultaneous alignment of short reads against multiple genomes. Genome Biol. 2009;10:98.","journal-title":"Genome Biol"},{"issue":"13","key":"147_CR6","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1093\/bioinformatics\/btt215","volume":"29","author":"L Huang","year":"2013","unstructured":"Huang L, Popic V, Batzoglou S. Short read alignment with populations of genomes. Bioinformatics. 2013;29(13):361\u201370.","journal-title":"Bioinformatics"},{"issue":"2","key":"147_CR7","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1109\/TCBB.2013.2297101","volume":"11","author":"J Sir\u00e9n","year":"2014","unstructured":"Sir\u00e9n J, V\u00e4lim\u00e4ki N, M\u00e4kinen V. Indexing graphs for path queries with applications in genome research. IEEE\/ACM Trans Comput Biol Bioinform. 2014;11(2):375\u201388.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"147_CR8","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1038\/ng.3257","volume":"47","author":"A Dilthey","year":"2015","unstructured":"Dilthey A, Cox C, Iqbal Z, Nelson MR, McVean G. Improved genome inference in the MHC using a population reference graph. Nat Genet. 2015;47:682\u20138.","journal-title":"Nat Genet"},{"key":"147_CR9","doi-asserted-by":"crossref","unstructured":"Maciuca S, del Ojo\u00a0Elias C, McVean G, Iqbal Z. A natural encoding of genetic variation in a Burrows\u2013Wheeler transform to enable mapping and genome inference. In: Proceedings of the 16th international workshop on algorithms in boinformatics, WABI 2016, Aarhus, Denmark, August 22\u201324, 2016. Lecture Notes in Computer Science, vol. 9838; 2016. p. 222\u201333.","DOI":"10.1007\/978-3-319-43681-4_18"},{"key":"147_CR10","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1038\/nbt.4227","volume":"36","author":"Garrison Erik","year":"2018","unstructured":"Erik Garrison, Jouni Sir\u00e9n, Novak Adam M, Hickey Glenn, Eizenga Jordan M, Dawson Eric T, Jones William, Garg Shilpa, Markello Charles, Lin Michael F, Paten Benedict, Durbin Richard. Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nat Biotechnol. 2018;36:875. https:\/\/doi.org\/10.1038\/nbt.4227 .","journal-title":"Nat Biotechnol"},{"key":"147_CR11","unstructured":"Sir\u00e9n J, Garrison E, Novak AM, Paten B, Durbin R. Haplotype-aware graph indexes. In: 18th international workshop on algorithms in bioinformatics, WABI 2018, August 20\u201322, 2018, Helsinki, Finland. LIPIcs, vol. 113. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Wadern, Germany; 2018. p. 4\u20131413."},{"issue":"Suppl 2","key":"147_CR12","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1186\/s12864-018-4465-8","volume":"19","author":"D Valenzuela","year":"2018","unstructured":"Valenzuela D, Norri T, Niko V, Pitk\u00e4nen E, M\u00e4kinen V. Towards pan-genome read alignment to improve variation calling. BMC Genom. 2018;19(Suppl 2):87.","journal-title":"BMC Genom"},{"issue":"3","key":"147_CR13","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1089\/cmb.2009.0169","volume":"17","author":"V M\u00e4kinen","year":"2010","unstructured":"M\u00e4kinen V, Navarro G, Sir\u00e9n J, V\u00e4lim\u00e4ki N. Storage and retrieval of highly repetitive sequence collections. J Comput Biol. 2010;17(3):281\u2013308.","journal-title":"J Comput Biol"},{"key":"147_CR14","doi-asserted-by":"crossref","unstructured":"Navarro G. Indexing highly repetitive collections. In: Proceedings of 23rd international workshop on combinatorial algorithms (IWOCA). LNCS 7643; 2012. p. 274\u20139.","DOI":"10.1007\/978-3-642-35926-2_29"},{"issue":"13","key":"147_CR15","first-page":"1534","volume":"6","author":"S Wandelt","year":"2013","unstructured":"Wandelt S, Starlinger J, Bux M, Leser U. Rcsi: scalable similarity search in thousand(s) of genomes. PVLDB. 2013;6(13):1534\u201345.","journal-title":"PVLDB"},{"issue":"2016","key":"147_CR16","doi-asserted-by":"publisher","first-page":"20130137","DOI":"10.1098\/rsta.2013.0137","volume":"372","author":"H Ferrada","year":"2014","unstructured":"Ferrada H, Gagie T, Hirvola T, Puglisi SJ. Hybrid indexes for repetitive datasets. Philos Trans R Soc A. 2014;372(2016):20130137.","journal-title":"Philos Trans R Soc A"},{"key":"147_CR17","doi-asserted-by":"publisher","first-page":"12","DOI":"10.3389\/fbioe.2015.00012","volume":"3","author":"T Gagie","year":"2015","unstructured":"Gagie T, Puglisi SJ. Searching and indexing genomic databases via kernelization. Front Bioeng Biotechnol. 2015;3:12.","journal-title":"Front Bioeng Biotechnol"},{"key":"147_CR18","first-page":"277","volume-title":"Lecture Notes in Computer Science","author":"Esko Ukkonen","year":"2002","unstructured":"Ukkonen E. Finding founder sequences from a set of recombinants. In: Proceedings of second international workshop on algorithms in bioinformatics, WABI 2002, Rome, Italy, September 17\u201321, 2002; 2002. p. 277\u201386."},{"key":"147_CR19","doi-asserted-by":"crossref","unstructured":"Rastas P, Ukkonen E. Haplotype inference via hierarchical genotype parsing. In: Proceedings of the 7th international workshop on algorithms in bioinformatics, WABI 2007, Philadelphia, PA, USA, September 8\u20139, 2007; 2007. p. 85\u201397.","DOI":"10.1007\/978-3-540-74126-8_9"},{"issue":"9","key":"147_CR20","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.","journal-title":"Bioinformatics"},{"key":"147_CR21","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.ipl.2019.02.003","volume":"146","author":"V M\u00e4kinen","year":"2019","unstructured":"M\u00e4kinen V, Norri T. Applying the positional Burrows\u2013Wheeler transform to all-pairs hamming distance. Inf Process Lett. 2019;146:17\u20139. https:\/\/doi.org\/10.1016\/j.ipl.2019.02.003 .","journal-title":"Inf Process Lett"},{"key":"147_CR22","unstructured":"Norri T, Cazaux B, Kosolobov D, M\u00e4kinen V. Minimum segmentation for pan-genomic founder reconstruction in linear time. In: 18th international workshop on algorithms in bioinformatics, WABI 2018, August 20\u201322, 2018, Helsinki, Finland. LIPIcs, vol. 113. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Wadern, Germany; 2018. p. 15\u201311515."},{"issue":"2","key":"147_CR23","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J Fischer","year":"2011","unstructured":"Fischer J, Heun V. Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J Comput. 2011;40(2):465\u201392. https:\/\/doi.org\/10.1137\/090779759 .","journal-title":"SIAM J Comput"},{"key":"147_CR24","doi-asserted-by":"crossref","unstructured":"Karp RM, Vazirani UV, Vazirani VV. An optimal algorithm for on-line bipartite matching. In: Proceedings of the twenty-second annual ACM symposium on Theory of computing, STOC. ACM; 1990. p. 352\u20138.","DOI":"10.1145\/100216.100262"},{"key":"147_CR25","first-page":"326","volume-title":"Experimental Algorithms","author":"Simon Gog","year":"2014","unstructured":"Gog S, Beller T, Moffat A, Petri M. From theory to practice: plug and play with succinct data structures. In: 13th international symposium on experimental algorithms, (SEA 2014); 2014. p. 326\u201337."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-019-0147-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13015-019-0147-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-019-0147-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,18]],"date-time":"2022-09-18T06:06:32Z","timestamp":1663481192000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-019-0147-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,17]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["147"],"URL":"https:\/\/doi.org\/10.1186\/s13015-019-0147-6","relation":{},"ISSN":["1748-7188"],"issn-type":[{"type":"electronic","value":"1748-7188"}],"subject":[],"published":{"date-parts":[[2019,5,17]]},"assertion":[{"value":"1 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 May 2019","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":"12"}}