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

Question

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

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

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

Answer 1

一种选择是：

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

对于Java来说，R-树有多种实现。我使用过的一种支持一维范围的方法是SIRtree，它位于库JTS中。它提供了插入范围和搜索交叉口的简单方法。

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