bloomfilter

The BTL C/C++ Common Bloom filters for bioinformatics projects, as well as any APIs created for other programming languages.

Build Status

usage example (C++)

Fast Bloom filter loading using the rolling hash function.

#include "BloomFilter.hpp"
#include <vector>
#include <string>
#include "vendor/ntHashIterator.hpp"

using namespace std;

int main(int argc, char** argv)
{
    /* test sequence */
    const string seq = "TAGAATCACCCAAAGA";
    /* k-mer size */
    const unsigned k = 5;
    /* number of Bloom filter hash functions */
    const unsigned numHashes = 4;
    /* size of Bloom filter (in bits) */
    const unsigned size = 1000;
    //Building the filter
    {
        /* init Bloom filter */
        BloomFilter bloom(size, numHashes, k);

        /* init rolling hash state and compute hash values for first k-mer */
        ntHashIterator itr(seq, numHashes, k);
        while (itr != itr.end()) {
            bloom.insert(*itr);
            ++itr;
        }
        /* store the bloom filter */
        bloom.storeFilter("filterPathname.bf");
    }

    //After building
    {
        /* load the bloom filter */
        BloomFilter bloom("filterPathname.bf");

        /* query the bloom filter */

        /* init rolling hash state and compute hash values for first k-mer */
        ntHashIterator itr(seq, numHashes, k);
        while (itr != itr.end()) {
            bloom.contains(*itr);
            ++itr;
        }
    }
    return 0;
}

Fast Counting Bloom filter loading using the rolling hash function.

#include "CountingBloomFilter.hpp"
#include <vector>
#include <string>
#include "vendor/ntHashIterator.hpp"

using namespace std;

int main(int argc, char** argv)
{
    /* test sequence */
    const string seq = "TAGAATCACCCAAAGA";
    /* k-mer size */
    const unsigned k = 5;
    /* number of Bloom filter hash functions */
    const unsigned numHashes = 4;
    /* size of Bloom filter (in bytes) */
    size_t size = 1000;
    /* counts to threshold bloom filter on*/
    const unsigned threshold = 1;
    //Building the filter
    {
        /* init Bloom filter */
        CountingBloomFilter<uint8_t> bloom(size, numHashes, k, threshold);

        /* init rolling hash state and compute hash values for first k-mer */
        ntHashIterator itr(seq, numHashes, k);
        while (itr != itr.end()) {
            bloom.insert(*itr);
            ++itr;
        }
        /* store the bloom filter */
        bloom.storeFilter("filterPathname.bf");
    }

    //After building
    {
        /* load the bloom filter */
        CountingBloomFilter<uint8_t> bloom("filterPathname.bf", threshold);

        /* query the bloom filter */

        /* init rolling hash state and compute hash values for first k-mer */
        ntHashIterator itr(seq, numHashes, k);
        while (itr != itr.end()) {
            bloom.contains(*itr);
            ++itr;
        }
    }
    return 0;
}

files

• BloomFilter.hpp: main Bloom filter class
• CountingBloomFilter.hpp: Counting Bloom filter class
• RollingHashIterator.h: Enable rolling hashing on a string
• RollingHash.h: rolling hash interface (required by RollingHashIterator.h)
• rolling.h: rolling hash function (required by BloomFilter.hpp and RollingHash.h)
• Tests/Unit: unit tests
• Tests/AdHoc: ad-hoc tests

unit tests

The unit tests may be compiled and run with:

$ ./autogen.sh
$ ./configure
$ make check

To see more detailed output for the individual tests, run the binaries in Tests/Unit from the command line. (The ad-hoc tests in Tests/AdHoc may also be run in this way.)

acknowledgements

This projects uses:

• CATCH unit test framework for C/C++
• nthash rolling hash implementation by Hamid Mohamadi
• cpptoml TOML parser and serializer implemented by Chase Geigle

Bloom filter file format

The specification of the Bloom filter file format is as follows:

1. magic header string
   • Description: bf magic string
   • Type: string
   • Value: BTLBloomFilter_v1 or BTLCountingBloomFilter_v1
2. header
   • Description: Plain header text
   • Type: string
   • Value:
   • size
     • Description: The size of Bloom filter
     • Type: size_t
     • Value:
   • sizeInBytes
     • Description: The size of Bloom filter in bytes
     • Type: size_t
     • Value:
   • hashNum
     • Description: number of hashes
     • Type: unsigned
     • Value:
   • kmerSize
     • Description: k-mer size
     • Type: unsigned
     • Value:
   • dFPR [optional]
     • Description: desired false positve rate
     • Type: double
     • Value:
   • nEntry [optional]
     • Description: number of entries
     • Type: uint64_t
     • Value:
   • tEntry [optional]
     • Description: total number of entries
     • Type: uint64_t
     • Value:
   • seed [optional] (Not yet implimented)
     • Description: initial seeds for different hashes
     • Type: uint64_t[nhash]
     • Value: [0,1, ..., nhash-1]
   • bitsPerCounter [optional]
     • Description: bits per each counter in the counting bloom filter
     • Type: unsigned
     • Value: 8
3. filter
   • Description: Bloom filter content
   • Type: uchar[sizeInBytes]
   • Value: