紧凑位切片签名索引 (COBS)

COBS（压缩位切片签名索引）是倒排索引和布隆过滤器之间的交叉。我们的目标应用是从文本文档中索引 DNA 样本或 q-gram 的 k-mers，并在具有用户选择的覆盖阈值的语料库上处理近似模式匹配查询。查询结果可能包含一些误报，这些误报随着查询长度和构建时确定的索引的误报率呈指数下降。COBS 紧凑而简单的数据结构在构建时间和查询性能方面优于 Pandey 等人的 Mantis 的其他索引。位居第二。但是，与 Mantis 和其他先前的工作不同，COBS 不需要 RAM 中的完整索引，因此旨在扩展到更大的文档集。

COBS 有两个接口：

• 在 C++ 中调用的命令行工具cobs（见下文）
• C++ 库的 Python 接口（参见https://bingmann.github.io/cobs-python-docs/）

有关 COBS 的更多信息，请参阅我们当前的研究论文：Timo Bingmann、Phelim Bradley、Florian Gauger 和 Zamin Iqbal。“COBS：紧凑的位切片签名索引”。在：第 26 届字符串处理和信息检索 (SPIRE) 国际研讨会上。第 285-303 页。斯宾格。2019 年 10 月。预印本 arXiv:1905.09624。

安装和第一步

安装

COBS 需要 CMake、C++17 编译器或 Boost.Filesystem 库。

要下载并安装 COBS，请运行：

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

并可选择运行make test以检查构建。

建立索引

COBS 可以读取 FASTA 文件 ( *.fa, *.fasta, *.fa.gz, *.fasta.gz)、FASTQ 文件 ( *.fq, *.fastq, *.fq.gz., *.fastq.gz)、McCortex 文件 ( *.ctx) 或文本文件 ( *.txt)。

您可以递归地扫描目录以查找与这些文件中的任何一个匹配的所有文件，或者传递一个*.list列出 COBS 应索引的所有路径的文件。

要检查要索引的文档列表，例如运行

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

要从这七个示例文档构建一个紧凑的 COBS 索引，请运行

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

检查--help许多选项。

查询索引

COBS 有一个简单的命令行查询工具：

src/cobs query -i example.cobs_compact AGTCAACGCTAAGGCATTTCCCCCCTGCCTCCTGCCTGCTGCCAAGCCCT

或查询的fasta文件

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

Python 接口

COBS 还有一个 Python 前端接口，可用于构建和查询索引。有关教程，请参阅https://bingmann.github.io/cobs-python-docs/。

实验结果

在我们的论文中，我们将 COBS 与其他七个 k-mer 索引软件包进行了比较。这些是主要结果，按索引中的文档数量缩放，并且在每个文档显示的第二个图表中。