Needle: a fast and space-efficient prefilter for estimating the quantification of very large collections of
Mitra Darvish1, Enrico Seiler1,2, Svenja Mehringer2
1Efficient Algorithms for Omics Data, Max Planck Institute for Molecular Genetics, Berlin, Germany.
Motivation:
The ever-growing size of sequencing data is a major bottleneck in bioinformatics as the advances of hardware development cannot keep up with the data growth. Therefore, an enormous amount of data is collected but rarely ever reused, because it is nearly impossible to find meaningful experiments in the stream of raw data.
Results:
As a solution, we propose Needle, a fast and space-efficient index which can be built for thousands of experiments in <2 h and can estimate the quantification of a transcript in these experiments in seconds, thereby outperforming its competitors. The basic idea of the Needle index is to create multiple interleaved Bloom filters that each store a set of representative k-mers depending on their multiplicity in the raw data. This is then used to quantify the query.
Availability And Implementation:
https://github.com/seqan/needle.
Supplementary Information:
Supplementary data are available at Bioinformatics online.
