Skip to main content
Join the official 2019 Python Developers SurveyStart the survey!

Compact Bit-Sliced Signature Index (COBS)

Project description

Compact Bit-Sliced Signature Index (COBS)

COBS (COmpact Bit-sliced Signature index) is a cross-over between an inverted index and Bloom filters. Our target application is to index k-mers of DNA samples or q-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. COBS' compact but simple data structure outperforms other indexes in construction time and query performance with Mantis by Pandey et al. in second place. However, unlike Mantis and other previous work, COBS does not need the complete index in RAM and is thus designed to scale to larger document sets.

cobs-architecture

COBS has two interfaces:

More information about COBS is presented in our current research paper: Timo Bingmann, Phelim Bradley, Florian Gauger, and Zamin Iqbal. "COBS: a Compact Bit-Sliced Signature Index". In: 26th International Symposium on String Processing and Information Retrieval (SPIRE). pages 285-303. Spinger. October 2019. preprint arXiv:1905.09624.

Installation and First Steps

Installation

COBS requires CMake, a C++17 compiler or the Boost.Filesystem library.

To download and install COBS run:

git clone --recursive https://github.com/bingmann/cobs.git
mkdir cobs/build
cd cobs/build
cmake ..
make -j4

and optionally run make test to check the build.

Building an Index

COBS can read FASTA files (*.fa, *.fasta, *.fa.gz, *.fasta.gz), FASTQ files (*.fq, *.fastq, *.fq.gz., *.fastq.gz), McCortex files (*.ctx), or text files (*.txt).

You can either recursively scan a directory for all files matching any of these files, or pass a *.list file which lists all paths COBS should index.

To check the document list to be indexed, run for example

src/cobs doc-list tests/data/fasta/

To construct a compact COBS index from these seven example documents run

src/cobs compact-construct tests/data/fasta/ example.cobs_compact

Check --help for many options.

Query an Index

COBS has a simple command line query tool:

src/cobs query -i example.cobs_compact AGTCAACGCTAAGGCATTTCCCCCCTGCCTCCTGCCTGCTGCCAAGCCCT

or a fasta file of queries with

src/cobs query -i example.cobs_compact -f query.fa

Python Interface

COBS also has a Python frontend interface which can be used to construct and query an index. See https://bingmann.github.io/cobs-python-docs/ for a tutorial.

Experimental Results

In our paper we compare COBS against seven other k-mer indexing software packages. These are the main results, scaling by number of documents in the index, and in the second diagram shown per document.

cobs-experiments-scaling cobs-experiments-scaling-per-documents

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for cobs-index, version 0.1.2
Filename, size File type Python version Upload date Hashes
Filename, size cobs_index-0.1.2-cp27-cp27m-manylinux2010_x86_64.whl (975.1 kB) File type Wheel Python version cp27 Upload date Hashes View hashes
Filename, size cobs_index-0.1.2-cp27-cp27mu-manylinux2010_x86_64.whl (975.1 kB) File type Wheel Python version cp27 Upload date Hashes View hashes
Filename, size cobs_index-0.1.2-cp34-cp34m-manylinux2010_x86_64.whl (974.3 kB) File type Wheel Python version cp34 Upload date Hashes View hashes
Filename, size cobs_index-0.1.2-cp35-cp35m-manylinux2010_x86_64.whl (974.4 kB) File type Wheel Python version cp35 Upload date Hashes View hashes
Filename, size cobs_index-0.1.2-cp36-cp36m-manylinux2010_x86_64.whl (974.4 kB) File type Wheel Python version cp36 Upload date Hashes View hashes
Filename, size cobs_index-0.1.2-cp37-cp37m-manylinux2010_x86_64.whl (974.6 kB) File type Wheel Python version cp37 Upload date Hashes View hashes
Filename, size cobs_index-0.1.2-cp38-cp38-manylinux2010_x86_64.whl (971.8 kB) File type Wheel Python version cp38 Upload date Hashes View hashes
Filename, size cobs_index-0.1.2.tar.gz (2.7 MB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page