区间的并集和交集

Question

我有一组不同id的时间间隔。例如：

df <- data.frame(id=c(rep("a",4),rep("b",2),rep("c",3)), start=c(100,250,400,600,150,610,275,600,700), end=c(200,300,550,650,275,640,325,675,725))

每个ID的时间间隔不重叠，但不同ID的时间间隔可能会重叠。下面是一张图片：

plot(range(df[,c(2,3)]),c(1,nrow(df)),type="n",xlab="",ylab="",yaxt="n")
for ( ii in 1:nrow(df) ) lines(c(df[ii,2],df[ii,3]),rep(nrow(df)-ii+1,2),col=as.numeric(df$id[ii]),lwd=2)
legend("bottomleft",lwd=2,col=seq_along(levels(df$id)),legend=levels(df$id))

我需要的是两个函数： 1. 一个函数将这些区间取并集。对于上面的例子，它将返回这个data.frame：

union.df <- data.frame(id=rep("a,b,c",4), start=c(100,400,600,700), end=c(325,550,675,725))

2. 一个函数将交叉的时间段进行比较，只有当所有id都在该时间段内时才保留该时间段。 对于上面的例子，它将返回以下数据框：

intersection.df <- data.frame(id="a,b,c", start=610, end=640)

- user1701545

---

尝试使用 ?intersect 和 ?union。 - Henk

“intersect”和“union”不起作用 - 它们适用于离散集合，而不是区间。 - Stephan Kolassa

你能解释一下如何得到“这些区间的并集和交集”，以及它们与你的ID有什么关系吗？考虑到你已经在一个个体内有多个不重叠的区间，所有区间的交集将为空。同样地，我不明白并集是从哪里来的。 - Stephan Kolassa

Answer 1

intervals包解决了以下问题的联合部分：

require(intervals)
idf <- Intervals(df[,2:3])
as.data.frame(interval_union(idf))

对于交集的部分，取决于区间的定义方式：

idl <- lapply(unique(df$id),function(x){var <- as(Intervals(df[df$id==x,2:3]),"Intervals_full");closed(var)[,1]<- FALSE;return(var)})
idt <- idl[[1]]
for(i in idl)idt <- interval_intersection(idt,i)
res <- as.data.frame(idt) 
res
   V1  V2
1 610 640

- Nightwriter

---

刚刚编辑了答案以应对第二部分。可以使用默认的闭区间，并删除结果中具有相同条目的行（在这种情况下为275 275）。所有这些都取决于区间是开放还是闭合的。 - Nightwriter

Answer 2

这有点尴尬，但思路是将数据展开为一系列开放和关闭事件。然后跟踪每个时间段同时打开的间隔数。这假设每个组没有重叠的间隔。

df <- data.frame(id=c(rep("a",4),rep("b",2),rep("c",3)), start=c(100,250,400,600,150,610,275,600,700), end=c(200,300,550,650,275,640,325,675,725))


sets<-function(start, end, group, overlap=length(unique(group))) {
    dd<-rbind(data.frame(pos=start, event=1), data.frame(pos=end, event=-1))
    dd<-aggregate(event~pos, dd, sum)
    dd<-dd[order(dd$pos),]
    dd$open <- cumsum(dd$event)
    r<-rle(dd$open>=overlap)
    ex<-cumsum(r$lengths-1 + rep(1, length(r$lengths))) 
    sx<-ex-r$lengths+1
    cbind(dd$pos[sx[r$values]],dd$pos[ex[r$values]+1])

} 

#union
with(df, sets(start, end, id,1))
#     [,1] [,2]
# [1,]  100  325
# [2,]  400  550
# [3,]  600  675
# [4,]  700  725

#overlap
with(df, sets(start, end, id,3))
#      [,1] [,2]
# [1,]  610  640

- MrFlick

Answer 3

对于交集，我会先计算每个范围内所包含的区间数量（在此代码中，范围的开始标记为ord.dirs$x，范围内区间数量为ord.dirs$z）：

