API文档可在 https://docs.rs/sbwt/latest/sbwt/ 查找。

lib.rs:

简介

此包包含对位矩阵SBWT数据结构的实现，该实现描述在《通过子集秩查询光谱Burrow-Wheeler变换的小型可搜索k-谱》中，用于DNA字母表ACGT。库的主要功能可以通过https://github.com/jnalanko/sbwt-rs-cli找到。该数据结构使用Burrows-Wheeler变换的变体以压缩k-mer集合，允许快速查找查询。如果输入k-mer是较长底层序列中的连续k-mer，则索引通常占用大约每个不同的k-mer5位，在现代硬件上支持约1 μs / k-mer的k-mer查找查询速度。

通过使用最长公共后缀数组可以进一步加快查询速度，（见此处），每个k-mer大约需要log(k)位空间。LCS数组还使计算k-bounded匹配统计和最短频率限制后缀（两者均描述此处）成为可能。最后，该包提供了一个接口，用于遍历k-mer的以节点为中心的De Bruijn图。

API快速入门

use sbwt::*;
use std::io::BufReader;
use std::io::BufWriter;
use std::fs::File;
use std::path::Path;

// Build the sbwt
let seqs: Vec<&[u8]> = vec![b"AACTGACTGATCGTCTTGACTCGTTTATCTACGGT", b"ACTGACAGCTCTGCGATGCGA"];
let seq_stream = sbwt::SliceSeqStream::new(seqs.as_slice());
let (sbwt, lcs) = SbwtIndexBuilder::new()
    .k(6).n_threads(4).build_lcs(true).add_rev_comp(true)
    .algorithm(BitPackedKmerSorting::new()
        .mem_gb(2)
        .dedup_batches(false)
        .temp_dir(Path::new("./temp")))
    .run(seq_stream);

// Query a k-mer
let query_kmer = b"GACTCG";
if sbwt.search(query_kmer).is_some() {
    println!("{} is found", &String::from_utf8_lossy(query_kmer));
}

// Query all k-mers of a longer query using k-bounded matching statistics
let lcs = lcs.unwrap(); // Ok because we used build_lcs(true)
let streaming_index = StreamingIndex::new(&sbwt, &lcs);
let long_query = b"TGATACGTCTTAGTGACTCGTTT";
for (i, (len, range)) in streaming_index.matching_statistics(long_query).iter().enumerate() {
    // Kmer ending at long_query[i] exists iff len == k
    println!("Longest match ending at {} has length {} and colex range {:?}", i, len, range);
}

// Write index to disk for later use
sbwt.serialize(&mut BufWriter::new(File::create("index.sbwt").unwrap())).unwrap();
lcs.serialize(&mut BufWriter::new(File::create("index.lcs").unwrap())).unwrap();

反向互补和输入预处理

如果您的输入非常大，您可能希望对其进行预处理以删除重复的k-mer，以减少构建时间、内存和磁盘空间。我们建议使用专门的工具，例如GGCAT、Cuttlefish或BCALM2来完成此操作。

这个软件包将k-mer与其反向互补序列视为不同。在使用k-mer与其反向互补序列视为相同的情况下，您需要将两个方向的序列都输入到索引中，或者只输入一个方向的序列，但每个k-mer都要以两种方式进行查询。前者可以通过在构建器中启用反向互补序列来轻松实现。对于后者，我们建议使用上面提到的单元组装工具之一，将数据转换为仅包含每个k-mer一种方向的规范单元组装。在此之后，非常重要的是，通过重新定位单元组装来保持相邻k-mer的一致方向，因为如此处所述，每个没有直接前驱的k-mer都会增加索引大小。这种方法的回报是，与明确索引两个方向的索引大小最多减少两倍，但缺点是现在查询需要以两种方向进行。

De Bruijn图操作

通过添加两个额外的位向量，该数据结构支持在输入k-mer的以节点为中心的De Bruijn图上进行遍历。节点集是不同的k-mer集合，如果x[1..k) = y[0..k-1)，则存在从x到y的边。边的标签是y的最后字符。该图不了解反向互补序列，因此如果您想遍历包含一个或两个端点反向互补的定向双向De Bruijn图中的边，您需要自己处理该逻辑。有关API的信息，请参阅Dbg。

构建算法

该软件包目前提供了一个构建算法：位打包k-mer排序。该算法提取输入中的所有k-mer，将每个k-mer打包到2k位，并并行排序。这需要O(nk)时间和磁盘空间，因此只适用于较小的k值。在实现中还有许多优化空间。对于较大的k值，计划使用基于后缀数组的构建算法。

关于索引空间使用的详细信息

该索引利用k-mer之间的重叠来以较小的空间编码它们。我们说k-mer x是源k-mer，如果它在输入k-mer的以节点为中心的De Bruijn图中没有入边，也就是说，不存在k-mer y ∈ S，使得y[1..k) = x[0..k-1)。在SbwtIndex<SubsetMatrix>中的位数是5(n + n')加上一个小的常数，其中n是数据集中不同k-mer的数量，n'是所有源k-mer长度为k-1的所有前缀的trie中的节点数量（有关SBWT内部工作原理的更多详细信息，请参阅此处）。当k-mer来自生物序列，并且单元组装是一致定位时，n'通常可以忽略不计，但如果k-mer是例如随机采样的子集，那么重叠的好处就会丢失，n'项将占主导地位。在最坏的情况下，n'可以达到n(k-1) + 1。

限制

实现仅支持DNA字母表ACGT。为了获得最佳压缩，输入k-mer应来自较长的底层序列，这样sbwt能够利用重叠以获得更好的压缩。对于非重叠k-mer集合，简单的哈希表可能是一个更好的选择。