Bloom Filter Trie: an alignment-free and reference-free data structure for pan-genome storage.

Area of Science:

• Genomics
• Bioinformatics
• Data Structures

Background:

• High-throughput sequencing generates vast amounts of genomic data, leading to the concept of pan-genomes.
• Pan-genomes, collections of sequences from multiple individuals of a species, are often represented using colored de Bruijn graphs (C-DBGs).
• C-DBGs store colored k-mers, which are substrings of length k tagged with their genome of origin.

Purpose of the Study:

• To develop a novel, efficient data structure for storing and querying pan-genomes as C-DBGs.
• To present an alignment-free, reference-free, and incremental method for pan-genome indexing.
• To improve upon existing state-of-the-art data structures in terms of speed and memory usage.

Main Methods:

• Introduction of the Bloom Filter Trie (BFT), a succinct data structure.
• BFT utilizes a new vertex representation for compressing and indexing shared substrings within the C-DBG.
• Inclusion of Bloom filters for efficient trie and graph traversals.

Main Results:

• The Bloom Filter Trie (BFT) was used to index and query various pan-genome datasets.
• BFT demonstrated up to two times faster construction compared to a state-of-the-art structure, using similar memory.
• Querying k-mers with BFT was 52-66 times faster and used 5.5-14.3 times less memory.

Conclusions:

• The Bloom Filter Trie (BFT) is a novel and efficient data structure for indexing pan-genomes as C-DBGs.
• BFT offers superior performance in terms of speed and memory efficiency compared to existing methods.
• The proposed structure facilitates effective compression and traversal of large-scale genomic datasets.