{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:33:39Z","timestamp":1773275619231,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"S3","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1186\/s12859-017-1466-6","type":"journal-article","created":{"date-parts":[[2017,3,14]],"date-time":"2017-03-14T09:07:24Z","timestamp":1489482444000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A framework for space-efficient read clustering in metagenomic samples"],"prefix":"10.1186","volume":"18","author":[{"given":"Jarno","family":"Alanko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabio","family":"Cunial","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Djamal","family":"Belazzougui","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Veli","family":"M\u00e4kinen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,3,14]]},"reference":[{"issue":"13","key":"1466_CR1","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1093\/bioinformatics\/btr216","volume":"27","author":"Y Peng","year":"2011","unstructured":"Peng Y, Leung HC, Yiu S-M, Chin FY. Meta-IDBA: a de novo assembler for metagenomic data. Bioinformatics. 2011; 27(13):94\u2013101.","journal-title":"Bioinformatics"},{"issue":"33","key":"1466_CR2","doi-asserted-by":"crossref","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 JM, Brown CT. Scaling metagenome sequence assembly with probabilistic de Bruijn graphs. Proc Natl Acad Sci. 2012; 109(33):13272\u201313277.","journal-title":"Proc Natl Acad Sci"},{"issue":"13","key":"1466_CR3","doi-asserted-by":"crossref","first-page":"4904","DOI":"10.1073\/pnas.1402564111","volume":"111","author":"AC Howe","year":"2014","unstructured":"Howe AC, Jansson JK, Malfatti SA, Tringe SG, Tiedje JM, Brown CT. Tackling soil diversity with the assembly of large, complex metagenomes. Proc Natl Acad Sci. 2014; 111(13):4904\u2013909.","journal-title":"Proc Natl Acad Sci"},{"issue":"1","key":"1466_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-9-1","volume":"9","author":"F Meyer","year":"2008","unstructured":"Meyer F, Paarmann D, D\u2019Souza M, Olson R, Glass E, Kubal M, Paczian T, Rodriguez A, Stevens R, Wilke A, Wilkening J, Edwards R. The metagenomics RAST server \u2013 a public resource for the automatic phylogenetic and functional analysis of metagenomes. BMC Bioinforma. 2008; 9(1):1\u20138.","journal-title":"BMC Bioinforma"},{"issue":"supplement 1","key":"1466_CR5","first-page":"D19","volume":"39","author":"R Leinonen","year":"2010","unstructured":"Leinonen R, Sugawara H, Shumway M. The sequence read archive. Nucleic Acids Res. 2010; 39(supplement 1):D19\u2013D21. http:\/\/nar.oxfordjournals.org\/content\/39\/suppl_1\/D19 .","journal-title":"Nucleic Acids Res"},{"issue":"2","key":"1466_CR6","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1109\/TCBB.2011.111","volume":"9","author":"C-H Su","year":"2012","unstructured":"Su C-H, Wang T-Y, Hsu M-T, Weng FC-H, Kao C-Y, Wang D, Tsai H-K. The impact of normalization and phylogenetic information on estimating the distance for metagenomes. IEEE\/ACM Trans Comput Biology Bioinforma. 2012; 9(2):619\u201328.","journal-title":"IEEE\/ACM Trans Comput Biology Bioinforma"},{"issue":"1","key":"1466_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2164-13-1","volume":"13","author":"B Jiang","year":"2012","unstructured":"Jiang B, Song K, Ren J, Deng M, Sun F, Zhang X. Comparison of metagenomic samples using sequence signatures. BMC Genomics. 2012; 13(1):1.","journal-title":"BMC Genomics"},{"issue":"1","key":"1466_CR8","doi-asserted-by":"crossref","first-page":"84348","DOI":"10.1371\/journal.pone.0084348","volume":"9","author":"Y Wang","year":"2014","unstructured":"Wang Y, Liu L, Chen L, Chen T, Sun F. Comparison of metatranscriptomic samples based on k-tuple frequencies. PloS ONE. 2014; 9(1):84348.","journal-title":"PloS ONE"},{"issue":"19","key":"1466_CR9","first-page":"1","volume":"13","author":"N Maillet","year":"2012","unstructured":"Maillet N, Lemaitre C, Chikhi R, Lavenier D, Peterlongo P. Compareads: comparing huge metagenomic experiments. BMC Bioinformatics. 2012; 13(19):1.","journal-title":"BMC Bioinformatics"},{"issue":"1","key":"1466_CR10","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1186\/1471-2105-11-544","volume":"11","author":"DR Kelley","year":"2010","unstructured":"Kelley DR, Salzberg SL. Clustering metagenomic sequences with interpolated Markov models. BMC Bioinformatics. 2010; 11(1):544.","journal-title":"BMC Bioinformatics"},{"issue":"1","key":"1466_CR11","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1186\/s12859-015-0473-8","volume":"16","author":"Y Wang","year":"2015","unstructured":"Wang Y, Hu H, Li X. MBBC: an efficient approach for metagenomic binning based on clustering. BMC Bioinformatics. 2015; 16(1):36.","journal-title":"BMC Bioinformatics"},{"issue":"1","key":"1466_CR12","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1186\/1471-2105-10-316","volume":"10","author":"A Kislyuk","year":"2009","unstructured":"Kislyuk A, Bhatnagar S, Dushoff J, Weitz JS. Unsupervised statistical clustering of environmental shotgun sequences. BMC Bioinformatics. 2009; 10(1):316.","journal-title":"BMC Bioinformatics"},{"issue":"3","key":"1466_CR13","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1089\/cmb.2010.0245","volume":"18","author":"Y-W Wu","year":"2011","unstructured":"Wu Y-W, Ye Y. A novel abundance-based algorithm for binning metagenomic sequences using \u2113-tuples. J Comput Biol. 2011; 18(3):523\u201334.","journal-title":"J Comput Biol"},{"issue":"1","key":"1466_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13015-014-0028-y","volume":"10","author":"T Van Lang","year":"2015","unstructured":"Van Lang T, Van Hoai T, et al.A two-phase binning algorithm using \u2113-mer frequency on groups of non-overlapping reads. Algorithm Mol Biol. 2015; 10(1):1.","journal-title":"Algorithm Mol Biol"},{"issue":"18","key":"1466_CR15","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1093\/bioinformatics\/bts397","volume":"28","author":"Y Wang","year":"2012","unstructured":"Wang Y, Leung HC, Yiu S-M, Chin FY. MetaCluster 5.0: a two-round binning approach for metagenomic data for low-abundance species in a noisy sample. Bioinformatics. 2012; 28(18):356\u201362.","journal-title":"Bioinformatics"},{"issue":"2","key":"1466_CR16","doi-asserted-by":"crossref","first-page":"231","DOI":"10.2174\/157489361002150518150716","volume":"10","author":"K Siegel","year":"2015","unstructured":"Siegel K, Altenburger K, Hon Y-S, Lin J, Yu C. Puzzlecluster: A novel unsupervised clustering algorithm for binning dna fragments in metagenomics. Current Bioinformatics. 2015; 10(2):231\u201352.","journal-title":"Current Bioinformatics"},{"issue":"2","key":"1466_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1371\/journal.pcbi.1002373","volume":"8","author":"Y Baran","year":"2012","unstructured":"Baran Y, Halperin E. Joint analysis of multiple metagenomic samples. PLoS Comput Biol. 2012; 8(2):1\u201311.","journal-title":"PLoS Comput Biol"},{"issue":"11","key":"1466_CR18","doi-asserted-by":"crossref","first-page":"1144","DOI":"10.1038\/nmeth.3103","volume":"11","author":"J Alneberg","year":"2014","unstructured":"Alneberg J, Bjarnason BS, de Bruijn I, Schirmer M, Quick J, Ijaz UZ, Lahti L, Loman NJ, Andersson AF, Quince C. Binning metagenomic contigs by coverage and composition. Nature methods. 2014; 11(11):1144\u20131146.","journal-title":"Nature methods"},{"issue":"1","key":"1466_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1748-7188-7-27","volume":"7","author":"O Tanaseichuk","year":"2012","unstructured":"Tanaseichuk O, Borneman J, Jiang T. Separating metagenomic short reads into genomes via clustering. Algorithms Mol Biol. 2012; 7(1):1.","journal-title":"Algorithms Mol Biol"},{"key":"1466_CR20","volume-title":"Proc. 14th Annual IEEE Symposium on Switching and Automata Theory","author":"P Weiner","year":"1973","unstructured":"Weiner P. Linear pattern matching algorithms. In: Proc. 14th Annual IEEE Symposium on Switching and Automata Theory. Washington, DC, USA: IEEE: 1973. p. 1\u201311."},{"key":"1466_CR21","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139940023","volume-title":"Genome-Scale Algorithm Design","author":"V M\u00e4kinen","year":"2015","unstructured":"M\u00e4kinen V, Belazzougui D, Cunial F, Tomescu AI. Genome-Scale Algorithm Design. Cambridge: Cambridge University Press; 2015. ISBN-13: 9781107078536."},{"key":"1466_CR22","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"R Grossi","year":"2003","unstructured":"Grossi R, Gupta A, Vitter JS. High-order entropy-compressed text indexes. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Baltimore: Society for Industrial and Applied Mathematics Address of symposium: 2003. p. 841\u201350."},{"key":"1466_CR23","volume-title":"Compact pat trees","author":"D Clark","year":"1996","unstructured":"Clark D. Compact pat trees. Canada: PhD thesis, University of Waterloo; 1996."},{"key":"1466_CR24","volume-title":"Proc. 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). LNCS v. 1180","author":"I Munro","year":"1996","unstructured":"Munro I. Tables. In: Proc. 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). LNCS v. 1180. Hyderabad: Springer: 1996. p. 37\u201342."},{"key":"1466_CR25","volume-title":"European Symposium on Algorithms","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: European Symposium on Algorithms. Sophia Antipolis: Springer: 2013. p. 133\u201344."},{"key":"1466_CR26","volume-title":"IEEE International Conference on Bioinformatics and Biomedicine, 2009","author":"TW Lam","year":"2009","unstructured":"Lam TW, Li R, Tam A, Wong S, Wu E, Yiu S-M. High throughput short read alignment via bi-directional BWT. In: IEEE International Conference on Bioinformatics and Biomedicine, 2009. Washington D.C: IEEE: 2009. p. 31\u20136."},{"issue":"15","key":"1466_CR27","doi-asserted-by":"crossref","first-page":"1966","DOI":"10.1093\/bioinformatics\/btp336","volume":"25","author":"R Li","year":"2009","unstructured":"Li R, Yu C, Li Y, Lam TW, Yiu S-M, Kristiansen K, Wang J. Soap2: An improved ultrafast tool for short read alignment. Bioinformatics. 2009; 25(15):1966\u20131967.","journal-title":"Bioinformatics"},{"key":"1466_CR28","volume-title":"21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010). Lecture Notes in Computer Science","author":"T Schnattinger","year":"2010","unstructured":"Schnattinger T, Ohlebusch E, Gog S. Bidirectional search in a string with wavelet trees. In: 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010). Lecture Notes in Computer Science. New York: Springer: 2010. p. 40\u201350."},{"key":"1466_CR29","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.ic.2011.03.007","volume":"213","author":"T Schnattinger","year":"2012","unstructured":"Schnattinger T, Ohlebusch E, Gog S. Bidirectional search in a string with wavelet trees and bidirectional matching statistics. Inform Comput. 2012; 213:13\u201322.","journal-title":"Inform Comput"},{"key":"1466_CR30","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.jda.2013.07.004","volume":"25","author":"G Navarro","year":"2014","unstructured":"Navarro G. Wavelet trees for all. J Discret Algorithms. 2014; 25:2\u201320.","journal-title":"J Discret Algorithms"},{"key":"1466_CR31","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen TH. Introduction to Algorithms. Cambridge, MA, USA: MIT press; 2009."},{"key":"1466_CR32","volume-title":"Combinatorial Pattern Matching, Proceedings","author":"T Beller","year":"2015","unstructured":"Beller T, Ohlebusch E. Efficient construction of a compressed de Bruijn graph for pan-genome analysis. In: Combinatorial Pattern Matching, Proceedings. Ischia Island: Springer: 2015. p. 40\u201351."},{"key":"1466_CR33","volume-title":"Combinatorial Pattern Matching, Proceedings","author":"D Belazzougui","year":"2015","unstructured":"Belazzougui D, Cunial F. A framework for space-efficient string kernels. In: Combinatorial Pattern Matching, Proceedings. Ischia Island: Springer: 2015. p. 13\u201325."},{"key":"1466_CR34","doi-asserted-by":"crossref","unstructured":"Gog S, Beller T, Moffat A, Petri M. From theory to practice: Plug and play with succinct data structures. In: 13th International Symposium on Experimental Algorithms. Copenhagen: 2014. p. 326\u201337.","DOI":"10.1007\/978-3-319-07959-2_28"},{"issue":"22","key":"1466_CR35","doi-asserted-by":"crossref","first-page":"3274","DOI":"10.1093\/bioinformatics\/btu541","volume":"30","author":"H Li","year":"2014","unstructured":"Li H. Fast construction of FM-index for long sequence reads. Bioinformatics. 2014; 30(22):3274\u20135.","journal-title":"Bioinformatics"},{"issue":"Suppl 2","key":"1466_CR36","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1186\/1471-2105-11-S2-S5","volume":"11","author":"B Yang","year":"2010","unstructured":"Yang B, Peng Y, Leung HC, Yiu S-M, Chen J-C, Chin FY. Unsupervised binning of environmental genomic fragments based on an error robust selection of \u2113-mers. BMC Bioinformatics. 2010; 11(Suppl 2):5.","journal-title":"BMC Bioinformatics"},{"key":"1466_CR37","doi-asserted-by":"crossref","unstructured":"Yang B, Peng Y, Leung H, Yiu S-M, Qin J, Li R, Chin FY. MetaCluster: unsupervised binning of environmental genomic fragments and taxonomic annotation. In: Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology: 2010. p. 170\u20139.","DOI":"10.1145\/1854776.1854803"},{"issue":"11","key":"1466_CR38","doi-asserted-by":"crossref","first-page":"1489","DOI":"10.1093\/bioinformatics\/btr186","volume":"27","author":"HC Leung","year":"2011","unstructured":"Leung HC, Yiu S-M, Yang B, Peng Y, Wang Y, Liu Z, Chen J, Qin J, Li R, Chin FY. A robust and accurate binning algorithm for metagenomic sequences with arbitrary species abundance ratio. Bioinformatics. 2011; 27(11):1489\u20131495.","journal-title":"Bioinformatics"},{"issue":"2","key":"1466_CR39","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1089\/cmb.2011.0276","volume":"19","author":"Y Wang","year":"2012","unstructured":"Wang Y, Leung HC, Yiu S-M, Chin FY. MetaCluster 4.0: a novel binning algorithm for NGS reads and huge number of species. J Comput Biol. 2012; 19(2):241\u20139.","journal-title":"J Comput Biol"},{"issue":"10","key":"1466_CR40","doi-asserted-by":"crossref","first-page":"3373","DOI":"10.1371\/journal.pone.0003373","volume":"3","author":"DC Richter","year":"2008","unstructured":"Richter DC, Ott F, Auch AF, Schmid R, Huson DH. MetaSim \u2013 a sequencing simulator for genomics and metagenomics. PloS ONE. 2008; 3(10):3373.","journal-title":"PloS ONE"},{"issue":"7285","key":"1466_CR41","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1038\/nature08821","volume":"464","author":"J Qin","year":"2010","unstructured":"Qin J, Li R, Raes J, Arumugam M, Burgdorf KS, Manichanh C, Nielsen T, Pons N, Levenez F, Yamada T, et al.A human gut microbial gene catalogue established by metagenomic sequencing. Nature. 2010; 464(7285):59\u201365.","journal-title":"Nature"},{"issue":"1","key":"1466_CR42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s40168-014-0050-9","volume":"2","author":"MG Langille","year":"2014","unstructured":"Langille MG, Meehan CJ, Koenig JE, Dhanani AS, Rose RA, Howlett SE, Beiko RG. Microbial shifts in the aging mouse gut. Microbiome. 2014; 2(1):1.","journal-title":"Microbiome"},{"key":"1466_CR43","volume-title":"Proceedings of the 46th Annual ACM Symposium on Theory of Computing","author":"D Belazzougui","year":"2014","unstructured":"Belazzougui D. Linear time construction of compressed text indices in compact space. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing. New York: ACM: 2014. p. 148\u201393."},{"key":"1466_CR44","unstructured":"Alanko J. bwtCluster: Space-efficient clustering of metagenomic reads using the bidirectional Burrows-Wheeler transform. 2016. https:\/\/github.com\/jnalanko\/bwtCluster . Accessed 06 Oct 2016."},{"key":"1466_CR45","unstructured":"Alanko J. BD_BWT_index: Bidirectional BWT text index for byte alphabets. 2016. https:\/\/github.com\/jnalanko\/BD_BWT_index . Accessed 06 Oct 2016."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-017-1466-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,25]],"date-time":"2017-06-25T12:34:36Z","timestamp":1498394076000},"score":1,"resource":{"primary":{"URL":"http:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-017-1466-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3]]},"references-count":45,"journal-issue":{"issue":"S3","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["1466"],"URL":"https:\/\/doi.org\/10.1186\/s12859-017-1466-6","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3]]},"article-number":"59"}}