As sequencing technology improves, our genomic datasets are now larger than ever before. To extract valuable information from this data, it is crucial to be able to store and query it efficiently. This is especially true of pan-genomes, which are a redundant collection of similar sequencing reads, often extracted from members of the same species. Since most of the base pairs in these sequences are identical, pan-genomes are a prime candidate for compression. One method, proposed by Holley et al [1] uses a data structure called the Bloom Filter Trie (BFT) to compress, store, and query pan-genomes. The BFT essentially represents and compresses a Colored De Bruijn Graph (C-DBG), using Bloom Filters and Burst Tries to store k-mers from pan-genomic sequences.
This repository is my implementation of the Bloom Filter Trie, as described by Holley et al 2016.
- This project uses Maven to build and run
- To install the project, run
./install.sh - To run a basic benchmarking of BFT against HashMap and ArrayList, run
./run_benchmarks.sh - To run the BFT algorithm on all the queries stored in the
querydirectory, run./run_bft.sh - Datasets of varying sizes are stored in the
dbdirectory, and sample queries are stored in thequerydirectory- To run the programs on a different dataset, update the BASH script by changing
./db/test-midand./query/test1to your liking
- To run the programs on a different dataset, update the BASH script by changing
The data provided in the db directory are sequences taken from various strains of E. coli.
db/test-xlargeare the full genomes of 10 different E. coli strains (warning: I have not completed a test on this yet)db/test-largeare the first ~6-10kb base-pairs from the genomes of 10 different E. coli strainsdb/test-medare the first ~300-500 base-pairs from the genomes of 10 different E. coli strainsdb/test-smallare the first ~100 base-pairs from the genomes of 10 different E. coli strainsdb/test-xsmallare the 12 base-pair sequences shown in the figures from Holley et al. 2016