Lib.rs

nucleic-acid

这个 Rust 库包含了一些用于处理 DNA 序列的生物信息学代码。它具有以下实现

• BWT - 使用后缀数组（通过诱导排序方法以 O(n) 空间在 O(n) 时间内构建）生成给定文本的 Burrows-Wheeler 变换。
• FM-Index - 它使用 BWT 在 O(1) 时间内计数/获取子字符串的出现次数。这是序列对齐的基础（注意，它在内存优化方面尚未优化）。
• 位向量 - DNA 序列几乎总是由一串 ATCG 组成。使用 2 位而不是通常的 8 位来表示核苷酸可以节省 大量 内存！BitsVec 为具有已知位范围的通用接口提供了一种方法。

用法

将此内容添加到您的 Cargo.toml

nucleic-acid = "0.1"

有关确切用法和详细示例，请参阅文档。

动机

BWT 和 FM-index 的实现已经由优秀的 rust-bio 库提供。但对于大型数据集（约 4 GB）来说，这并不理想。编写此库是为了有效地处理此类数据集。

基准测试

BitsVec

请注意，BitsVec 比普通的 Vec 慢得多，因为我们不能通过 位 移动指针，因此我们需要进行一些位移和位运算来实现这一点。这至少需要 7-10 次额外的操作（每调用一次函数），包括指针的读写。所以，它 很慢。

bench_1_bits_vec_fill_with_1000_elements  ... bench:       1,961 ns/iter (+/- 142)
bench_1_bits_vec_get_1000_ints            ... bench:      26,429 ns/iter (+/- 281)
bench_1_bits_vec_push_1000_ints           ... bench:       8,574 ns/iter (+/- 1,409)
bench_1_bits_vec_set_1000_ints            ... bench:      31,423 ns/iter (+/- 948)
bench_22_bits_vec_fill_with_1000_elements ... bench:       1,422 ns/iter (+/- 184)
bench_22_bits_vec_get_1000_ints           ... bench:      28,098 ns/iter (+/- 458)
bench_22_bits_vec_push_1000_ints          ... bench:      11,701 ns/iter (+/- 3,853)
bench_22_bits_vec_set_1000_ints           ... bench:      32,632 ns/iter (+/- 1,032)
bench_40_bits_vec_fill_with_1000_elements ... bench:       1,941 ns/iter (+/- 123)
bench_40_bits_vec_get_1000_ints           ... bench:      27,771 ns/iter (+/- 2,613)
bench_40_bits_vec_push_1000_ints          ... bench:      13,475 ns/iter (+/- 5,716)
bench_40_bits_vec_set_1000_ints           ... bench:      32,786 ns/iter (+/- 1,649)
bench_63_bits_vec_fill_with_1000_elements ... bench:       3,078 ns/iter (+/- 273)
bench_63_bits_vec_get_1000_ints           ... bench:      29,247 ns/iter (+/- 2,903)
bench_63_bits_vec_push_1000_ints          ... bench:      20,756 ns/iter (+/- 2,717)
bench_63_bits_vec_set_1000_ints           ... bench:      34,674 ns/iter (+/- 2,819)

如您所注意到的，一旦接近 usize 的大小（在我的情况下，推送 63 位值比推送 22 或 40 位值慢得多），这就会变得效率低下。

suffix_array

由于诱导排序方法是 O(n)，它比通常的 O(nlogn) 排序快得多，并且内存效率也很高。

bench_sort_rotations_1000_random_values         ... bench:     292,912 ns/iter (+/- 24,688)
bench_suffix_array_1000_random_values           ... bench:     100,227 ns/iter (+/- 16,021)

FMIndex

FM-index 在构建和获取时非常快，但它消耗了大量的内存（几乎与后缀数组相同）。有多种方法可以优化这一点（我将在将来尝试这样做）。

bench_fm_index_1000_random_values_constructor   ... bench:     115,514 ns/iter (+/- 20,053)
bench_fm_index_1000_random_values_get_100_chars ... bench:       1,094 ns/iter (+/- 78)