{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T01:45:45Z","timestamp":1742953545363,"version":"3.40.3"},"publisher-location":"Cham","reference-count":64,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319639628"},{"type":"electronic","value":"9783319639628"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-63962-8_53-1","type":"book-chapter","created":{"date-parts":[[2018,2,27]],"date-time":"2018-02-27T06:33:18Z","timestamp":1519713198000},"page":"1-7","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Compressed Indexes for Repetitive Textual Datasets"],"prefix":"10.1007","author":[{"given":"Travis","family":"Gagie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,2,10]]},"reference":[{"key":"53-1_CR1","doi-asserted-by":"crossref","unstructured":"Abeliuk A, C\u00e1novas R, Navarro G (2013) Practical compressed suffix trees. Algorithms 6(2):319\u2013351","DOI":"10.3390\/a6020319"},{"key":"53-1_CR2","unstructured":"Belazzougui D, Cunial F (2017) Representing the suffix tree with the CDAWG. In: Proceedings of the 28th symposium on combinatorial pattern matching (CPM), pp 7:1\u20137:13"},{"key":"53-1_CR3","doi-asserted-by":"crossref","unstructured":"Belazzougui D, Cunial F, Gagie T, Prezza N, Raffinot M (2015) Composite repetition-aware data structures. In: Proceedings of the 26th symposium on combinatorial pattern matching (CPM), pp 26\u201339","DOI":"10.1007\/978-3-319-19929-0_3"},{"key":"53-1_CR4","doi-asserted-by":"crossref","unstructured":"Belazzougui D, Cunial F, Gagie T, Prezza N, Raffinot M (2017) Flexible indexing of repetitive collections. In: Proceedings of the 13th conference on computability in Europe (CiE), pp 162\u2013174","DOI":"10.1007\/978-3-319-58741-7_17"},{"key":"53-1_CR5","unstructured":"Bille P, Ettienne MB, G\u00f8rtz IL, Vildh\u00f8j HW (2017) Time-space trade-offs for Lempel-Ziv compressed indexing. In: Proceedings of the 28th symposium on combinatorial pattern matching (CPM), pp 16:1\u201316:17"},{"key":"53-1_CR6","doi-asserted-by":"crossref","unstructured":"Blumer A, Blumer J, Haussler D, McConnell RM, Ehrenfeucht A (1987) Complete inverted files for efficient text retrieval and analysis. J ACM 34(3):578\u2013595","DOI":"10.1145\/28869.28873"},{"key":"53-1_CR7","doi-asserted-by":"crossref","unstructured":"Bowe A, Onodera T, Sadakane K, Shibuya T (2012) Succinct de Bruijn graphs. In: Proceedings of the 12th workshop on algorithms in bioinformatics (WABI), pp 225\u2013235","DOI":"10.1007\/978-3-642-33122-0_18"},{"key":"53-1_CR8","doi-asserted-by":"crossref","unstructured":"Claude F, Navarro G (2011) Self-indexed grammar-based compression. Fundamenta Informaticae 111(3):313\u2013337","DOI":"10.3233\/FI-2011-565"},{"key":"53-1_CR9","doi-asserted-by":"crossref","unstructured":"Claude F, Navarro G (2012) Improved grammar-based compressed indexes. In: Proceedings of the 19th symposium on string processing and information retrieval (SPIRE), pp 180\u2013192","DOI":"10.1007\/978-3-642-34109-0_19"},{"key":"53-1_CR10","doi-asserted-by":"crossref","unstructured":"Claude F, Fari\u00f1a A, Mart\u00ednez-Prieto MA, Navarro G (2016) Universal indexes for highly repetitive document collections. Inf Syst 61:1\u201323","DOI":"10.1016\/j.is.2016.04.002"},{"key":"53-1_CR11","doi-asserted-by":"crossref","unstructured":"Danek A, Deorowicz S, Grabowski S (2014) Indexes of large genome collections on a PC. PLoS One 9(10):e109384","DOI":"10.1371\/journal.pone.0109384"},{"key":"53-1_CR12","doi-asserted-by":"crossref","unstructured":"Dilthey A, Cox C, Iqbal Z, Nelson MR, McVean G (2015) Improved genome inference in the MHC using a population reference graph. Nat Genet 47(6):682\u2013688","DOI":"10.1038\/ng.3257"},{"key":"53-1_CR13","doi-asserted-by":"crossref","unstructured":"Do HH, Jansson J, Sadakane K, Sung W (2014) Fast relative Lempel-Ziv self-index for similar sequences. Theor Comput Sci 532:14\u201330","DOI":"10.1016\/j.tcs.2013.07.024"},{"key":"53-1_CR14","doi-asserted-by":"crossref","unstructured":"Eggertsson HP et al (2017) Graphtyper enables population-scale genotyping using pangenome graphs. Nat Genet 49(11):1654\u20131660","DOI":"10.1038\/ng.3964"},{"key":"53-1_CR15","doi-asserted-by":"crossref","unstructured":"Ferrada H, Gagie T, Hirvola T, Puglisi SJ (2014) Hybrid indexes for repetitive datasets. Phil Trans R Soc A 372(2016):20130137","DOI":"10.1098\/rsta.2013.0137"},{"key":"53-1_CR16","doi-asserted-by":"crossref","unstructured":"Ferrada H, Kempa D, Puglisi SJ (2018) Hybrid indexing revisited. In: Proceedings of the 20th workshop on algorithm engineering and experiments (ALENEX), pp 1\u20138","DOI":"10.1137\/1.9781611975055.1"},{"key":"53-1_CR17","doi-asserted-by":"crossref","unstructured":"Ferragina P, Manzini G (2000) Opportunistic data structures with applications. In: Proceedings of the 41st symposium on foundations of computer science (FOCS), pp 390\u2013398","DOI":"10.1109\/SFCS.2000.892127"},{"key":"53-1_CR18","doi-asserted-by":"crossref","unstructured":"Ferragina P, Manzini G (2005) Indexing compressed text. J ACM 52(4):552\u2013581","DOI":"10.1145\/1082036.1082039"},{"key":"53-1_CR19","doi-asserted-by":"crossref","unstructured":"Ferragina P, Luccio F, Manzini G, Muthukrishnan S (2009) Compressing and indexing labeled trees, with applications. J ACM 57(1):4:1\u20134:33","DOI":"10.1145\/1613676.1613680"},{"key":"53-1_CR20","doi-asserted-by":"crossref","unstructured":"Gagie T, Puglisi SJ (2015) Searching and indexing genomic databases via kernelization. Front Bioeng Biotechnol 3:12","DOI":"10.3389\/fbioe.2015.00012"},{"key":"53-1_CR21","doi-asserted-by":"crossref","unstructured":"Gagie T, Gawrychowski P, K\u00e4rkk\u00e4inen J, Nekrich Y, Puglisi SJ (2012) A faster grammar-based self-index. In: Proceedings of the 6th conference on language and automata theory and applications (LATA), pp 240\u2013251","DOI":"10.1007\/978-3-642-28332-1_21"},{"key":"53-1_CR22","doi-asserted-by":"crossref","unstructured":"Gagie T, Gawrychowski P, K\u00e4rkk\u00e4inen J, Nekrich Y, Puglisi SJ (2014) LZ77-based self-indexing with faster pattern matching. In: Proceedings of the 11th Latin American symposium on theoretical informatincs (LATIN), pp 731\u2013742","DOI":"10.1007\/978-3-642-54423-1_63"},{"key":"53-1_CR23","doi-asserted-by":"crossref","unstructured":"Gagie T, Manzini G, Sir\u00e9n J (2017a) Wheeler graphs: a framework for BWT-based data structures. Theor Comput Sci 698:67\u201378","DOI":"10.1016\/j.tcs.2017.06.016"},{"key":"53-1_CR24","doi-asserted-by":"crossref","unstructured":"Gagie T, Navarro G, Prezza N (2017b) Optimal-time text indexing in BWT-runs bounded space. Technical report 1705.10382, arXiv.org","DOI":"10.1137\/1.9781611975031.96"},{"key":"53-1_CR25","doi-asserted-by":"crossref","unstructured":"Gagie T, Navarro G, Prezza N (2018) Optimal-time text indexing in BWT-runs bounded space. In: Proceedings of the 29th symposium on discrete algorithms (SODA), pp 1459\u20131477","DOI":"10.1137\/1.9781611975031.96"},{"key":"53-1_CR26","doi-asserted-by":"crossref","unstructured":"Grossi R, Vitter JS (2000) Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract). In: Proceedings of the 32nd symposium on theory of computing (STOC), pp 397\u2013406","DOI":"10.1145\/335305.335351"},{"key":"53-1_CR27","doi-asserted-by":"crossref","unstructured":"Grossi R, Vitter JS (2005) Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J Comput 35(2):378\u2013407","DOI":"10.1137\/S0097539702402354"},{"key":"53-1_CR28","unstructured":"K\u00e4rkk\u00e4inen J, Ukkonen E (1996) Lempel-Ziv parsing and sublinear-size index structures for string matching. In: Proceedings of the 3rd South American workshop on string processing (WSP), pp 141\u2013155"},{"key":"53-1_CR29","unstructured":"Kempa D, Prezza N (2017) At the roots of dictionary compression: string attractors. In: Proceedings of the 50th symposium on theory of computing (STOC), 2018. CoRR abs\/1710.10964"},{"key":"53-1_CR30","doi-asserted-by":"crossref","unstructured":"Kreft S, Navarro G (2013) On compressing and indexing repetitive sequences. Theor Comput Sci 483:115\u2013133","DOI":"10.1016\/j.tcs.2012.02.006"},{"key":"53-1_CR31","doi-asserted-by":"crossref","unstructured":"Langmead B, Trapnell C, Pop M, Salzberg SL (2009) Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biol 10(3):R25","DOI":"10.1186\/gb-2009-10-3-r25"},{"key":"53-1_CR32","doi-asserted-by":"crossref","unstructured":"Li H, Durbin R (2009) Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics 25(14):1754\u20131760","DOI":"10.1093\/bioinformatics\/btp324"},{"key":"53-1_CR33","doi-asserted-by":"crossref","unstructured":"Maciuca S, del Ojo Elias C, McVean G, Iqbal Z (2016) A natural encoding of genetic variation in a Burrows-Wheeler transform to enable mapping and genome inference. In: Proceedings of the 16th workshop on algorithms in bioinformatics (WABI), pp 222\u2013233","DOI":"10.1007\/978-3-319-43681-4_18"},{"key":"53-1_CR34","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen V, Navarro G, Sir\u00e9n J, V\u00e4lim\u00e4ki N (2010) Storage and retrieval of highly repetitive sequence collections. J Comput Biol 17(3):281\u2013308","DOI":"10.1089\/cmb.2009.0169"},{"key":"53-1_CR35","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen V, Belazzougui D, Cunial F, Tomescu AI (2015) Genome-scale algorithm design: biological sequence analysis in the era of high-throughput sequencing. Cambridge University Press, Cambridge","DOI":"10.1017\/CBO9781139940023"},{"key":"53-1_CR36","doi-asserted-by":"crossref","unstructured":"Maruyama S, Nakahara M, Kishiue N, Sakamoto H (2013) ESP-index: a compressed index based on edit-sensitive parsing. J Discrete Algorithms 18:100\u2013112","DOI":"10.1016\/j.jda.2012.07.009"},{"key":"53-1_CR37","doi-asserted-by":"crossref","unstructured":"Na JC, Park H, Crochemore M, Holub J, Iliopoulos CS, Mouchard L, Park K (2013a) Suffix tree of alignment: an efficient index for similar data. In: Proceedings of the 24th international workshop on combinatorial algorithms (IWOCA), pp 337\u2013348","DOI":"10.1007\/978-3-642-45278-9_29"},{"key":"53-1_CR38","doi-asserted-by":"crossref","unstructured":"Na JC, Park H, Lee S, Hong M, Lecroq T, Mouchard L, Park K (2013b) Suffix array of alignment: a practical index for similar data. In: Proceedings of the 20th symposium on string processing and information retrieval (SPIRE), pp 243\u2013254","DOI":"10.1007\/978-3-319-02432-5_27"},{"key":"53-1_CR39","doi-asserted-by":"crossref","unstructured":"Na JC, Kim H, Park H, Lecroq T, L\u00e9onard M, Mouchard L, Park K (2016) FM-index of alignment: a compressed index for similar strings. Theor Comput Sci 638:159\u2013170","DOI":"10.1016\/j.tcs.2015.08.008"},{"key":"53-1_CR40","doi-asserted-by":"crossref","unstructured":"Na JC, Kim H, Min S, Park H, Lecroq T, L\u00e9onard M, Mouchard L, Park K (2018) FM-index of alignment with gaps. Theor Comput Sci. https:\/\/doi.org\/10.1016\/j.tcs.2017.02.020","DOI":"10.1016\/j.tcs.2017.02.020"},{"key":"53-1_CR41","doi-asserted-by":"crossref","unstructured":"Navarro G (2017) A self-index on block trees. In: Proceedings of the 17th symposium on string processing and information retrieval (SPIRE), pp 278\u2013289","DOI":"10.1007\/978-3-319-67428-5_24"},{"key":"53-1_CR42","unstructured":"Navarro G, Ord\u00f3\u00f1ez A (2016) Faster compressed suffix trees for repetitive text collections. J Exp Algorithmics 21(1):article 1.8"},{"key":"53-1_CR43","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316135228","volume-title":"Flexible pattern matching in strings \u2013 practical on-line search algorithms for texts and biological sequences","author":"G Navarro","year":"2002","unstructured":"Navarro G, Raffinot M (2002) Flexible pattern matching in strings \u2013 practical on-line search algorithms for texts and biological sequences. Cambridge University Press, Cambridge, UK"},{"key":"53-1_CR44","unstructured":"Nishimoto T, Tomohiro I, Inenaga S, Bannai H, Takeda M (2016) Dynamic index and LZ factorization in compressed space. In: Proceedings of the prague stringology conference (PSC), pp 158\u2013170"},{"key":"53-1_CR45","doi-asserted-by":"crossref","unstructured":"Novak AM, Garrison E, Paten B (2017a) A graph extension of the positional Burrows-Wheeler transform and its applications. Algorithms Mol Biol 12(1):18:1\u201318:12","DOI":"10.1186\/s13015-017-0109-9"},{"key":"53-1_CR46","unstructured":"Novak AM et al (2017b) Genome graphs. Technical report 101378, bioRxiv"},{"key":"53-1_CR47","volume-title":"Bioinformatics algorithms: sequence analysis, genome rearrangements, and phylogenetic reconstruction","author":"E Ohlebusch","year":"2013","unstructured":"Ohlebusch E (2013) Bioinformatics algorithms: sequence analysis, genome rearrangements, and phylogenetic reconstruction. Oldenbusch Verlag, Bremen, Germany"},{"issue":"5","key":"53-1_CR48","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1101\/gr.214155.116","volume":"27","author":"B Paten","year":"2017","unstructured":"Paten B, Novak AM, Eizenga JM, Garrison E (2017) Genome graphs and the evolution of genome inference. Genome Res 27(5):665\u2013676","journal-title":"Genome Res"},{"key":"53-1_CR49","doi-asserted-by":"crossref","unstructured":"Proch\u00e1zka P, Holub J (2014) Compressing similar biological sequences using FM-index. In: Proceedings of the data compression conference (DCC), pp 312\u2013321","DOI":"10.1109\/DCC.2014.47"},{"issue":"24","key":"53-1_CR50","doi-asserted-by":"publisher","first-page":"3499","DOI":"10.1093\/bioinformatics\/btu438","volume":"30","author":"R Rahn","year":"2014","unstructured":"Rahn R, Weese D, Reinert K (2014) Journaled string tree \u2013 a scalable data structure for analyzing thousands of similar genomes on your laptop. Bioinformatics 30(24):3499\u20133505","journal-title":"Bioinformatics"},{"key":"53-1_CR51","doi-asserted-by":"crossref","unstructured":"Sadakane K (2000) Compressed text databases with efficient query algorithms based on the compressed suffix array. In: Proceedings of the 11th international symposium on algorithms and computations (ISAAC), pp 410\u2013421","DOI":"10.1007\/3-540-40996-3_35"},{"issue":"2","key":"53-1_CR52","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","volume":"48","author":"K Sadakane","year":"2003","unstructured":"Sadakane K (2003) New text indexing functionalities of the compressed suffix arrays. J Algorithms 48(2):294\u2013313","journal-title":"J Algorithms"},{"issue":"9","key":"53-1_CR53","doi-asserted-by":"publisher","first-page":"R98","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 (2009) Simultaneous alignment of short reads against multiple genomes. Genome Biol 10(9):R98","journal-title":"Genome Biol"},{"key":"53-1_CR54","doi-asserted-by":"crossref","unstructured":"Sir\u00e9n J (2017) Indexing variation graphs. In: Proceedings of the 19th workshop on algorithm engineering and experiments (ALENEX), pp 13\u201327","DOI":"10.1137\/1.9781611974768.2"},{"key":"53-1_CR55","doi-asserted-by":"crossref","unstructured":"Sir\u00e9n J, V\u00e4lim\u00e4ki N, M\u00e4kinen V (2011) Indexing finite language representation of population genotypes. In: Proceedings of the 11th workshop on algorithms in bioinformatics (WABI), pp 270\u2013281","DOI":"10.1007\/978-3-642-23038-7_23"},{"issue":"2","key":"53-1_CR56","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 Bioinform 11(2): 375\u2013388","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"53-1_CR57","doi-asserted-by":"crossref","unstructured":"Takabatake Y, Tabei Y, Sakamoto H (2014) Improved ESP-index: a practical self-index for highly repetitive texts. In: Proceedings of the 13th symposium on experimental algorithms (SEA), pp 338\u2013350","DOI":"10.1007\/978-3-319-07959-2_29"},{"key":"53-1_CR58","doi-asserted-by":"crossref","unstructured":"Takabatake Y, Nakashima K, Kuboyama T, Tabei Y, Sakamoto H (2016) siEDM: an efficient string index and search algorithm for edit distance with moves. Algorithms 9(2):26","DOI":"10.3390\/a9020026"},{"key":"53-1_CR59","doi-asserted-by":"crossref","unstructured":"Takagi T, Goto K, Fujishige Y, Inenaga S, Arimura H (2017) Linear-size CDAWG: new repetition-aware indexing and grammar compression. In: Proceedings of the 24th symposium on string processing and information retrieval (SPIRE), pp 304\u2013316","DOI":"10.1007\/978-3-319-67428-5_26"},{"key":"53-1_CR60","doi-asserted-by":"crossref","unstructured":"Valenzuela D (2016) CHICO: a compressed hybrid index for repetitive collections. In: Proceedings of the 15th symposium on experimental algorithms (SEA), pp 326\u2013338","DOI":"10.1007\/978-3-319-38851-9_22"},{"key":"53-1_CR61","doi-asserted-by":"crossref","unstructured":"Valenzuela D, M\u00e4kinen V (2017) CHIC: a short read aligner for pan-genomic references. Technical report 178129, bioRxiv.org","DOI":"10.1101\/178129"},{"issue":"5","key":"53-1_CR62","doi-asserted-by":"publisher","first-page":"461","DOI":"10.14778\/2735479.2735480","volume":"8","author":"S Wandelt","year":"2015","unstructured":"Wandelt S, Leser U (2015) MRCSI: compressing and searching string collections with multiple references. Proc VLDB Endowment 8(5):461\u2013472","journal-title":"Proc VLDB Endowment"},{"issue":"13","key":"53-1_CR63","doi-asserted-by":"publisher","first-page":"1534","DOI":"10.14778\/2536258.2536265","volume":"6","author":"S Wandelt","year":"2013","unstructured":"Wandelt S, Starlinger J, Bux M, Leser U (2013) RCSI: scalable similarity search in thousand(s) of genomes. Proc VLDB Endowment 6(13):1534\u20131545","journal-title":"Proc VLDB Endowment"},{"issue":"3","key":"53-1_CR64","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J Ziv","year":"1977","unstructured":"Ziv J, Lempel A (1977) A universal algorithm for sequential data compression. IEEE Trans Inf Theory 23(3):337\u2013343","journal-title":"IEEE Trans Inf Theory"}],"container-title":["Encyclopedia of Big Data Technologies"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-63962-8_53-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,28]],"date-time":"2020-10-28T19:16:14Z","timestamp":1603912574000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-63962-8_53-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319639628","9783319639628"],"references-count":64,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-63962-8_53-1","relation":{},"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"10 February 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}