We present COBS, a compact bit-sliced signature index, which is a cross-over between an inverted index and Bloom filters. Our target application is to index @math -mers of DNA samples or @math -grams from text documents and process approximate pattern matching queries on the corpus with a user-chosen coverage threshold. Query results may contain a number of false positives which decreases exponentially with the query length and the false positive rate of the index determined at construction time. We compare COBS to seven other index software packages on 100 000 microbial DNA samples. COBS' compact but simple data structure outperforms the other indexes in construction time and query performance with Mantis by on second place. However, different from Mantis and other previous work, COBS does not need the complete index in RAM and is thus designed to scale to larger document sets.
The currently most cited line of work on DNA @math -mer indices for approximate search are the Sequence Bloom Trees (SBTs) first proposed by Solomon and Kingsford @cite_16 . In an SBT the @math -mers of each document are individually indexed into a Bloom filter, which are then arranged as the leaves of a binary tree. The inner nodes of the binary tree are union Bloom filters of their descendants. A query can then breadth-first traverse the tree pruning search paths which no longer sufficiently cover a given threshold @math of the query @math -mers.
@cite_16
2266239166
A data indexing method enables fast and computationally efficient searching of short-read sequencing archives.