{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T17:40:03Z","timestamp":1748454003077,"version":"3.41.0"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319199283"},{"type":"electronic","value":"9783319199290"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19929-0_4","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T13:09:49Z","timestamp":1434373789000},"page":"40-51","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis"],"prefix":"10.1007","author":[{"given":"Timo","family":"Beller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enno","family":"Ohlebusch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","volume":"2","author":"MI Abouelhoda","year":"2004","unstructured":"Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms 2, 53\u201386 (2004)","journal-title":"J. Discrete Algorithms"},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.jda.2012.07.007","volume":"18","author":"T Beller","year":"2013","unstructured":"Beller, T., Gog, S., Ohlebusch, E., Schnattinger, T.: Computing the longest common prefix array based on the Burrows-Wheeler transform. J. Discrete Algorithms 18, 22\u201331 (2013)","journal-title":"J. Discrete Algorithms"},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/978-3-319-02432-5_5","volume-title":"String Processing and Information Retrieval","author":"T Beller","year":"2013","unstructured":"Beller, T., Zwerger, M., Gog, S., Ohlebusch, E.: Space-efficient construction of the Burrows-Wheeler transform. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) SPIRE 2013. LNCS, vol. 8214, pp. 5\u201316. Springer, Heidelberg (2013)"},{"key":"4_CR4","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Research Report 124, Digital Systems Research Center (1994)"},{"key":"4_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-319-07566-2_10","volume-title":"Combinatorial Pattern Matching","author":"B Cazaux","year":"2014","unstructured":"Cazaux, B., Lecroq, T., Rivals, E.: From indexing data structures to de Bruijn graphs. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 89\u201399. Springer, Heidelberg (2014)"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1007\/978-3-642-12200-2_60","volume-title":"LATIN 2010: Theoretical Informatics","author":"P Ferragina","year":"2010","unstructured":"Ferragina, P., Gagie, T., Manzini, G.: Lightweight data indexing and compression in external memory. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 697\u2013710. Springer, Heidelberg (2010)"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, pp. 390\u2013398 (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2011.12.002","volume":"426\u2013427","author":"T Gagie","year":"2012","unstructured":"Gagie, T., Navarro, G., Puglisi, S.J.: New algorithms on wavelet trees and applications to information retrieval. Theoret. Comput. Sci. 426\u2013427, 25\u201341 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1007\/978-3-319-07959-2_28","volume-title":"Experimental Algorithms","author":"S Gog","year":"2014","unstructured":"Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 326\u2013337. Springer, Heidelberg (2014)"},{"key":"4_CR10","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 841\u2013850 (2003)"},{"issue":"13","key":"4_CR11","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.: Short read alignment with populations of genomes. Bioinformatics 29(13), i361\u2013i370 (2013)","journal-title":"Bioinformatics"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"issue":"3","key":"4_CR13","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.tcs.2007.07.018","volume":"387","author":"J K\u00e4rkk\u00e4inen","year":"2007","unstructured":"K\u00e4rkk\u00e4inen, J.: Fast BWT in small space by blockwise suffix sorting. Theoret. Comput. Sci. 387(3), 249\u2013257 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"24","key":"4_CR14","doi-asserted-by":"publisher","first-page":"3476","DOI":"10.1093\/bioinformatics\/btu756","volume":"30","author":"S Marcus","year":"2014","unstructured":"Marcus, S., Lee, H., Schatz, M.C.: SplitMEM: a graphical algorithm for pan-genome analysis with suffix skips. Bioinformatics 30(24), 3476\u20133483 (2014)","journal-title":"Bioinformatics"},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1007\/978-3-319-07959-2_36","volume-title":"Experimental Algorithms","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Ord\u00f3\u00f1ez, A.: Faster compressed suffix trees for repetitive text collections. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 424\u2013435. Springer, Heidelberg (2014)"},{"key":"4_CR16","volume-title":"Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction","author":"E Ohlebusch","year":"2013","unstructured":"Ohlebusch, E.: Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag, Germany (2013)"},{"key":"4_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/978-3-642-16321-0_36","volume-title":"String Processing and Information Retrieval","author":"E Ohlebusch","year":"2010","unstructured":"Ohlebusch, E., Gog, S., K\u00fcgel, A.: Computing matching statistics and maximal exact matches on compressed full-text indexes. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 347\u2013358. Springer, Heidelberg (2010)"},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-03784-9_9","volume-title":"String Processing and Information Retrieval","author":"D Okanohara","year":"2009","unstructured":"Okanohara, D., Sadakane, K.: A linear-time Burrows-Wheeler transform using induced sorting. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol. 5721, pp. 90\u2013101. Springer, Heidelberg (2009)"},{"issue":"2","key":"4_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1242471.1242472","volume":"39","author":"SJ Puglisi","year":"2007","unstructured":"Puglisi, S.J., Smyth, W.F., Turpin, A.: A taxonomy of suffix array construction algorithms. ACM Comput. Surv. 39(2), 1\u201331 (2007). Article 4","journal-title":"ACM Comput. Surv."},{"issue":"24","key":"4_CR20","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.: Journaled string tree-a scalable data structure for analyzing thousands of similar genomes on your laptop. Bioinformatics 30(24), 3499\u20133505 (2014)","journal-title":"Bioinformatics"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1038\/msb.2011.54","volume":"7","author":"J Rozowsky","year":"2011","unstructured":"Rozowsky, J., Abyzov, A., Wang, J., Alves, P., Raha, D., Harmanci, A., Leng, J., Bjornson, R., Kong, Y., Kitabayashi, N., Bhardwaj, N., Rubin, M., Snyder, M., Gerstein, M.: AlleleSeq: Analysis of allele-specific expression and binding in a network framework. Mol. Syst. Biol. 7, 522 (2011)","journal-title":"Mol. Syst. Biol."},{"issue":"9","key":"4_CR22","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.: Simultaneous alignment of short reads against multiple genomes. Genome Biol. 10(9), R98 (2009)","journal-title":"Genome Biol."},{"key":"4_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-540-89097-3_17","volume-title":"String Processing and Information Retrieval","author":"J Sir\u00e9n","year":"2008","unstructured":"Sir\u00e9n, J., V\u00e4lim\u00e4ki, N., M\u00e4kinen, V., Navarro, G.: Run-length compressed indexes are superior for highly repetitive sequence collections. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol. 5280, pp. 164\u2013175. Springer, Heidelberg (2008)"},{"key":"4_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-642-38036-5_24","volume-title":"Bioinformatics Research and Applications","author":"N V\u00e4lim\u00e4ki","year":"2013","unstructured":"V\u00e4lim\u00e4ki, N., Rivals, E.: Scalable and versatile k-mer indexing for high-throughput sequencing data. In: Cai, Z., Eulenstein, O., Janies, D., Schwartz, D. (eds.) ISBRA 2013. LNCS, vol. 7875, pp. 237\u2013248. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19929-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T16:58:02Z","timestamp":1748451482000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19929-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319199283","9783319199290"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19929-0_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}