Mismatch-tolerant, alignment-free sequence classification using multiple spaced seeds and multiindex Bloom filters

Alignment-free classification tools have enabled high-throughput processing of sequencing data in many bioinformatics analysis pipe-lines primarily due to their computational efficiency. Originally k-mer based, such tools often lack sensitivity when faced with se-quencing errors and polymorphisms. In response, some tools have been augmented with spaced seeds, which are capable of tolerating mismatches. However, spaced seeds have seen little practical use in classification because they bring increased computational and mem-ory costs compared to methods that use k-mers. These limitations have also caused the design and length of practical spaced seeds to be constrained, since storing spaced seeds can be costly. To address these challenges, we have designed a probabilistic data structure called a multiindex Bloom Filter (miBF), which can store multiple spaced seed sequences with a low memory cost that remains static regardless of seed length or seed design. We formalize how to minimize the false-positive rate of miBFs when classifying se-quences from multiple targets or references. Available within Bio-Bloom Tools, we illustrate the utility of miBF in two use cases: read -binning for targeted assembly, and taxonomic read assignment. In our benchmarks, an analysis pipeline based on miBF shows higher sensitivity and specificity for read-binning than sequence alignment -based methods, also executing in less time. Similarly, for taxonomic classification, miBF enables higher sensitivity than a conventional spaced seed-based approach, while using half the memory and an order of magnitude less computational time.