COITrees: 缓存无关区间树

COITrees实现了一个数据结构，用于对静态整数区间集合进行快速重叠查询，主要考虑基因组区间。

借鉴cgranges，此数据结构在连续内存中存储区间，但通过将节点存储在顺序的van Emde Boas布局中提高了查询性能。计算布局需要一些额外的时间和内存，但提高了查询树的平均缓存局部性。如果区间集合相对较大，并且执行了足够多的查询，则通常会优于其他数据结构。

SortedQuerent类型实现了另一种查询策略，该策略跟踪先前查询的结果。当一个查询与先前查询重叠时，可以重用该先前查询的结果，从而显著加速当前查询。（在基准测试中，这是--sorted选项。）

某些操作可以通过使用SIMD指令进一步加速。已实现了两种COITree变体，以利用x86-64 cpu上的AVX2指令（AVXCOITree）和ARM cpu上的Neon指令（NeonCOITree）。如果检测到适当的指令集，则将COITree类型定义为这些类型之一。通常需要使用环境变量RUSTFLAGS="-Ctarget-cpu=native"进行编译才能实现此功能。后备实现（BasicCOITree）支持Rust编译到任何平台，并且仍然非常高效。

尝试使用

这是一个主要用于其他程序中的库，但出于基准测试的目的，它包括一个用于交集 BED 文件的程序。

要尝试使用，只需克隆此存储库并运行

cargo run --release --example bed-intersect -- test1.bed test2.bed > intersections.bed

基准测试

A 是 Ensembl 人类基因组注释中的 2,755,864 个区间，B 是来自某些 RNA-Seq 对齐的 62,159,484 个区间，而 B' 是 B 的前 200 万行。

按顺序排序的区间

带有覆盖率

随机顺序的区间

带有覆盖率

所有基准测试均在 ryzen 5950x 上运行。

讨论

这些基准测试在某种程度上是现实的，因为它们使用真实数据，但它们并不完全是苹果对苹果的，因为它们都涉及解析和写入 BED 文件。大多数程序（包括 coitrees 中实现的程序）都有不完整的 BED 解析器，有些使用其他快捷方式，如假设一组具有特定命名方案的固定染色体。

bedtools 的缺点是它实际上是一个有用的工具，而不仅仅是为了赢得基准测试而实现。很明显，它可以快得多，但毫无疑问，一些成本可以归因于功能丰富性、完整性和安全性。

如果您怀疑有更快的 BED 交集程序（或者只是有趣），请告诉我，我会尝试对其进行基准测试。