r - 在 R 的 data.table 中 foverlap 的一次迭代中查找所有重叠

Question

我正在尝试使用 data.table 在 R 中合并一堆重叠的时间段。我接到了一个电话，要求自己对 table 进行 foverlap，这已经足够高效了。

我的问题是这样的:说 A 期与 B 期重叠，B 期与 C 期重叠，但 A 与 C 不重叠。在这种情况下，A 不与 C 分组，它们最终必须合并。

目前我有一个 while 循环查找重叠和合并，直到不再发生合并，但这并不是完全可扩展的。我可以看到的一个解决方案是将组的索引递归地应用于自身直到稳定，但这看起来仍然需要一个循环，我想要一个完全矢量化的解决方案。

dt = data.table(start = c(1,2,4,6,8,10),
                end   = c(2,3,6,8,10,12))
setkeyv(dt,c("start","end"))

f = foverlaps(dt,
              dt,
              type="any",
              mult="first",
              which="TRUE")

#Needs to return [1,1,3,3,3,3]
print(f)
#1 1 3 3 4 5
print(f[f])
#1 1 3 3 3 4
print(f[f][f])
#1 1 3 3 3 3

任何人都可以帮助我对向量化这个程序有一些想法吗？

使用 ID 进行编辑:

dt = data.table(id = c('A','A','A','A','A','B','B','B'),
                eventStart = c(1,2,4,6,8,10,11,15),
                eventEnd   = c(2,3,6,8,10,12,14,16))
setkeyv(dt,c("id","eventStart","eventEnd"))

f = foverlaps(dt,
              dt,
              type="any",
              mult="first",
              which="TRUE")

#Needs to return [1 1 3 3 3 6 6 8] or similar

Answer 1

Bioconductor 上的 IRanges 包是 data.table 的 foverlaps() 的灵感来源，它对此类问题有一些方便的功能。
也许， reduce() 可能是您正在寻找合并所有重叠时期的函数:

library(data.table)
dt = data.table(start = c(1,2,4,6,8,10),
                end   = c(2,3,6,8,10,12))

library(IRanges)
ir <- IRanges(dt$start, dt$end)

ir

IRanges object with 6 ranges and 0 metadata columns:
          start       end     width
      <integer> <integer> <integer>
  [1]         1         2         2
  [2]         2         3         2
  [3]         4         6         3
  [4]         6         8         3
  [5]         8        10         3
  [6]        10        12         3

reduce(ir, min.gapwidth = 0L)

IRanges object with 2 ranges and 0 metadata columns:
          start       end     width
      <integer> <integer> <integer>
  [1]         1         3         3
  [2]         4        12         9

as.data.table(reduce(ir, min.gapwidth = 0L))

   start end width
1:     1   3     3
2:     4  12     9

在 Bioconductor 上，有一个全面的 Introduction to IRanges 可用。

编辑 :OP 提供了第二个示例数据集，其中包括 id 列，并询问 IRanges 是否支持通过 id 连接间隔。
向 IRanges 添加数据似乎很快专注于基因组研究领域，这对我来说是未知的。但是，我发现使用 IRanges 的以下方法:
使用 IRanges 分组

library(data.table)
# 2nd sample data set provided by the OP
dt = data.table(id = c('A','A','A','A','A','B','B','B'),
                eventStart = c(1,2,4,6,8,10,11,15),
                eventEnd   = c(2,3,6,8,10,12,14,16))

library(IRanges)
# set names when constructing IRanges object
ir <- IRanges(dt$eventStart, dt$eventEnd, names = dt$id)

lapply(split(ir, names(ir)), reduce, min.gapwidth = 0L)

$A
IRanges object with 2 ranges and 0 metadata columns:
          start       end     width
      <integer> <integer> <integer>
  [1]         1         3         3
  [2]         4        10         7

$B
IRanges object with 2 ranges and 0 metadata columns:
          start       end     width
      <integer> <integer> <integer>
  [1]        10        14         5
  [2]        15        16         2

将其转换回 data.table 会导致一段相当笨拙的代码:

ir <- IRanges(dt$eventStart, dt$eventEnd, names = dt$id)
rbindlist(lapply(split(ir, names(ir)), 
                 function(x) as.data.table(reduce(x, min.gapwidth = 0L))), 
          idcol = "id")

   id start end width
1:  A     1   3     3
2:  A     4  10     7
3:  B    10  14     5
4:  B    15  16     2

data.table 内的分组
如果我们在 data.table 内分组并在单个块上应用 reduce()，我们可以用更少复杂的代码获得相同的结果:

dt[, as.data.table(reduce(IRanges(eventStart, eventEnd), min.gapwidth = 0L)), id]