dirs <- data.frame(x=c(df$start, df$end), y=rep(c(1, -1), each=nrow(df)))
ord.dirs <- dirs[order(dirs$x),]
ord.dirs$z <- cumsum(ord.dirs$y)
ord.dirs <- ord.dirs[!duplicated(ord.dirs$x, fromLast=T),]
ord.dirs
#      x  y z
# 1  100  1 1
# 5  150  1 2
# 10 200 -1 1
# 2  250  1 2
# 14 275 -1 2
# 11 300 -1 1
# 16 325 -1 0
# 3  400  1 1
# 12 550 -1 0
# 8  600  1 2
# 6  610  1 3
# 15 640 -1 2
# 13 650 -1 1
# 17 675 -1 0
# 9  700  1 1
# 18 725 -1 0

现在，您只需要获取具有正确间隔数量（本例中为3）的范围即可：

pos.all <- which(ord.dirs$z == length(unique(df$id)))
data.frame(start=ord.dirs$x[pos.all], end=ord.dirs$x[pos.all+1])
#   start end
# 1   610 640

您可以使用ord.dirs同样地获取集合的并集：

zero.pos <- which(ord.dirs$z == 0)
data.frame(start=c(ord.dirs$x[1], ord.dirs$x[head(zero.pos, -1)+1]),
           end=ord.dirs$x[zero.pos])
#   start end
# 1   100 325
# 2   400 550
# 3   600 675
# 4   700 725

- josliber

Answer 4

GenomicRanges软件包提供了一些交集和重叠函数：

library(GenomicRanges)
source("http://bioconductor.org/biocLite.R")
biocLite("Gviz")    
library(Gviz)

创建一个Grange对象，其seqnames相等（这很重要）。

df <- data.frame(id=c(rep("a",4),rep("b",2),rep("c",3)),     start=c(100,250,400,600,150,610,275,600,700), end=c(200,300,550,650,275,640,325,675,725))
gr <- GRanges(seqnames = rep(1,nrow(df)),IRanges(start = df$start,end =      df$end))

现在，您也可以使用Gviz软件包绘制范围。

d0 <- GenomeAxisTrack()
d1 <- AnnotationTrack(gr,group = df$id,fill=df$id)
plotTracks(c(d0,d1))

联合操作是通过reduce函数完成的，其中区间被折叠。

as.data.frame(reduce(gr))[,2:3]

交集是通过findoverlaps完成的。然后，通过与3个范围重叠的范围进行过滤。

OL <- as.data.frame(findOverlaps(gr,type="within"))
table(OL[,1])

df[as.numeric(names(which(table(OL[,1])==3))),]

- Roman

Answer 5

使用iv_groups()和reduce()d iv_set_intersect()(在ivs 0.2.0中)进行自我联合，以及用于交集的reduce()d iv_intersect()(在0.1.0中): ivs。

library(ivs)
library(dplyr, warn.conflicts = FALSE)
library(purrr)
library(tidyr)

df <- tibble(
  id=c(rep("a",4),rep("b",2),rep("c",3)), 
  start=c(100,250,400,600,150,610,275,600,700), 
  end=c(200,300,550,650,275,640,325,675,725)
)

df <- df %>%
  mutate(range = iv(start, end), .keep = "unused")

df
#> # A tibble: 9 × 2
#>   id         range
#>   <chr>  <iv<dbl>>
#> 1 a     [100, 200)
#> 2 a     [250, 300)
#> 3 a     [400, 550)
#> 4 a     [600, 650)
#> 5 b     [150, 275)
#> 6 b     [610, 640)
#> 7 c     [275, 325)
#> 8 c     [600, 675)
#> 9 c     [700, 725)

# Union:
# Merge all overlapping ranges
df %>% 
  reframe(range = iv_groups(range))
#> # A tibble: 4 × 1
#>        range
#>    <iv<dbl>>
#> 1 [100, 325)
#> 2 [400, 550)
#> 3 [600, 675)
#> 4 [700, 725)

# Intersection:
# Chop the ranges by `id`
df_chopped <- df %>%
  chop(range)

# Reduce an interval set intersection operation over each pair of interval vectors
df_chopped %>%
  reframe(range = reduce(range, iv_set_intersect))
#> # A tibble: 1 × 1
#>        range
#>    <iv<dbl>>
#> 1 [610, 640)

- Davis Vaughan