The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Compacting de Bruijn graphs from sequencing data quickly and in low memory
Open accessAbstract
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. 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 GB 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 GB of memory on a single machine. Hence, bcalm 2 is at least an order of magnitude more efficient than other available methods. Availability and Implementation : Source code of bcalm 2 is freely available at: https://github.com/GATB/bcalm Contact: rayan.chikhi@univ-lille1.fr
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A fast, lock-free approach for efficient parallel counting of occurrences of k -mers
Marçais, G., & Kingsford, C. (2011) · Bioinformatics · doi:10.1093/bioinformatics/btr011 · Cited by 4,661
Cited by
Haplotype-resolved diverse human genomes and integrated analysis of structural variation
Ebert, P., Audano, P. A., Zhu, Q., Rodriguez-Martin, B., Porubsky, D., Bonder, M. J., Sulovari, A., Ebler, J., Zhou, W., Serra Mari, R., et al. (2021) · Science · doi:10.1126/science.abf7117 · Cited by 702
ABySS 2.0: resource-efficient assembly of large genomes using a Bloom filter
Jackman, S. D., Vandervalk, B. P., Mohamadi, H., Chu, J., Yeo, S., Hammond, S. A., Jahesh, G., Khan, H., Coombe, L., Warren, R. L., et al. (2017) · Genome Research · doi:10.1101/gr.214346.116 · Cited by 679
The barley pan-genome reveals the hidden legacy of mutation breeding
Jayakodi, M., Padmarasu, S., Haberer, G., Bonthala, V. S., Gundlach, H., Monat, C., Lux, T., Kamal, N., Lang, D., Himmelbach, A., et al. (2020) · Nature · doi:10.1038/s41586-020-2947-8 · Cited by 565
The design and construction of reference pangenome graphs with minigraph
Li, H., Feng, X., & Chu, C. (2020) · Genome Biology · doi:10.1186/s13059-020-02168-z · Cited by 455
TRITEX: chromosome-scale sequence assembly of Triticeae genomes with open-source tools
Monat, C., Padmarasu, S., Lux, T., Wicker, T., Gundlach, H., Himmelbach, A., Ens, J., Li, C., Muehlbauer, G. J., Schulman, A. H., et al. (2019) · Genome Biology · doi:10.1186/s13059-019-1899-5 · Cited by 251
Metadata
- Authors
- Chikhi, R., Limasset, A., & Medvedev, P.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2016-06-11
- Volume
- 32
- Issue
- 12
- Pages
- i201-i208
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2438121987
- Cited by
- 228
- References
- 1
- FWCI
- 6.62
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.