Classification of DNA sequences using Bloom filters.

Stranneheim H, Käller M, Allander T, Andersson B, Arvestad L, Lundeberg J

Bioinformatics 26 (13) 1595-1600 [2010-07-01; online 2010-05-18]

New generation sequencing technologies producing increasingly complex datasets demand new efficient and specialized sequence analysis algorithms. Often, it is only the 'novel' sequences in a complex dataset that are of interest and the superfluous sequences need to be removed. A novel algorithm, fast and accurate classification of sequences (FACSs), is introduced that can accurately and rapidly classify sequences as belonging or not belonging to a reference sequence. FACS was first optimized and validated using a synthetic metagenome dataset. An experimental metagenome dataset was then used to show that FACS achieves comparable accuracy as BLAT and SSAHA2 but is at least 21 times faster in classifying sequences. Source code for FACS, Bloom filters and MetaSim dataset used is available at The Bloom::Faster 1.6 Perl module can be downloaded from CPAN at approximately palvaro/Bloom-Faster-1.6/; Supplementary data are available at Bioinformatics online.

NGI Stockholm (Genomics Applications)

NGI Stockholm (Genomics Production)

QC bibliography QC xrefs

PubMed 20472541

DOI 10.1093/bioinformatics/btq230

Crossref 10.1093/bioinformatics/btq230


pmc PMC2887045