ArticleAlgorithms for molecular biology : AMB2016
Bloom Filter Trie: an alignment-free and reference-free data structure for pan-genome storage.
Article in Algorithms for molecular biology : AMB, 2016. The graph could read no effect estimate from its abstract, so it casts no vote on the map. Cited by 30 papers, 1 of them a synthesis that pooled it.
What it found
Each row is one number read from the abstract, on the scale the paper reported it, with its interval. Left of the dashed line favours the treatment, right favours the comparator. Under each row is the sentence it came from. New to these charts? A ten-minute tutorial.
The abstract states no effect estimate the extractor could read, or names no intervention and outcome on the map, so this paper lights no cell and moves no belief. It is still indexed, cited and linked below.
The trial behind it
Trials whose registry record cites this paper, or whose number appears in the abstract. A trial that started after this paper was published is citing it as background, not reporting it.
Neither the registry nor the abstract names a trial number. If this is a trial report, that itself is worth knowing.
Who cites it
30 citing papers in PubMed, 1 synthesis or guideline pooled it.
- Vertical lossless genomic data compression tools for assembled genomes: A systematic literature review.PloS one · 2020Pooled it
- Conway-Bromage-Lyndon (CBL): an exact, dynamic representation of k-mer sets.Bioinformatics (Oxford, England) · 2024Article
- DNA Bloom Filter enables anti-contamination and file version control for DNA-based data storage.Briefings in bioinformatics · 2024Article
- PanKmer: k-mer-based and reference-free pangenome analysis.Bioinformatics (Oxford, England) · 2023Article
- Scalable sequence database search using partitioned aggregated Bloom comb trees.Bioinformatics (Oxford, England) · 2023Article
- Data Structures to Represent a Set ofACM computing surveys · 2022Article
- Succinct dynamic de Bruijn graphs.Bioinformatics (Oxford, England) · 2021Article
- Cuttlefish: fast, parallel and low-memory compaction of de Bruijn graphs from large-scale genome collections.Bioinformatics (Oxford, England) · 2021Article
- A variant selection framework for genome graphs.Bioinformatics (Oxford, England) · 2021Article
- A tri-tuple coordinate system derived for fast and accurate analysis of the colored de Bruijn graph-based pangenomes.BMC bioinformatics · 2021Article
- Simplitigs as an efficient and scalable representation of de Bruijn graphs.Genome biology · 2021Article
- Representation ofJournal of computational biology : a journal of computational molecular cell biology · 2021Article
- Buffering updates enables efficient dynamic de Bruijn graphs.Computational and structural biotechnology journal · 2021Article
- Data structures based onGenome research · 2021Review
- REINDEER: efficient indexing of k-mer presence and abundance in sequencing datasets.Bioinformatics (Oxford, England) · 2020Article
- Pan-genomics in the human genome era.Nature reviews. Genetics · 2020Review
- An Efficient, Scalable, and Exact Representation of High-Dimensional Color Information Enabled Using de Bruijn Graph Search.Journal of computational biology : a journal of computational molecular cell biology · 2020Article
- Alignment- and reference-free phylogenomics with colored de Bruijn graphs.Algorithms for molecular biology : AMB · 2020Article
- Building large updatable colored de Bruijn graphs via merging.Bioinformatics (Oxford, England) · 2019Article
- Alignment-free inference of hierarchical and reticulate phylogenomic relationships.Briefings in bioinformatics · 2019Review
Corrections and comments
PubMed lists nothing against this paper. Absence here is not a guarantee, only a check that was made.
Authors and funding
3 authors.
Funding
No grant is acknowledged in the PubMed record.
Abstract
backgroundHigh throughput sequencing technologies have become fast and cheap in the past years. As a result, large-scale projects started to sequence tens to several thousands of genomes per species, producing a high number of sequences sampled from each genome. Such a highly redundant collection of very similar sequences is called a pan-genome. It can be transformed into a set of sequences "colored" by the genomes to which they belong. A colored de Bruijn graph (C-DBG) extracts from the sequences all colored k-mers, strings of length k, and stores them in vertices.
resultsIn this paper, we present an alignment-free, reference-free and incremental data structure for storing a pan-genome as a C-DBG: the bloom filter trie (BFT). The data structure allows to store and compress a set of colored k-mers, and also to efficiently traverse the graph. Bloom filter trie was used to index and query different pangenome datasets. Compared to another state-of-the-art data structure, BFT was up to two times faster to build while using about the same amount of main memory. For querying k-mers, BFT was about 52-66 times faster while using about 5.5-14.3 times less memory.
conclusionWe present a novel succinct data structure called the Bloom Filter Trie for indexing a pan-genome as a colored de Bruijn graph. The trie stores k-mers and their colors based on a new representation of vertices that compress and index shared substrings. Vertices use basic data structures for lightweight substrings storage as well as Bloom filters for efficient trie and graph traversals. Experimental results prove better performance compared to another state-of-the-art data structure. AVAILABILITY: https://www.github.com/GuillaumeHolley/BloomFilterTrie.
Indexed as
Identifiers
What OpenQuestion holds
Registered trials
Read under generation 80e0d062 · epoch 390. Bibliography from PubMed, PubMed Central and OpenAlex; grants from NIH RePORTER; trial links from ClinicalTrials.gov; estimates, votes and beliefs from the OpenQuestion graph.