{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,27]],"date-time":"2026-07-27T10:33:21Z","timestamp":1785148401987,"version":"3.55.0"},"reference-count":38,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,28]],"date-time":"2016-10-28T00:00:00Z","timestamp":1477612800000},"content-version":"vor","delay-in-days":139,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation : As the quantity of data per sequencing experiment increases, the challenges of fragment assembly are becoming increasingly computational. The de Bruijn graph is a widely used data structure in fragment assembly algorithms, used to represent the information from a set of reads. Compaction is an important data reduction step in most de Bruijn graph based algorithms where long simple paths are compacted into single vertices. Compaction has recently become the bottleneck in assembly pipelines, and improving its running time and memory usage is an important problem.<\/jats:p>\n               <jats:p>Results : We present an algorithm and a tool bcalm 2 for the compaction of de Bruijn graphs. bcalm 2 is a parallel algorithm that distributes the input based on a minimizer hashing technique, allowing for good balance of memory usage throughout its execution. For human sequencing data, bcalm 2 reduces the computational burden of compacting the de Bruijn graph to roughly an hour and 3\u2009GB of memory. We also applied bcalm 2 to the 22 Gbp loblolly pine and 20 Gbp white spruce sequencing datasets. Compacted graphs were constructed from raw reads in less than 2 days and 40\u2009GB of memory on a single machine. Hence, bcalm 2 is at least an order of magnitude more efficient than other available methods.<\/jats:p>\n               <jats:p>Availability and Implementation : Source code of bcalm 2 is freely available at: https:\/\/github.com\/GATB\/bcalm<\/jats:p>\n               <jats:p>Contact: \u00a0rayan.chikhi@univ-lille1.fr<\/jats:p>","DOI":"10.1093\/bioinformatics\/btw279","type":"journal-article","created":{"date-parts":[[2016,6,15]],"date-time":"2016-06-15T15:43:52Z","timestamp":1466005432000},"page":"i201-i208","source":"Crossref","is-referenced-by-count":222,"title":["Compacting de Bruijn graphs from sequencing data quickly and in low memory"],"prefix":"10.1093","volume":"32","author":[{"given":"Rayan","family":"Chikhi","sequence":"first","affiliation":[{"name":"1 CNRS, CRIStAL, Lille, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Antoine","family":"Limasset","sequence":"additional","affiliation":[{"name":"2 ENS Cachan Brittany, Bruz, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Medvedev","sequence":"additional","affiliation":[{"name":"3 Department of Computer Science and Engineering, The Pennsylvania State University, USA"},{"name":"4 Department of Biochemistry and Molecular Biology, The Pennsylvania State University, USA"},{"name":"5 Genome Sciences Institute of the Huck, The Pennsylvania State University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2016,6,11]]},"reference":[{"key":"2023020112315581000_btw279-B1","doi-asserted-by":"crossref","first-page":"1492","DOI":"10.1093\/bioinformatics\/btt178","article-title":"Assembling the 20\u2009gb white spruce (\n              Picea glauca\n              ) genome from whole-genome shotgun sequencing data","volume":"29","author":"Birol","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020112315581000_btw279-B2","doi-asserted-by":"crossref","first-page":"1519","DOI":"10.1089\/cmb.2009.0238","article-title":"Ray: simultaneous assembly of reads from a mix of high-throughput sequencing technologies","volume":"17","author":"Boisvert","year":"2010","journal-title":"J. Comput. Biol"},{"key":"2023020112315581000_btw279-B3","first-page":"236","volume-title":"WABI","author":"Chikhi","year":"2012"},{"key":"2023020112315581000_btw279-B4","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/978-3-319-05269-4_4","volume-title":"In: Research in Computational Molecular Biology","author":"Chikhi","year":"2014"},{"key":"2023020112315581000_btw279-B5","volume-title":"Introduction to Algorithms","author":"Cormen","year":"2009"},{"key":"2023020112315581000_btw279-B6","article-title":"Kmc 2: Fast and resource-frugal \n              k\n              -mer counting","author":"Deorowicz","year":"2014","journal-title":"arXiv Preprint arXiv"},{"key":"2023020112315581000_btw279-B7","doi-asserted-by":"crossref","first-page":"2959","DOI":"10.1093\/bioinformatics\/btu406","article-title":"GATB: genome assembly & analysis tool box","volume":"30","author":"Drezen","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020112315581000_btw279-B8","author":"Duan","year":"2014"},{"key":"2023020112315581000_btw279-B9","author":"Garg","year":"2013"},{"key":"2023020112315581000_btw279-B10","author":"Georganas","year":"2014"},{"key":"2023020112315581000_btw279-B11","author":"Georganas","year":"2015"},{"key":"2023020112315581000_btw279-B12","doi-asserted-by":"crossref","first-page":"1513","DOI":"10.1073\/pnas.1017351108","article-title":"High-quality draft assemblies of mammalian genomes from massively parallel sequence data","volume":"108","author":"Gnerre","year":"2011","journal-title":"PNAS"},{"key":"2023020112315581000_btw279-B13","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1038\/nbt.1883","article-title":"Full-length transcriptome assembly from RNA-Seq data without a reference genome","volume":"29","author":"Grabherr","year":"2011","journal-title":"Nat. Biotechnol"},{"key":"2023020112315581000_btw279-B14","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1038\/ng.1028","article-title":"De novo assembly and genotyping of variants using colored de Bruijn graphs","volume":"44","author":"Iqbal","year":"2012","journal-title":"Nat. Genet"},{"key":"2023020112315581000_btw279-B15","author":"Jackson","year":"2008"},{"key":"2023020112315581000_btw279-B16","author":"Jackson","year":"2010"},{"key":"2023020112315581000_btw279-B17","author":"Kececioglu","year":"1992"},{"key":"2023020112315581000_btw279-B18","doi-asserted-by":"crossref","first-page":"e75505.","DOI":"10.1371\/journal.pone.0075505","article-title":"Comparing memory-efficient genome assemblers on stand-alone and cloud infrastructures","volume":"8","author":"Kleftogiannis","year":"2013","journal-title":"PloS One"},{"key":"2023020112315581000_btw279-B19","doi-asserted-by":"crossref","first-page":"560.","DOI":"10.1186\/1471-2105-11-560","article-title":"Efficient parallel and out of core algorithms for constructing large bi-directed de Bruijn graphs","volume":"11","author":"Kundeti","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023020112315581000_btw279-B20","doi-asserted-by":"crossref","first-page":"169","DOI":"10.14778\/2535569.2448951","article-title":"Memory efficient minimum substring partitioning","volume":"6","author":"Li","year":"2013","journal-title":"Proc. VLDB Endowment"},{"key":"2023020112315581000_btw279-B21","doi-asserted-by":"crossref","first-page":"977","DOI":"10.1109\/TPDS.2012.190","article-title":"Pasqual: parallel techniques for next generation genome sequence assembly","volume":"24","author":"Liu","year":"2013","journal-title":"IEEE Trans. Parallel Distributed Syst"},{"key":"2023020112315581000_btw279-B22","doi-asserted-by":"crossref","first-page":"354.","DOI":"10.1186\/1471-2105-12-354","article-title":"Parallelized short read assembly of large genomes using de bruijn graphs","volume":"12","author":"Liu","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023020112315581000_btw279-B23","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/978-3-642-37401-2_8","volume-title":"Web Technologies and Applications","author":"Lu","year":"2013"},{"key":"2023020112315581000_btw279-B24","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1186\/2047-217X-1-18","article-title":"SOAPdenovo2: an empirically improved memory-efficient short-read de novo assembler","volume":"1","author":"Luo","year":"2012","journal-title":"GigaScience"},{"key":"2023020112315581000_btw279-B25","doi-asserted-by":"crossref","first-page":"764","DOI":"10.1093\/bioinformatics\/btr011","article-title":"A fast, lock-free approach for efficient parallel counting of occurrences of k-mers","volume":"27","author":"Mar\u00e7ais","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020112315581000_btw279-B26","first-page":"289","article-title":"Computability of models for sequence assembly","author":"Medvedev","year":"2007","journal-title":"WABI"},{"key":"2023020112315581000_btw279-B27","doi-asserted-by":"crossref","first-page":"333.","DOI":"10.1186\/1471-2105-12-333","article-title":"Efficient counting of k-mers in DNA sequences using a Bloom filter","volume":"12","author":"Melsted","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023020112315581000_btw279-B28","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/978-3-642-35606-3_17","volume-title":"Network and Parallel Computing","author":"Meng","year":"2012"},{"key":"2023020112315581000_btw279-B29","volume-title":"RECOMB-Seq 2014","author":"Meng","year":"2014"},{"key":"2023020112315581000_btw279-B30","doi-asserted-by":"crossref","first-page":"2189","DOI":"10.1109\/TPDS.2012.80","article-title":"A framework for scalable genome assembly on clusters, clouds, and grids","volume":"23","author":"Moretti","year":"2012","journal-title":"IEEE Trans. Parallel Distributed Syst"},{"key":"2023020112315581000_btw279-B31","first-page":"1","volume-title":"IEEE BIBM 2012","author":"Movahedi","year":"2012"},{"key":"2023020112315581000_btw279-B32","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1093\/bioinformatics\/btt020","article-title":"DSK: k-mer counting with very low memory usage","volume":"29","author":"Rizk","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020112315581000_btw279-B33","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1101\/gr.131383.111","article-title":"GAGE: a critical evaluation of genome assemblies and assembly algorithms","volume":"22","author":"Salzberg","year":"2011","journal-title":"Genome Res"},{"key":"2023020112315581000_btw279-B34","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1101\/gr.089532.108","article-title":"ABySS: a parallel assembler for short read sequence data","volume":"19","author":"Simpson","year":"2009","journal-title":"Genome Res"},{"key":"2023020112315581000_btw279-B35","doi-asserted-by":"crossref","first-page":"S18.","DOI":"10.1186\/1471-2105-13-S19-S18","article-title":"Tiger: tiled iterative genome assembler","volume":"13","author":"Wu","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023020112315581000_btw279-B36","doi-asserted-by":"crossref","first-page":"S1.","DOI":"10.1186\/1471-2105-13-S6-S1","article-title":"Exploiting sparseness in de novo genome assembly","volume":"13","author":"Ye","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023020112315581000_btw279-B37","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1007\/978-3-642-37401-2_12","volume-title":"Web Technologies and Applications","author":"Zeng","year":"2013"},{"key":"2023020112315581000_btw279-B38","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1534\/genetics.113.159715","article-title":"Sequencing and assembly of the 22-gb loblolly pine genome","volume":"196","author":"Zimin","year":"2014","journal-title":"Genetics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/12\/i201\/49021929\/bioinformatics_32_12_i201.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/12\/i201\/49021929\/bioinformatics_32_12_i201.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T22:38:25Z","timestamp":1675291105000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/12\/i201\/2289008"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,11]]},"references-count":38,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2016,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw279","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,6,15]]},"published":{"date-parts":[[2016,6,11]]}}}