我有两个大的基因组区域列表，格式为两个 bed 文件，有很多工具可以帮助我检查两个列表的重叠。
任何给定区域(一个来自列表 A，另一个来自列表 B)，只要它们在任何坐标上重叠，就称为重叠。有可用的工具可以做到这一点。但我希望编写一个高效的算法，我可以在列表 A 中维护一个类似哈希表的结构，然后我迭代列表 B 中的所有区域，对于列表 B 中的每个区域，我可以使用快速算法来判断是否有一些列表 A 中的区域与列表 B 中的特定区域重叠。
我特别需要一个有效的解决方案，因为这两个列表都非常大。非常感谢。
最佳答案
一个选择是:
- 在一个 BED 文件中创建区域的一维 R 树。为每个外显子插入一个范围。
- 对于另一个 BED 文件中的每个区域，在 R 树中搜索 该区域每个外显子的交叉点。
对于 Java，R 树有多种实现。我用过的支持一维范围的是 SIRtree , 在图书馆 JTS .它提供了插入范围和搜索交集的简单方法。
内存中表示的任何数据结构对于足够大的 BED 文件来说都是可扩展性问题。您可以通过增加 VM 可用的内存量(硬件和 -Xmx 设置)或通过在磁盘上表示您的数据结构来解决这个问题。
关于java - 检查重叠基因组区域的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31321993/