检查重叠基因组区域的算法

Question

我有两个 bed 文件形式的大型基因组区域列表，有很多工具可以帮助我检查两个列表的重叠。

任何给定的区域（一个来自列表A，另一个来自列表B），只要它们在任何坐标上重叠，就称为重叠。有可用的工具可以做到这一点。但是我希望编写一个高效的算法，我可以在列表 A 中维护一个类似 hash-table 的结构，然后我迭代列表 B 中的所有区域，对于列表 B 中的每个区域，我可以使用快速算法来判断列表 A 中的某些区域是否与列表 B 中的特定区域重叠。

我特别需要一个有效的解决方案，因为这两个列表都非常大。非常感谢。

Answer 1

一个选择是：

1. 创建一个 BED 文件中区域的一维 R 树。为每个外显子插入一个范围。
2. 对于另一个 BED 文件中的每个区域，在 R 树中搜索 该区域每个外显子的交叉点。

对于Java，R树有多种实现。我用过的支持一维范围的是 SIRtree, in the library JTS。它提供了插入范围和搜索交集的简单方法。

内存中表示的任何数据结构对于足够大的 BED 文件来说都是可伸缩性问题。您可以通过增加 VM 可用的内存量（硬件和 -Xmx 设置）或通过在磁盘上表示您的数据结构来解决这个问题。