{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,31]],"date-time":"2026-10-31T10:19:26Z","timestamp":1793441966487,"version":"4.5.0"},"reference-count":101,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,3,1]],"date-time":"2022-03-01T00:00:00Z","timestamp":1646092800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T00:00:00Z","timestamp":1646352000000},"content-version":"vor","delay-in-days":3,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Computational pangenomics is an emerging research field that is changing the way computer scientists are facing challenges in biological sequence analysis. In past decades, contributions from combinatorics, stringology, graph theory and data structures were essential in the development of a plethora of software tools for the analysis of the human genome. These tools allowed computational biologists to approach ambitious projects at population scale, such as the 1000 Genomes Project. A major contribution of the 1000 Genomes Project is the characterization of a broad spectrum of genetic variations in the human genome, including the discovery of novel variations in the South Asian, African and European populations\u2014thus enhancing the catalogue of variability within the reference genome. Currently, the need to take into account the high variability in population genomes as well as the specificity of an individual genome in a personalized approach to medicine is rapidly pushing the abandonment of the traditional paradigm of using a single reference genome. A graph-based representation of multiple genomes, or <jats:italic>a graph pangenome<\/jats:italic>, is replacing the linear reference genome. This means completely rethinking well-established procedures to analyze, store, and access information from genome representations. Properly addressing these challenges is crucial to face the computational tasks of ambitious healthcare projects aiming to characterize human diversity by sequencing 1M individuals\u00a0(Stark et\u00a0al. 2019). This tutorial aims to introduce readers to the most recent advances in the theory of data structures for the representation of graph pangenomes. We discuss efficient representations of <jats:italic>haplotypes<\/jats:italic> and the variability of <jats:italic>genotypes<\/jats:italic> in graph pangenomes, and highlight applications in solving computational problems in human and microbial (viral) pangenomes.<\/jats:p>","DOI":"10.1007\/s11047-022-09882-6","type":"journal-article","created":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T15:01:21Z","timestamp":1646406081000},"page":"81-108","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":75,"title":["Computational graph pangenomics: a tutorial on data structures and their applications"],"prefix":"10.1007","volume":"21","author":[{"given":"Jasmijn A.","family":"Baaijens","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paola","family":"Bonizzoni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christina","family":"Boucher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gianluca","family":"Della Vedova","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuri","family":"Pirola","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raffaella","family":"Rizzi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jouni","family":"Sir\u00e9n","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,3,4]]},"reference":[{"issue":"1","key":"9882_CR1","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","volume":"2","author":"M Abouelhoda","year":"2004","unstructured":"Abouelhoda M, Kurtz S, Ohlebusch E (2004) Replacing suffix trees with enhanced suffix arrays. J Discret Algorithms 2(1):53\u201386. https:\/\/doi.org\/10.1016\/S1570-8667(03)00065-0","journal-title":"J Discret Algorithms"},{"issue":"5","key":"9882_CR2","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1101\/gr.215038.116","volume":"27","author":"JA Baaijens","year":"2017","unstructured":"Baaijens JA, Zine El Aabidine A, Rivals E et al (2017) De novo assembly of viral quasispecies using overlap graphs. Genome Res 27(5):835\u2013848. https:\/\/doi.org\/10.1101\/gr.215038.116","journal-title":"Genome Res"},{"issue":"24","key":"9882_CR3","doi-asserted-by":"publisher","first-page":"5086","DOI":"10.1093\/bioinformatics\/btz443","volume":"35","author":"JA Baaijens","year":"2019","unstructured":"Baaijens JA, Van der Roest B, K\u00f6ster J et al (2019) Full-length de novo viral quasispecies assembly through variation graph construction. Bioinformatics 35(24):5086\u20135094. https:\/\/doi.org\/10.1093\/bioinformatics\/btz443","journal-title":"Bioinformatics"},{"key":"9882_CR4","doi-asserted-by":"publisher","unstructured":"Baaijens JA, Stougie L, Sch\u00f6nhuth A (2020) Strain-aware assembly of genomes from mixed samples using flow variation graphs. bioRxiv:645721. https:\/\/doi.org\/10.1101\/645721","DOI":"10.1101\/645721"},{"key":"9882_CR5","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-019-1774-4","author":"S Ballouz","year":"2019","unstructured":"Ballouz S, Dobin A, Gillis JA (2019) Is it time to change the reference genome? Genome Biol. https:\/\/doi.org\/10.1186\/s13059-019-1774-4","journal-title":"Genome Biol"},{"key":"9882_CR6","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.tcs.2019.08.005","volume":"812","author":"H Bannai","year":"2020","unstructured":"Bannai H, Gagie T et al (2020) Refining the r-index. Theor Comput Sci 812:96\u2013108. https:\/\/doi.org\/10.1016\/j.tcs.2019.08.005","journal-title":"Theor Comput Sci"},{"issue":"1","key":"9882_CR7","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1089\/cmb.2013.0112","volume":"21","author":"S Beretta","year":"2014","unstructured":"Beretta S, Bonizzoni P, Della Vedova G et al (2014) Modeling alternative splicing variants from RNA-seq data with isoform graphs. J Comput Biol 21(1):16\u201340. https:\/\/doi.org\/10.1089\/cmb.2013.0112","journal-title":"J Comput Biol"},{"issue":"6","key":"9882_CR8","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1038\/nbt.3238","volume":"33","author":"K Berlin","year":"2015","unstructured":"Berlin K, Koren S, Chin CS et al (2015) Assembling large genomes with single-molecule sequencing and locality-sensitive hashing. Nat Biotechnol 33(6):623. https:\/\/doi.org\/10.1038\/nbt.3238","journal-title":"Nat Biotechnol"},{"issue":"9","key":"9882_CR9","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1089\/cmb.2015.0220","volume":"23","author":"P Bonizzoni","year":"2016","unstructured":"Bonizzoni P, Dondi R, Klau GW et al (2016) On the minimum error correction problem for haplotype assembly in diploid and polyploid genomes. J Comput Biol 23(9):718\u2013736. https:\/\/doi.org\/10.1089\/cmb.2015.0220","journal-title":"J Comput Biol"},{"issue":"1","key":"9882_CR10","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1186\/s13015-019-0148-5","volume":"14","author":"C Boucher","year":"2019","unstructured":"Boucher C, Gagie T, Kuhnle A et al (2019) Prefix-free parsing for building big BWTs. Algorithms Mol Biol 14(1):13:1-13:15","journal-title":"Algorithms Mol Biol"},{"key":"9882_CR11","doi-asserted-by":"publisher","unstructured":"Boucher C, Cvacho O, Gagie T, et\u00a0al (2021) PFP compressed suffix trees. In: 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics, pp 60\u201372. https:\/\/doi.org\/10.1137\/1.9781611976472.5","DOI":"10.1137\/1.9781611976472.5"},{"key":"9882_CR12","unstructured":"Burrows M, Wheeler DJ (1994) A block-sorting lossless data compression algorithm. Tech. rep., Digital Systems Research Center"},{"issue":"17","key":"9882_CR13","doi-asserted-by":"publisher","first-page":"2927","DOI":"10.1093\/bioinformatics\/bty202","volume":"34","author":"J Chen","year":"2018","unstructured":"Chen J, Zhao Y, Sun Y (2018) De novo haplotype reconstruction in viral quasispecies using paired-end read guided path finding. Bioinformatics 34(17):2927\u20132935. https:\/\/doi.org\/10.1093\/bioinformatics\/bty202","journal-title":"Bioinformatics"},{"issue":"1","key":"9882_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/gb-2010-11-1-r1","volume":"22","author":"NC Chen","year":"2021","unstructured":"Chen NC, Solomon B, Mun T et al (2021) Reference flow: reducing reference bias using multiple population genomes. Genome Biol 22(1):1\u201317","journal-title":"Genome Biol"},{"issue":"12","key":"9882_CR15","doi-asserted-by":"publisher","first-page":"i201","DOI":"10.1093\/bioinformatics\/btw279","volume":"32","author":"R Chikhi","year":"2016","unstructured":"Chikhi R, Limasset A, Medvedev P (2016) Compacting de Bruijn graphs from sequencing data quickly and in low memory. Bioinformatics 32(12):i201\u2013i208. https:\/\/doi.org\/10.1093\/bioinformatics\/btw279","journal-title":"Bioinformatics"},{"issue":"7831","key":"9882_CR16","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1038\/s41586-020-2859-7","volume":"586","author":"A Choudhury","year":"2020","unstructured":"Choudhury A, Aron S, Botigu\u00e9 LR et al (2020) High-depth African genomes inform human migration and health. Nature 586(7831):741\u2013748. https:\/\/doi.org\/10.1038\/s41586-020-2859-7","journal-title":"Nature"},{"issue":"7831","key":"9882_CR17","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1038\/s41586-020-2859-7","volume":"586","author":"A Choudhury","year":"2020","unstructured":"Choudhury A, Aron S, Botigu\u00e9 LR et al (2020) High-depth African genomes inform human migration and health. Nature 586(7831):741\u2013748","journal-title":"Nature"},{"key":"9882_CR18","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.is.2014.06.002","volume":"47","author":"F Claude","year":"2015","unstructured":"Claude F, Navarro G, Ord\u00f3\u00f1ez A (2015) The wavelet matrix: an efficient wavelet tree for large alphabets. Inf Syst 47:15\u201332. https:\/\/doi.org\/10.1016\/j.is.2014.06.002","journal-title":"Inf Syst"},{"key":"9882_CR19","unstructured":"Cobas D, Gagie T, Navarro G (2021) A Fast and Small Subsampled R-Index. In: Proc. of the 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, pp 13:1\u201313:16"},{"issue":"11","key":"9882_CR20","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1038\/nbt.2023","volume":"29","author":"PE Compeau","year":"2011","unstructured":"Compeau PE, Pevzner PA, Tesler G (2011) How to apply de bruijn graphs to genome assembly. Nat Biotechnol 29(11):987\u2013991","journal-title":"Nat Biotechnol"},{"issue":"1","key":"9882_CR21","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1093\/bib\/bbw089","volume":"19","author":"Computational Pan-Genomics Consortium","year":"2018","unstructured":"Computational Pan-Genomics Consortium (2018) Computational pan-genomics: status, promises and challenges. Brief Bioinform 19(1):118\u2013135. https:\/\/doi.org\/10.1093\/bib\/bbw089","journal-title":"Brief Bioinform"},{"issue":"15","key":"9882_CR22","doi-asserted-by":"publisher","first-page":"2156","DOI":"10.1093\/bioinformatics\/btr330","volume":"27","author":"P Danecek","year":"2011","unstructured":"Danecek P, Auton A, Abecasis G et al (2011) The variant call format and VCFtools. Bioinformatics 27(15):2156\u20132158. https:\/\/doi.org\/10.1093\/bioinformatics\/btr330","journal-title":"Bioinformatics"},{"key":"9882_CR23","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-018-2436-3","author":"L Denti","year":"2018","unstructured":"Denti L, Rizzi R, Beretta S et al (2018) ASGAL: aligning RNA-Seq data to a splicing graph to detect novel alternative splicing events. BMC Bioinform. https:\/\/doi.org\/10.1186\/s12859-018-2436-3","journal-title":"BMC Bioinform"},{"key":"9882_CR24","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.isci.2019.07.011","volume":"18","author":"L Denti","year":"2019","unstructured":"Denti L, Previtali M, Bernardini G et al (2019) MALVA: genotyping by mapping-free ALlele detection of known VAriants. iScience 18:20\u201327. https:\/\/doi.org\/10.1016\/j.isci.2019.07.011","journal-title":"iScience"},{"key":"9882_CR25","volume-title":"Graph theory. Graduate texts in mathematics","author":"R Diestel","year":"2005","unstructured":"Diestel R (2005) Graph theory. Graduate texts in mathematics, 3rd edn. Springer-Verlag, Heidelberg","edition":"3"},{"key":"9882_CR26","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 et al (2015) Improved genome inference in the MHC using a population reference graph. Nat Genet 47:682\u2013688. https:\/\/doi.org\/10.1038\/ng.3257","journal-title":"Nat Genet"},{"issue":"9","key":"9882_CR27","doi-asserted-by":"publisher","first-page":"1266","DOI":"10.1093\/bioinformatics\/btu014","volume":"30","author":"R Durbin","year":"2014","unstructured":"Durbin R (2014) Efficient haplotype matching and storage using the Positional Burrows-Wheeler transform (PBWT). Bioinformatics 30(9):1266\u20131272. https:\/\/doi.org\/10.1093\/bioinformatics\/btu014","journal-title":"Bioinformatics"},{"key":"9882_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-27659-9","volume-title":"Multicriteria optimization","author":"M Ehrgott","year":"2005","unstructured":"Ehrgott M (2005) Multicriteria optimization, vol 491. Springer, Berlin. https:\/\/doi.org\/10.1007\/3-540-27659-9"},{"issue":"21","key":"9882_CR29","doi-asserted-by":"publisher","first-page":"5139","DOI":"10.1093\/bioinformatics\/btaa640","volume":"36","author":"JM Eizenga","year":"2020","unstructured":"Eizenga JM, Novak AM, Kobayashi E et al (2020) Efficient dynamic variation graphs. Bioinformatics 36(21):5139\u20135144. https:\/\/doi.org\/10.1093\/bioinformatics\/btaa640","journal-title":"Bioinformatics"},{"issue":"1","key":"9882_CR30","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1146\/annurev-genom-120219-080406","volume":"21","author":"JM Eizenga","year":"2020","unstructured":"Eizenga JM, Novak AM, Sibbesen JA et al (2020) Pangenome graphs. Annu Rev Genomics Hum Genet 21(1):139\u2013162. https:\/\/doi.org\/10.1146\/annurev-genom-120219-080406","journal-title":"Annu Rev Genomics Hum Genet"},{"key":"9882_CR31","doi-asserted-by":"publisher","unstructured":"Eizenga JM, Lorig-Roach R, Meredith MM, et\u00a0al (2021) Walk-preserving transformation of overlapped sequence graphs into blunt sequence graphs with GetBlunted. In: Connecting with Computability - 17th Conference on Computability in Europe, CiE 2021, Proceedings. Springer, LNCS, pp 169\u2013177. https:\/\/doi.org\/10.1007\/978-3-030-80049-9_15","DOI":"10.1007\/978-3-030-80049-9_15"},{"issue":"4","key":"9882_CR32","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina P, Manzini G (2005) Indexing compressed text. J ACM 52(4):552\u2013581. https:\/\/doi.org\/10.1145\/1082036.1082039","journal-title":"J ACM"},{"issue":"1","key":"9882_CR33","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/1613676.1613680","volume":"57","author":"P Ferragina","year":"2009","unstructured":"Ferragina P, Luccio F, Manzini G et al (2009) Compressing and indexing labeled trees, with applications. J ACM 57(1):4:1-4:33. https:\/\/doi.org\/10.1145\/1613676.1613680","journal-title":"J ACM"},{"issue":"4","key":"9882_CR34","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1093\/bioinformatics\/btaa782","volume":"37","author":"B Freire","year":"2020","unstructured":"Freire B, Ladra S, Param\u00e1 JR et al (2020) Inference of viral quasispecies with a paired de Bruijn graph. Bioinformatics 37(4):473\u2013481. https:\/\/doi.org\/10.1093\/bioinformatics\/btaa782","journal-title":"Bioinformatics"},{"key":"9882_CR35","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-021-02426-8","author":"A Fritz","year":"2021","unstructured":"Fritz A, Bremges A, Deng ZL et al (2021) Haploflow: strain-resolved de novo assembly of viral genomes. Genome Biol. https:\/\/doi.org\/10.1186\/s13059-021-02426-8","journal-title":"Genome Biol"},{"key":"9882_CR36","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.tcs.2017.06.016","volume":"698","author":"T Gagie","year":"2017","unstructured":"Gagie T, Manzini G, Sir\u00e9n J (2017) Wheeler graphs: a framework for BWT-based data structures. Theoret Comput Sci 698:67\u201378. https:\/\/doi.org\/10.1016\/j.tcs.2017.06.016","journal-title":"Theoret Comput Sci"},{"key":"9882_CR37","doi-asserted-by":"publisher","DOI":"10.1145\/3375890","author":"T Gagie","year":"2020","unstructured":"Gagie T, Navarro G, Prezza N (2020) Fully functional suffix trees and optimal text searching in BWT-runs bounded space. J ACM JACM. https:\/\/doi.org\/10.1145\/3375890","journal-title":"J ACM JACM"},{"key":"9882_CR38","doi-asserted-by":"publisher","unstructured":"Garrison E (2019) Graphical pangenomics. Thesis, University of Cambridge. https:\/\/doi.org\/10.17863\/CAM.41621, https:\/\/www.repository.cam.ac.uk\/handle\/1810\/294516","DOI":"10.17863\/CAM.41621"},{"key":"9882_CR39","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1038\/nbt.4227","volume":"36","author":"E Garrison","year":"2018","unstructured":"Garrison E, Sir\u00e9n J, Novak A et al (2018) Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nat Biotechnol 36:875\u2013879. https:\/\/doi.org\/10.1038\/nbt.4227","journal-title":"Nat Biotechnol"},{"key":"9882_CR40","unstructured":"Garrison E, et\u00a0al (2019) seqwish: A variation graph inducer. https:\/\/github.com\/ekg\/seqwish"},{"issue":"5979","key":"9882_CR41","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1126\/science.1188021","volume":"328","author":"RE Green","year":"2010","unstructured":"Green RE, Krause J, Briggs AW et al (2010) A draft sequence of the Neandertal Genome. Science 328(5979):710\u2013722. https:\/\/doi.org\/10.1126\/science.1188021","journal-title":"Science"},{"key":"9882_CR42","unstructured":"Grunwald P (2004) A tutorial introduction to the minimum description length principle. arXiv:math\/0406077http:\/\/arxiv.org\/abs\/math\/0406077"},{"key":"9882_CR43","doi-asserted-by":"publisher","unstructured":"Guarracino A, Heumos S, Nahnsen S, et\u00a0al (2021) ODGI: understanding pangenome graphs. bioRxiv:2021.11.10.467921. https:\/\/doi.org\/10.1101\/2021.11.10.467921","DOI":"10.1101\/2021.11.10.467921"},{"key":"9882_CR44","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 (1997) Algorithms on strings, trees and sequences: computer science and computational biology. Cambridge University Press, Cambridge"},{"issue":"13","key":"9882_CR45","doi-asserted-by":"publisher","first-page":"i361","DOI":"10.1093\/bioinformatics\/btt215","volume":"29","author":"L Huang","year":"2013","unstructured":"Huang L, Popic V, Batzoglou S (2013) Short read alignment with populations of genomes. Bioinformatics 29(13):i361\u2013i370. https:\/\/doi.org\/10.1093\/bioinformatics\/btt215","journal-title":"Bioinformatics"},{"key":"9882_CR46","doi-asserted-by":"publisher","unstructured":"Jain C, Dilthey A, Misra S, et\u00a0al (2019) Accelerating sequence alignment to graphs. bioRxiv:2019.05.27.651638. https:\/\/doi.org\/10.1101\/651638","DOI":"10.1101\/651638"},{"issue":"Supplement-1","key":"9882_CR47","doi-asserted-by":"publisher","first-page":"i460","DOI":"10.1093\/bioinformatics\/btab302","volume":"37","author":"C Jain","year":"2021","unstructured":"Jain C, Tavakoli N, Aluru S (2021) A variant selection framework for genome graphs. Bioinformatics 37(Supplement-1):i460\u2013i467. https:\/\/doi.org\/10.1093\/bioinformatics\/btab302","journal-title":"Bioinformatics"},{"key":"9882_CR48","doi-asserted-by":"publisher","DOI":"10.1186\/s13742-015-0097-y","author":"L Kaplinski","year":"2015","unstructured":"Kaplinski L, Lepamets M, Remm M (2015) GenomeTester4: a toolkit for performing basic set operations - union, intersection and complement on k-mer lists. GigaScience. https:\/\/doi.org\/10.1186\/s13742-015-0097-y","journal-title":"GigaScience"},{"key":"9882_CR49","doi-asserted-by":"publisher","unstructured":"Karasikov M, Mustafa H, Danciu D, et\u00a0al (2020) Metagraph: Indexing and analysing nucleotide archives at petabase-scale. bioRxiv:2020.10.01.322164. https:\/\/doi.org\/10.1101\/2020.10.01.322164","DOI":"10.1101\/2020.10.01.322164"},{"key":"9882_CR50","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen J, Manzini G, Puglisi S (2009) Permuted longest-common-prefix array. In: Proc. of the 20th Annual Symposium on Combinatorial Pattern Matching CPM 2009, pp 181\u2013192","DOI":"10.1007\/978-3-642-02441-2_17"},{"key":"9882_CR51","doi-asserted-by":"publisher","DOI":"10.1093\/bioadv\/vbab005","author":"P Khorsand","year":"2021","unstructured":"Khorsand P, Denti L et al (2021) Comparative genome analysis using sample-specific string detection in accurate long reads. Bioinf Adv. https:\/\/doi.org\/10.1093\/bioadv\/vbab005","journal-title":"Bioinf Adv"},{"issue":"17","key":"9882_CR52","doi-asserted-by":"publisher","first-page":"2759","DOI":"10.1093\/bioinformatics\/btx304","volume":"33","author":"M Kokot","year":"2017","unstructured":"Kokot M, D\u0142ugosz M, Deorowicz S (2017) KMC 3: counting and manipulating k-mer statistics. Bioinformatics 33(17):2759\u20132761. https:\/\/doi.org\/10.1093\/bioinformatics\/btx304","journal-title":"Bioinformatics"},{"key":"9882_CR53","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2012.02.006","volume":"483","author":"S Kreft","year":"2013","unstructured":"Kreft S, Navarro G (2013) On compressing and indexing repetitive sequences. Theoret Comput Sci 483:115\u2013133. https:\/\/doi.org\/10.1016\/j.tcs.2012.02.006","journal-title":"Theoret Comput Sci"},{"key":"9882_CR54","first-page":"139","volume-title":"String processing and information retrieval","author":"G Kucherov","year":"2014","unstructured":"Kucherov G, Tsur D (2014) Improved filters for the approximate suffix-prefix overlap problem. In: Moura E, Crochemore M (eds) String processing and information retrieval. Springer International Publishing, Cham, pp 139\u2013148"},{"issue":"4","key":"9882_CR55","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1089\/cmb.2019.0309","volume":"27","author":"A Kuhnle","year":"2020","unstructured":"Kuhnle A, Mun T, Boucher C et al (2020) Efficient construction of a complete index for pan-genomics read alignment. J Comput Biol 27(4):500\u2013513. https:\/\/doi.org\/10.1089\/cmb.2019.0309","journal-title":"J Comput Biol"},{"issue":"3","key":"9882_CR56","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1093\/bioinformatics\/18.3.452","volume":"18","author":"C Lee","year":"2002","unstructured":"Lee C, Grasso C, Sharlow MF (2002) Multiple sequence alignment using partial order graphs. Bioinformatics 18(3):452\u2013464. https:\/\/doi.org\/10.1093\/bioinformatics\/18.3.452","journal-title":"Bioinformatics"},{"key":"9882_CR57","unstructured":"Li H (2013) Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. arXiv:1303.3997"},{"issue":"18","key":"9882_CR58","doi-asserted-by":"publisher","first-page":"3094","DOI":"10.1093\/bioinformatics\/bty191","volume":"34","author":"H Li","year":"2018","unstructured":"Li H (2018) Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics 34(18):3094\u20133100. https:\/\/doi.org\/10.1093\/bioinformatics\/bty191","journal-title":"Bioinformatics"},{"key":"9882_CR59","unstructured":"Li H, Chin J, Durbin R, et\u00a0al (2017) GFA: Graphical Fragment Assembly (GFA) Format Specification. http:\/\/gfa-spec.github.io\/GFA-spec\/"},{"key":"9882_CR60","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-020-02168-z","author":"H Li","year":"2020","unstructured":"Li H, Feng X, Chu C (2020) The design and construction of reference pangenome graphs with minigraph. Genome Biol. https:\/\/doi.org\/10.1186\/s13059-020-02168-z","journal-title":"Genome Biol"},{"key":"9882_CR61","doi-asserted-by":"crossref","unstructured":"Logsdon GA, Vollger MR, Eichler EE (2020) Long-read human genome sequencing and its applications. Nature Reviews Genetics 1\u201318","DOI":"10.1038\/s41576-020-0236-x"},{"key":"9882_CR62","doi-asserted-by":"publisher","DOI":"10.1186\/s12864-015-1481-9","author":"A Magi","year":"2015","unstructured":"Magi A, D\u2019Aurizio R, Palombo F et al (2015) Characterization and identification of hidden rare variants in the human genome. BMC Genomics. https:\/\/doi.org\/10.1186\/s12864-015-1481-9","journal-title":"BMC Genomics"},{"issue":"1","key":"9882_CR63","first-page":"40","volume":"12","author":"V M\u00e4kinen","year":"2005","unstructured":"M\u00e4kinen V, Navarro G (2005) Succinct suffix arrays based on run-length encoding. Nordic J Comput 12(1):40\u201366","journal-title":"Nordic J Comput"},{"key":"9882_CR64","unstructured":"M\u00e4kinen V, Cazaux B, Equi M, et\u00a0al (2020) Linear time construction of indexable founder block graphs. arXiv:2005.09342"},{"key":"9882_CR65","unstructured":"Malhotra R, Wu MMS, Rodrigo A, et\u00a0al (2016) Maximum likelihood de novo reconstruction of viral populations using paired end sequencing data. arXiv:1502.04239"},{"issue":"5","key":"9882_CR66","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber U, Myers G (1993) Suffix arrays: a new method for on-line string searches. SIAM J Comput 22(5):935\u2013948","journal-title":"SIAM J Comput"},{"issue":"3","key":"9882_CR67","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/j.tcs.2007.07.014","volume":"387","author":"S Mantaci","year":"2007","unstructured":"Mantaci S, Restivo A, Rosone G et al (2007) An extension of the Burrows-Wheeler Transform. Theoret Comput Sci 387(3):298\u2013312. https:\/\/doi.org\/10.1016\/j.tcs.2007.07.014","journal-title":"Theoret Comput Sci"},{"key":"9882_CR68","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1186\/s13015-016-0075-7","volume":"11","author":"G Miclotte","year":"2016","unstructured":"Miclotte G, Heydari M, Demeester P et al (2016) Jabba: hybrid error correction for long sequencing reads. Algorithms Mol Biol 11:10. https:\/\/doi.org\/10.1186\/s13015-016-0075-7","journal-title":"Algorithms Mol Biol"},{"issue":"22","key":"9882_CR69","doi-asserted-by":"publisher","first-page":"3492","DOI":"10.1093\/bioinformatics\/btw397","volume":"32","author":"H Mohamadi","year":"2016","unstructured":"Mohamadi H, Chu J, Vandervalk BP et al (2016) ntHash: recursive nucleotide hashing. Bioinformatics 32(22):3492\u20133494. https:\/\/doi.org\/10.1093\/bioinformatics\/btw397","journal-title":"Bioinformatics"},{"issue":"4","key":"9882_CR70","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1089\/cmb.2019.0316","volume":"27","author":"T Mun","year":"2020","unstructured":"Mun T, Kuhnle A, Boucher C et al (2020) Matching reads to many genomes with the r-index. J Comput Biol 27(4):514\u2013518. https:\/\/doi.org\/10.1089\/cmb.2019.0316","journal-title":"J Comput Biol"},{"issue":"Suppl.\u00a02","key":"9882_CR71","doi-asserted-by":"publisher","first-page":"ii79","DOI":"10.1093\/bioinformatics\/bti1114","volume":"21","author":"E Myers","year":"2005","unstructured":"Myers E (2005) The fragment assembly string graph. Bioinformatics 21(Suppl.\u00a02):ii79\u2013ii85. https:\/\/doi.org\/10.1093\/bioinformatics\/bti1114","journal-title":"Bioinformatics"},{"issue":"3","key":"9882_CR72","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 et al (2010) Storage and retrieval of highly repetitive sequence collections. J Comput Biol 17(3):281\u2013308. https:\/\/doi.org\/10.1089\/cmb.2009.0169","journal-title":"J Comput Biol"},{"key":"9882_CR73","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-019-2821-6","author":"A Naseri","year":"2019","unstructured":"Naseri A, Zhi D, Zhang S (2019) Multi-allelic positional Burrows-Wheeler transform. BMC Bioinform. https:\/\/doi.org\/10.1186\/s12859-019-2821-6","journal-title":"BMC Bioinform"},{"key":"9882_CR74","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1186\/s13015-017-0109-9","volume":"12","author":"A Novak","year":"2017","unstructured":"Novak A, Garrison E, Paten B (2017) A graph extension of the positional Burrows-Wheeler transform and its applications. Algorithms Mol Biol 12:18. https:\/\/doi.org\/10.1186\/s13015-017-0109-9","journal-title":"Algorithms Mol Biol"},{"issue":"9","key":"9882_CR75","doi-asserted-by":"publisher","first-page":"1512","DOI":"10.1101\/gr.123356.111","volume":"21","author":"B Paten","year":"2011","unstructured":"Paten B, Earl D, Nguyen N et al (2011) Cactus: algorithms for genome multiple sequence alignment. Genome Res 21(9):1512\u20131528. https:\/\/doi.org\/10.1101\/gr.123356.111","journal-title":"Genome Res"},{"issue":"5","key":"9882_CR76","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1101\/gr.214155.116","volume":"27","author":"B Paten","year":"2017","unstructured":"Paten B, Novak A, Eizenga J et al (2017) Genome graphs and the evolution of genome inference. Genome Res 27(5):665\u2013676. https:\/\/doi.org\/10.1101\/gr.214155.116","journal-title":"Genome Res"},{"issue":"7","key":"9882_CR77","doi-asserted-by":"publisher","first-page":"1986","DOI":"10.1007\/s00453-017-0327-z","volume":"80","author":"A Policriti","year":"2017","unstructured":"Policriti A, Prezza N (2017) LZ77 computation based on the run-length encoded BWT. Algorithmica 80(7):1986\u20132011. https:\/\/doi.org\/10.1007\/s00453-017-0327-z","journal-title":"Algorithmica"},{"issue":"7624","key":"9882_CR78","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1038\/538161a","volume":"538","author":"AB Popejoy","year":"2016","unstructured":"Popejoy AB, Fullerton SM (2016) Genomics is failing on diversity. Nature 538(7624):161\u2013164. https:\/\/doi.org\/10.1038\/538161a","journal-title":"Nature"},{"issue":"2","key":"9882_CR79","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1038\/s41588-018-0316-4","volume":"51","author":"G Rakocevic","year":"2019","unstructured":"Rakocevic G, Semenyuk V, Lee WP et al (2019) Fast and accurate genomic analyses using genome graphs. Nat Genet 51(2):354\u2013362. https:\/\/doi.org\/10.1038\/s41588-018-0316-4","journal-title":"Nat Genet"},{"issue":"19","key":"9882_CR80","doi-asserted-by":"publisher","first-page":"3599","DOI":"10.1093\/bioinformatics\/btz162","volume":"35","author":"M Rautiainen","year":"2019","unstructured":"Rautiainen M, M\u00e4kinen V, Marschall T (2019) Bit-parallel sequence-to-graph alignment. Bioinformatics 35(19):3599\u20133607. https:\/\/doi.org\/10.1093\/bioinformatics\/btz162","journal-title":"Bioinformatics"},{"key":"9882_CR81","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/s40484-019-0181-x","volume":"7","author":"R Rizzi","year":"2019","unstructured":"Rizzi R, Beretta S, Patterson M et al (2019) Overlap graphs and de Bruijn graphs: data structures for de novo genome assembly in the big data era. Quantit Biol 7:278\u2013292. https:\/\/doi.org\/10.1007\/s40484-019-0181-x","journal-title":"Quantit Biol"},{"key":"9882_CR82","doi-asserted-by":"crossref","unstructured":"Rossi M, Oliva M, Langmead B, et\u00a0al (2021) MONI: A pangenomics index for finding MEMs. In: Proc. of the 25th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2021","DOI":"10.1101\/2021.07.06.451246"},{"issue":"5","key":"9882_CR83","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1101\/gr.213611.116","volume":"27","author":"VA Schneider","year":"2017","unstructured":"Schneider VA, Graves-Lindsay T, Howe K et al (2017) Evaluation of grch38 and de novo haploid genome assemblies demonstrates the enduring quality of the reference assembly. Genome Res 27(5):849\u2013864","journal-title":"Genome Res"},{"key":"9882_CR84","doi-asserted-by":"publisher","unstructured":"Shchur V, Ziganurova L, Durbin R (2019) Fast and scalable genome-wide inference of local tree topologies from large number of haplotypes based on tree consistent PBWT data structure. bioRxiv:2019.02.06.542035. https:\/\/doi.org\/10.1101\/542035","DOI":"10.1101\/542035"},{"issue":"1","key":"9882_CR85","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1038\/s41588-018-0273-y","volume":"51","author":"RM Sherman","year":"2019","unstructured":"Sherman RM, Forman J, Antonescu V et al (2019) Assembly of a pan-genome from deep sequencing of 910 humans of african descent. Nat Genet 51(1):30\u201335","journal-title":"Nat Genet"},{"key":"9882_CR86","doi-asserted-by":"publisher","unstructured":"Shi F (1996) Suffix arrays for multiple strings: a method for on-line multiple string searches. In: Concurrency and Parallelism, Programming, Networking, and Security, LNCS, vol 1179. Springer, pp 11\u201322. https:\/\/doi.org\/10.1007\/BFb0027775","DOI":"10.1007\/BFb0027775"},{"issue":"7","key":"9882_CR87","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1038\/s41588-018-0145-5","volume":"50","author":"JA Sibbesen","year":"2018","unstructured":"Sibbesen JA, Maretty L et al (2018) Accurate genotyping across variant classes and lengths using variant graphs. Nat Genetic 50(7):1054\u20131059. https:\/\/doi.org\/10.1038\/s41588-018-0145-5","journal-title":"Nat Genetic"},{"key":"9882_CR88","doi-asserted-by":"publisher","unstructured":"Sibbesen JA, Eizenga JM, Novak AM, et\u00a0al (2021) Haplotype-aware pantranscriptome analyses using spliced pangenome graphs. bioRxiv:2021.03.26.437240. https:\/\/doi.org\/10.1101\/2021.03.26.437240","DOI":"10.1101\/2021.03.26.437240"},{"key":"9882_CR89","doi-asserted-by":"publisher","unstructured":"Sir\u00e9n J (2017) Indexing variation graphs. In: 2017 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX). Proceedings, SIAM, pp 13\u201327. https:\/\/doi.org\/10.1137\/1.9781611974768.2","DOI":"10.1137\/1.9781611974768.2"},{"key":"9882_CR90","doi-asserted-by":"publisher","unstructured":"Sir\u00e9n J, Monlong J, Chang X, et\u00a0al (2021) Genotyping common, large structural variations in 5,202 genomes using pangenomes, the Giraffe mapper, and the vg toolkit. bioRxiv:2020.12.04.412486. https:\/\/doi.org\/10.1101\/2020.12.04.412486","DOI":"10.1101\/2020.12.04.412486"},{"issue":"2","key":"9882_CR91","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 (2014) Indexing graphs for path queries with applications in genome research. IEEE\/ACM Trans Comput Biol Bioinf 11(2):375\u2013388. https:\/\/doi.org\/10.1109\/TCBB.2013.2297101","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"2","key":"9882_CR92","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1093\/bioinformatics\/btz575","volume":"36","author":"J Sir\u00e9n","year":"2020","unstructured":"Sir\u00e9n J, Garrison E, Novak AM et al (2020) Haplotype-aware graph indexes. Bioinformatics 36(2):400\u2013407. https:\/\/doi.org\/10.1093\/bioinformatics\/btz575","journal-title":"Bioinformatics"},{"issue":"1","key":"9882_CR93","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.ajhg.2018.11.014","volume":"104","author":"Z Stark","year":"2019","unstructured":"Stark Z, Dolman L, Manolio TA et al (2019) Integrating genomics into healthcare: a global responsibility. Am J Human Genetics 104(1):13\u201320","journal-title":"Am J Human Genetics"},{"issue":"9","key":"9882_CR94","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1038\/s41588-018-0182-0","volume":"50","author":"S Sun","year":"2018","unstructured":"Sun S, Zhou Y, Chen J et al (2018) Extensive intraspecific gene order and gene structural variations between Mo17 and other maize genomes. Nat Genet 50(9):1289\u20131295. https:\/\/doi.org\/10.1038\/s41588-018-0182-0","journal-title":"Nat Genet"},{"issue":"39","key":"9882_CR95","doi-asserted-by":"publisher","first-page":"13950","DOI":"10.1073\/pnas.0506758102","volume":"102","author":"H Tettelin","year":"2005","unstructured":"Tettelin H et al (2005) Genome analysis of multiple pathogenic isolates of streptococcus agalactiae: implications for the microbial \u201cpan-genome\u2019\u2019. Proc Natl Acad Sci 102(39):13950\u201313955. https:\/\/doi.org\/10.1073\/pnas.0506758102","journal-title":"Proc Natl Acad Sci"},{"issue":"7571","key":"9882_CR96","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 (2015) A global reference for human genetic variation. Nature 526(7571):68\u201374. https:\/\/doi.org\/10.1038\/nature15393","journal-title":"Nature"},{"issue":"3","key":"9882_CR97","doi-asserted-by":"publisher","first-page":"e1003,515","DOI":"10.1371\/journal.pcbi.1003515","volume":"10","author":"A T\u00f6pfer","year":"2014","unstructured":"T\u00f6pfer A, Marschall T, Bull R et al (2014) Viral quasispecies assembly via maximal clique enumeration. PLoS Comput Biol 10(3):e1003,515. https:\/\/doi.org\/10.1371\/journal.pcbi.1003515","journal-title":"PLoS Comput Biol"},{"key":"9882_CR98","doi-asserted-by":"publisher","unstructured":"Ukkonen E (2002) Finding founder sequences from a set of recombinants. In: Algorithms in Bioinformatics, WABI 2002. Springer, pp 277\u2013286. https:\/\/doi.org\/10.1007\/3-540-45784-4_21","DOI":"10.1007\/3-540-45784-4_21"},{"key":"9882_CR99","doi-asserted-by":"publisher","unstructured":"V\u00e4lim\u00e4lki N, Ladra S, M\u00e4lkinen V (2010) Approximate all-pairs suffix\/prefix overlaps. In: Combinatorial Pattern Matching, CPM 2010, LNCS, vol 6129. Springer, pp 76\u201387. https:\/\/doi.org\/10.1007\/978-3-642-13509-5_8","DOI":"10.1007\/978-3-642-13509-5_8"},{"issue":"1","key":"9882_CR100","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1186\/s12859-015-0533-0","volume":"16","author":"M Vyverman","year":"2015","unstructured":"Vyverman M, De Baets B, Fack V et al (2015) A long fragment aligner called ALFALFA. BMC Bioinform 16(1):159. https:\/\/doi.org\/10.1186\/s12859-015-0533-0","journal-title":"BMC Bioinform"},{"issue":"6","key":"9882_CR101","doi-asserted-by":"publisher","first-page":"101149","DOI":"10.1016\/j.isci.2020.101149","volume":"23","author":"L Williams","year":"2020","unstructured":"Williams L, Mumey B (2020) Maximal perfect haplotype blocks with wildcards. iScience 23(6):101149. https:\/\/doi.org\/10.1016\/j.isci.2020.101149","journal-title":"iScience"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-022-09882-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-022-09882-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-022-09882-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,2]],"date-time":"2022-08-02T13:11:41Z","timestamp":1659445901000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-022-09882-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3]]},"references-count":101,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["9882"],"URL":"https:\/\/doi.org\/10.1007\/s11047-022-09882-6","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3]]},"assertion":[{"value":"14 February 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 March 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2022","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Missing Open Access funding information has been added in the Funding Note","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}