{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T23:57:28Z","timestamp":1778025448819,"version":"3.51.4"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319052687","type":"print"},{"value":"9783319052694","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-05269-4_4","type":"book-chapter","created":{"date-parts":[[2014,2,27]],"date-time":"2014-02-27T22:19:53Z","timestamp":1393539593000},"page":"35-55","source":"Crossref","is-referenced-by-count":76,"title":["On the Representation of de Bruijn Graphs"],"prefix":"10.1007","author":[{"given":"Rayan","family":"Chikhi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Limasset","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaun","family":"Jackman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jared T.","family":"Simpson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Medvedev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Adjeroh, D., Bell, T.C., Mukherjee, A.: The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching. Springer (2008)","DOI":"10.1007\/978-0-387-78909-5"},{"issue":"5","key":"4_CR2","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1089\/cmb.2012.0021","volume":"19","author":"A. Bankevich","year":"2012","unstructured":"Bankevich, A., Nurk, S., Antipov, D., Gurevich, A.A., Dvorkin, M., Kulikov, A.S., Lesin, V.M., Nikolenko, S.I., Pham, S.K., Prjibelski, A.D., Pyshkin, A., Sirotkin, A., Vyahhi, N., Tesler, G., Alekseyev, M.A., Pevzner, P.A.: SPAdes: A new genome assembly algorithm and its applications to single-cell sequencing. Journal of Computational Biology\u00a019(5), 455\u2013477 (2012)","journal-title":"Journal of Computational Biology"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Birol, I., Raymond, A., Jackman, S.D., Pleasance, S., Coope, R., Taylor, G.A., Yuen, M.M.S., Keeling, C.I., Brand, D., Vandervalk, B.P., Kirk, H., Pandoh, P., Moore, R.A., Zhao, Y., Mungall, A.J., Jaquish, B., Yanchuk, A., Ritland, C., Boyle, B., Bousquet, J., Ritland, K., MacKay, J., Bohlmann, J., Jones, S.J.: Assembling the 20 Gb white spruce (Picea glauca) genome from whole-genome shotgun sequencing data. Bioinformatics (2013)","DOI":"10.1093\/bioinformatics\/btt178"},{"issue":"7","key":"4_CR4","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"B.H. Bloom","year":"1970","unstructured":"Bloom, B.H.: Space\/time trade-offs in hash coding with allowable errors. Commun. ACM\u00a013(7), 422\u2013426 (1970)","journal-title":"Commun. ACM"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Boisvert, S., Raymond, F., Godzaridis, \u00c9., Laviolette, F., Corbeil, J., et al.: Ray Meta: scalable de novo metagenome assembly and profiling. Genome Biology\u00a013(12), R122 (2012)","DOI":"10.1186\/gb-2012-13-12-r122"},{"key":"4_CR6","unstructured":"Bowe, A.: Succinct de Bruijn graphs (blog post), http:\/\/alexbowe.com\/succinct-debruijn-graphs\/ (accessed: October 18, 2013)"},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/978-3-642-33122-0_18","volume-title":"Algorithms in Bioinformatics","author":"A. Bowe","year":"2012","unstructured":"Bowe, A., Onodera, T., Sadakane, K., Shibuya, T.: Succinct de bruijn graphs. In: Raphael, B., Tang, J. (eds.) WABI 2012. LNCS, vol.\u00a07534, pp. 225\u2013235. Springer, Heidelberg (2012)"},{"key":"4_CR8","volume-title":"A block sorting lossless data compression algorithm. Technical report 124. Tech. rep.","author":"M. Burrows","year":"1994","unstructured":"Burrows, M., Wheeler, D.J.: A block sorting lossless data compression algorithm. Technical report 124. Tech. rep. Digital Equipment Corporation, Palo Alto (1994)"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/978-3-642-33122-0_19","volume-title":"Algorithms in Bioinformatics","author":"R. Chikhi","year":"2012","unstructured":"Chikhi, R., Rizk, G.: Space-efficient and exact de Bruijn graph representation based on a Bloom filter. In: Raphael, B., Tang, J. (eds.) WABI 2012. LNCS, vol.\u00a07534, pp. 236\u2013248. Springer, Heidelberg (2012)"},{"issue":"4","key":"4_CR10","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1093\/bioinformatics\/btq697","volume":"27","author":"T.C. Conway","year":"2011","unstructured":"Conway, T.C., Bromage, A.J.: Succinct data structures for assembling large genomes. Bioinformatics\u00a027(4), 479 (2011)","journal-title":"Bioinformatics"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Compressing and indexing labeled trees, with applications. J. ACM\u00a057(1) (2009)","DOI":"10.1145\/1613676.1613680"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 390\u2013398. IEEE (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jda.2011.08.001","volume":"10","author":"T. Gagie","year":"2012","unstructured":"Gagie, T.: Bounds from a card trick. Journal of Discrete Algorithms\u00a010, 2\u20134 (2012)","journal-title":"Journal of Discrete Algorithms"},{"issue":"4","key":"4_CR14","doi-asserted-by":"publisher","first-page":"1513","DOI":"10.1073\/pnas.1017351108","volume":"108","author":"S. Gnerre","year":"2011","unstructured":"Gnerre, S., MacCallum, I., Przybylski, D., Ribeiro, F.J., Burton, J.N., Walker, B.J., Sharpe, T., Hall, G., Shea, T.P., Sykes, S.: High-quality draft assemblies of mammalian genomes from massively parallel sequence data. Proceedings of the National Academy of Sciences\u00a0108(4), 1513 (2011)","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"4_CR15","unstructured":"Gonz\u00e1lez, R., Grabowski, S., M\u00e4kinen, V., Navarro, G.: Practical implementation of rank and select queries. In: Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA 2005), Greece, pp. 27\u201338 (2005)"},{"issue":"7","key":"4_CR16","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1038\/nbt.1883","volume":"29","author":"M.G. Grabherr","year":"2011","unstructured":"Grabherr, M.G., Haas, B.J., Yassour, M., Levin, J.Z., Thompson, D.A., Amit, I., Adiconis, X., Fan, L., Raychowdhury, R., Zeng, Q., et al.: Full-length transcriptome assembly from RNA-Seq data without a reference genome. Nature Biotechnology\u00a029(7), 644\u2013652 (2011)","journal-title":"Nature Biotechnology"},{"issue":"6","key":"4_CR17","first-page":"659","volume":"100","author":"D. Haussler","year":"2008","unstructured":"Haussler, D., O\u2019Brien, S.J., Ryder, O.A., Barker, F.K., Clamp, M., Crawford, A.J., Hanner, R., Hanotte, O., Johnson, W.E., McGuire, J.A., et al.: Genome 10K: a proposal to obtain whole-genome sequence for 10,000 vertebrate species. Journal of Heredity\u00a0100(6), 659\u2013674 (2008)","journal-title":"Journal of Heredity"},{"issue":"2","key":"4_CR18","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1089\/cmb.1995.2.291","volume":"2","author":"R.M. Idury","year":"1995","unstructured":"Idury, R.M., Waterman, M.S.: A new algorithm for DNA sequence assembly. Journal of Computational Biology\u00a02(2), 291\u2013306 (1995)","journal-title":"Journal of Computational Biology"},{"issue":"2","key":"4_CR19","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1038\/ng.1028","volume":"44","author":"Z. Iqbal","year":"2012","unstructured":"Iqbal, Z., Caccamo, M., Turner, I., Flicek, P., McVean, G.: De novo assembly and genotyping of variants using colored de Bruijn graphs. Nature Genetics\u00a044(2), 226\u2013232 (2012)","journal-title":"Nature Genetics"},{"issue":"4","key":"4_CR20","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/nmeth.1923","volume":"9","author":"B. Langmead","year":"2012","unstructured":"Langmead, B., Salzberg, S.L.: Fast gapped-read alignment with Bowtie 2. Nature Methods\u00a09(4), 357\u2013359 (2012)","journal-title":"Nature Methods"},{"issue":"14","key":"4_CR21","doi-asserted-by":"publisher","first-page":"1838","DOI":"10.1093\/bioinformatics\/bts280","volume":"28","author":"H. Li","year":"2012","unstructured":"Li, H.: Exploring single-sample SNP and INDEL calling with whole-genome de novo assembly. Bioinformatics\u00a028(14), 1838\u20131844 (2012)","journal-title":"Bioinformatics"},{"issue":"14","key":"4_CR22","doi-asserted-by":"publisher","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","volume":"25","author":"H. Li","year":"2009","unstructured":"Li, H., Durbin, R.: Fast and accurate short read alignment with Burrows\u2013Wheeler transform. Bioinformatics\u00a025(14), 1754\u20131760 (2009)","journal-title":"Bioinformatics"},{"issue":"2","key":"4_CR23","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1101\/gr.097261.109","volume":"20","author":"R. Li","year":"2010","unstructured":"Li, R., Zhu, H., Ruan, J., Qian, W., Fang, X., Shi, Z., Li, Y., Li, S., Shan, G., Kristiansen, K.: De novo assembly of human genomes with massively parallel short read sequencing. Genome Research\u00a020(2), 265 (2010)","journal-title":"Genome Research"},{"issue":"15","key":"4_CR24","doi-asserted-by":"publisher","first-page":"1966","DOI":"10.1093\/bioinformatics\/btp336","volume":"25","author":"R. Li","year":"2009","unstructured":"Li, R., Yu, C., Li, Y., Lam, T.W., Yiu, S.M., Kristiansen, K., Wang, J.: SOAP2: an improved ultrafast tool for short read alignment. Bioinformatics\u00a025(15), 1966\u20131967 (2009)","journal-title":"Bioinformatics"},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"Li, Y., Kamousi, P., Han, F., Yang, S., Yan, X., Suri, S.: Memory efficient minimum substring partitioning. In: Proceedings of the 39th International Conference on Very Large Data Bases, pp. 169\u2013180. VLDB Endowment (2013)","DOI":"10.14778\/2535569.2448951"},{"issue":"6","key":"4_CR26","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ygeno.2010.03.001","volume":"95","author":"J.R. Miller","year":"2010","unstructured":"Miller, J.R., Koren, S., Sutton, G.: Assembly algorithms for next-generation sequencing data. Genomics\u00a095(6), 315\u2013327 (2010)","journal-title":"Genomics"},{"issue":"33","key":"4_CR27","doi-asserted-by":"publisher","first-page":"13272","DOI":"10.1073\/pnas.1121464109","volume":"109","author":"J. Pell","year":"2012","unstructured":"Pell, J., Hintze, A., Canino-Koning, R., Howe, A., Tiedje, J.M., Brown, C.T.: Scaling metagenome sequence assembly with probabilistic de Bruijn graphs. Proceedings of the National Academy of Sciences\u00a0109(33), 13272\u201313277 (2012)","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"1","key":"4_CR28","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1080\/07391102.1989.10507752","volume":"7","author":"P.A. Pevzner","year":"1989","unstructured":"Pevzner, P.A.: l-Tuple DNA sequencing: computer analysis. Journal of Biomolecular Structure & Dynamics\u00a07(1), 63\u201373 (1989)","journal-title":"Journal of Biomolecular Structure & Dynamics"},{"issue":"5","key":"4_CR29","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1093\/bioinformatics\/btt020","volume":"29","author":"G. Rizk","year":"2013","unstructured":"Rizk, G., Lavenier, D., Chikhi, R.: DSK: k-mer counting with very low memory usage. Bioinformatics\u00a029(5), 652\u2013653 (2013)","journal-title":"Bioinformatics"},{"issue":"18","key":"4_CR30","doi-asserted-by":"publisher","first-page":"3363","DOI":"10.1093\/bioinformatics\/bth408","volume":"20","author":"M. Roberts","year":"2004","unstructured":"Roberts, M., Hayes, W., Hunt, B.R., Mount, S.M., Yorke, J.A.: Reducing storage requirements for biological sequence comparison. Bioinformatics\u00a020(18), 3363\u20133369 (2004)","journal-title":"Bioinformatics"},{"issue":"4","key":"4_CR31","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1089\/cmb.2004.11.734","volume":"11","author":"M. Roberts","year":"2004","unstructured":"Roberts, M., Hunt, B.R., Yorke, J.A., Bolanos, R.A., Delcher, A.L.: A preprocessor for shotgun assembly of large genomes. Journal of Computational Biology\u00a011(4), 734\u2013752 (2004)","journal-title":"Journal of Computational Biology"},{"issue":"1","key":"4_CR32","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1186\/1471-2105-14-313","volume":"14","author":"E.A. R\u00f8dland","year":"2013","unstructured":"R\u00f8dland, E.A.: Compact representation of k-mer de bruijn graphs for genome read assembly. BMC Bioinformatics\u00a014(1), 313 (2013)","journal-title":"BMC Bioinformatics"},{"key":"4_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-642-40453-5_28","volume-title":"Algorithms in Bioinformatics","author":"K. Salikhov","year":"2013","unstructured":"Salikhov, K., Sacomoto, G., Kucherov, G.: Using cascading Bloom filters to improve the memory usage for de Brujin graphs. In: Darling, A., Stoye, J. (eds.) WABI 2013. LNCS, vol.\u00a08126, pp. 364\u2013376. Springer, Heidelberg (2013)"},{"issue":"3","key":"4_CR34","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1101\/gr.131383.111","volume":"22","author":"S.L. Salzberg","year":"2012","unstructured":"Salzberg, S.L., Phillippy, A.M., Zimin, A., Puiu, D., Magoc, T., Koren, S., Treangen, T.J., Schatz, M.C., Delcher, A.L., Roberts, M., et al.: GAGE: A critical evaluation of genome assemblies and assembly algorithms. Genome Research\u00a022(3), 557\u2013567 (2012)","journal-title":"Genome Research"},{"key":"4_CR35","unstructured":"Simpson, J.T.: Exploring genome characteristics and sequence quality without a reference. arXiv preprint arXiv:1307.8026 (2013)"},{"issue":"12","key":"4_CR36","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1093\/bioinformatics\/btq217","volume":"26","author":"J.T. Simpson","year":"2010","unstructured":"Simpson, J.T., Durbin, R.: Efficient construction of an assembly string graph using the FM-index. Bioinformatics\u00a026(12), 367\u2013373 (2010)","journal-title":"Bioinformatics"},{"issue":"3","key":"4_CR37","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1101\/gr.126953.111","volume":"22","author":"J.T. Simpson","year":"2012","unstructured":"Simpson, J.T., Durbin, R.: Efficient de novo assembly of large genomes using compressed data structures. Genome Research\u00a022(3), 549\u2013556 (2012)","journal-title":"Genome Research"},{"issue":"6","key":"4_CR38","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1101\/gr.089532.108","volume":"19","author":"J.T. Simpson","year":"2009","unstructured":"Simpson, J.T., Wong, K., Jackman, S.D., Schein, J.E., Jones, S.J., Birol, \u0130.: ABySS: a parallel assembler for short read sequence data. Genome Research\u00a019(6), 1117\u20131123 (2009)","journal-title":"Genome Research"},{"issue":"4","key":"4_CR39","first-page":"359","volume":"114","author":"J. Sondow","year":"2007","unstructured":"Sondow, J., Stong, R.: Choice bounds: 11132. The American Mathematical Monthly\u00a0114(4), 359\u2013360 (2007)","journal-title":"The American Mathematical Monthly"},{"key":"4_CR40","doi-asserted-by":"crossref","unstructured":"Ye, C., Ma, Z.S., Cannon, C.H., Pop, M., Douglas, W.Y.: Exploiting sparseness in de novo genome assembly. BMC Bioinformatics\u00a013(suppl. 6), S1 (2012)","DOI":"10.1186\/1471-2105-13-S6-S1"},{"issue":"5","key":"4_CR41","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1101\/gr.074492.107","volume":"18","author":"D.R. Zerbino","year":"2008","unstructured":"Zerbino, D.R., Birney, E.: Velvet: algorithms for de novo short read assembly using de Bruijn graphs. Genome Research\u00a018(5), 821\u2013829 (2008)","journal-title":"Genome Research"}],"container-title":["Lecture Notes in Computer Science","Research in Computational Molecular Biology"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-05269-4_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T23:23:09Z","timestamp":1746141789000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-05269-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319052687","9783319052694"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-05269-4_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}