{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:49Z","timestamp":1759638289827},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662495285"},{"type":"electronic","value":"9783662495292"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49529-2_13","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T04:09:41Z","timestamp":1458533381000},"page":"164-178","source":"Crossref","is-referenced-by-count":12,"title":["Bidirectional Variable-Order de Bruijn Graphs"],"prefix":"10.1007","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[]},{"given":"Veli","family":"M\u00e4kinen","sequence":"additional","affiliation":[]},{"given":"Marco","family":"Previtali","sequence":"additional","affiliation":[]},{"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,22]]},"reference":[{"issue":"5","key":"13_CR1","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1089\/cmb.2012.0021","volume":"19","author":"A Bankevich","year":"2012","unstructured":"Bankevich, A., et al.: SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing. J. Comput. Biol. 19(5), 455\u2013477 (2012)","journal-title":"J. Comput. Biol."},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-642-40450-4_12","volume-title":"Algorithms \u2013 ESA 2013","author":"D Belazzougui","year":"2013","unstructured":"Belazzougui, D., Cunial, F., K\u00e4rkk\u00e4inen, J., M\u00e4kinen, V.: Versatile succinct representations of the bidirectional burrows-wheeler transform. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 133\u2013144. Springer, Heidelberg (2013)"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Boucher, C., Bowe, A., Gagie, T., Puglisi, S.J., Sadakane, K.: Variable-order de Bruijn graphs. In: Proceedings of the Data Compression Conference (DCC), pp. 383\u2013392. IEEE (2015)","DOI":"10.1109\/DCC.2015.70"},{"key":"13_CR4","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. 7534, pp. 225\u2013235. Springer, Heidelberg (2012)"},{"key":"13_CR5","unstructured":"Burrows, M., Wheeler, D.J.: A block sorting lossless data compression algorithm. Technical report 124, Digital Equipment Corporation (1994)"},{"issue":"5","key":"13_CR6","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1101\/gr.7337908","volume":"18","author":"J Butler","year":"2008","unstructured":"Butler, J., et al.: ALLPATHS: de novo assembly of whole-genome shotgun microreads. Genome Res. 18(5), 810\u2013820 (2008)","journal-title":"Genome Res."},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-319-05269-4_4","volume-title":"Research in Computational Molecular Biology","author":"R Chikhi","year":"2014","unstructured":"Chikhi, R., Limasset, A., Jackman, S., Simpson, J.T., Medvedev, P.: On the representation of de Bruijn graphs. In: Sharan, R. (ed.) RECOMB 2014. LNCS, vol. 8394, pp. 35\u201355. Springer, Heidelberg (2014)"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Chikhi, R., Rizk, G.: Space-efficient and exact de Bruijn graph representation based on a Bloom filter. Algorithm. Mol. Biol. 8(22) (2012)","DOI":"10.1186\/1748-7188-8-22"},{"issue":"4","key":"13_CR9","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1093\/bioinformatics\/btq697","volume":"27","author":"TC Conway","year":"2011","unstructured":"Conway, T.C., Bromage, A.J.: Succinct data structures for assembling large genomes. Bioinformatics 27(4), 479\u2013486 (2011)","journal-title":"Bioinformatics"},{"issue":"6","key":"13_CR10","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1093\/jhered\/esp086","volume":"100","author":"D Haussler","year":"2009","unstructured":"Haussler, D., et al.: Genome 10K: a proposal to obtain whole-genome sequence for 10,000 vertebrate species. J. Hered. 100(6), 659\u2013674 (2009)","journal-title":"J. Hered."},{"key":"13_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-662-48221-6_16","volume-title":"Algorithms in Bioinformatics","author":"G Holley","year":"2015","unstructured":"Holley, G., Wittler, R., Stoye, J.: Bloom filter trie \u2013 a data structure for pan-genome storage. In: Pop, M., Touzet, H. (eds.) WABI 2015. LNCS, vol. 9289, pp. 217\u2013230. Springer, Heidelberg (2015)"},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/3-540-45452-7_13","volume-title":"Combinatorial Pattern Matching","author":"W-K Hon","year":"2002","unstructured":"Hon, W.-K., Sadakane, K.: Space-economical algorithms for finding maximal unique matches. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol. 2373, pp. 144\u2013152. Springer, Heidelberg (2002)"},{"issue":"2","key":"13_CR13","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1101\/gr.097261.109","volume":"20","author":"R Li","year":"2010","unstructured":"Li, R., et al.: De novo assembly of human genomes with massively parallel short read sequencing. Genome Res. 20(2), 265\u2013272 (2010)","journal-title":"Genome Res."},{"issue":"15","key":"13_CR14","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. Bioinformatics 25(15), 1966\u20131967 (2009)","journal-title":"Bioinformatics"},{"key":"13_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1007\/978-3-662-48350-3_74","volume-title":"European Symposium on Algorithms","author":"JI Munro","year":"2015","unstructured":"Munro, J.I., Nekrich, Y.: Compressed data structures for dynamic sequences. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 891\u2013902. Springer, Heidelberg (2015)"},{"issue":"5","key":"13_CR16","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1137\/130908245","volume":"43","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Nekrich, Y.: Optimal dynamic sequence representations. SIAM J. Comput. 43(5), 1781\u20131806 (2014)","journal-title":"SIAM J. Comput."},{"key":"13_CR17","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1137\/1.9781611972870.6","volume-title":"2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX)","author":"Daisuke Okanohara","year":"2007","unstructured":"Okanohara, D., Sadakane, K.: Practical entropy-compressed rank\/select dictionary. In: ALENEX, pp. 60\u201370 (2007)"},{"issue":"12","key":"13_CR18","doi-asserted-by":"publisher","first-page":"2024","DOI":"10.1101\/gr.080200.108","volume":"18","author":"S Ossowski","year":"2008","unstructured":"Ossowski, S., et al.: Sequencing of natural strains of Arabidopsis thaliana with short reads. Genome Res. 18(12), 2024\u20132033 (2008)","journal-title":"Genome Res."},{"issue":"33","key":"13_CR19","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. Proc. Nat. Acad. Sci. 109(33), 13272\u201313277 (2012)","journal-title":"Proc. Nat. Acad. Sci."},{"key":"13_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/978-3-642-12683-3_28","volume-title":"Research in Computational Molecular Biology","author":"Y Peng","year":"2010","unstructured":"Peng, Y., Leung, H.C.M., Yiu, S.M., Chin, F.Y.L.: IDBA \u2013 a practical iterative de Bruijn graph de novo assembler. In: Berger, B. (ed.) RECOMB 2010. LNCS, vol. 6044, pp. 426\u2013440. Springer, Heidelberg (2010)"},{"issue":"1","key":"13_CR21","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/1748-7188-9-2","volume":"9","author":"Kamil Salikhov","year":"2014","unstructured":"Salikhov, K., Sacomoto, G., Kucherov, G.: Using cascading Bloom filters to improve the memory usage for de Bruijn graphs. Algorithms Mol. Biol. 9(2) (2014)","journal-title":"Algorithms for Molecular Biology"},{"key":"13_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-642-13509-5_5","volume-title":"Combinatorial Pattern Matching","author":"T Schnattinger","year":"2010","unstructured":"Schnattinger, T., Ohlebusch, E., Gog, S.: Bidirectional search in a string with wavelet trees. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, pp. 40\u201350. Springer, Heidelberg (2010)"},{"issue":"6","key":"13_CR23","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1101\/gr.089532.108","volume":"19","author":"JT Simpson","year":"2009","unstructured":"Simpson, J.T., et al.: ABySS: a parallel assembler for short read sequence data. Genome Res. 19(6), 1117\u20131123 (2009)","journal-title":"Genome Res."},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"The 1000 Genomes Project Consortium. An integrated map of genetic variation from 1,092 human genomes. Nature 491(7422), 56\u201365 (2012)","DOI":"10.1038\/nature11632"},{"issue":"7164","key":"13_CR25","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1038\/nature06244","volume":"449","author":"PJ Turnbaugh","year":"2007","unstructured":"Turnbaugh, P.J., et al.: The human microbiome project: exploring the microbial part of ourselves in a changing world. Nature 449(7164), 804\u2013810 (2007)","journal-title":"Nature"}],"container-title":["Lecture Notes in Computer Science","LATIN 2016: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49529-2_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T17:20:56Z","timestamp":1559409656000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49529-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662495285","9783662495292"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49529-2_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}