CODEWITHSUNDEEP
rrangegroupingoverlap
PieterD
PieterD

Reputation: 59

R group by overlapping ranges

I have a data frame where rows contain ranges. I would like to determine groups of ranges in which each range overlaps for more than 75% with at least one of the other rows in the group. The grouping should be added to the original as an index variable.

Example data is as follows:

df <- data.frame(label = c("A", "B", "C", "D", "E", "F"),
                 start = c(16, 18, 37, 62, 15, 45),
                 stop = c(22, 24, 55, 66, 23, 55))

The resulting df should look like:

label       start   stop   ID
"A"         6       22     1
"B"         6       24     1
"C"         37      55     2
"D"         62      66     3
"E"         15      23     1
"F"         45      55     2

First I have tried a dplyr option with mutate and lag, but then grouping depends on the order of the rows and will not work in all cases. Next I tried a for loop with seq_along, but I could not manage to solve the problem. Hope one of you can...

Upvotes: 0

Views: 689

Answers (1)

r2evans
r2evans

Reputation: 160407

overlap <- function(A, B) {
  shared <- pmax(0, min(A[2], B[2]) - max(A[1], B[1]))
  max(shared / c(diff(A), diff(B)))
}

eg <- expand.grid(a = seq_len(nrow(df)), b = seq_len(nrow(df)))
eg <- eg[eg$a < eg$b,]

together <- cbind(
  setNames(df[eg$a,], paste0(names(df), "1")),
  setNames(df[eg$b,], paste0(names(df), "2"))
)
together <- within(together, {
  shared  = pmax(0, pmin(stop1, stop2) - pmax(start1, start2))
  overlap = pmax(shared / (stop1 - start1), shared / (stop2 - start2))
})[, c("label1", "label2", "overlap")]

bigenough <- together[together$overlap >= 0.75,]
groups <- split(bigenough$label2, bigenough$label1)

for (ltr in df$label) {
  ind <- (ltr == names(groups)) | sapply(groups, `%in%`, x = ltr)
  groups <- c(
    setNames(list(unique(c(ltr, names(groups[ind]), unlist(groups[ind])))), ltr),
    groups[!ind]
  )
}

groups <- data.frame(
  ID = rep(seq_along(groups), lengths(groups)),
  label = unlist(groups)
)

Results:

merge(df, groups, by = "label")
#   label start stop ID
# 1     A    16   22  2
# 2     B    18   24  2
# 3     C    37   55  1
# 4     D    62   66  3
# 5     E    15   23  2
# 6     F    45   55  1

You asked for a way to do with without a for loop. Since we need one iteration (of the loop) to work with the results of the previous iteration, lapply won't work for us. We can, however, use Reduce:

# groups <- split(...)

groups <- Reduce(function(grps, ltr) {
  ind <- (ltr == names(grps)) | sapply(grps, `%in%`, x = ltr)
  c(setNames(list(unique(c(ltr, names(grps[ind]), unlist(grps[ind])))), ltr),
    grps[!ind])
}, df$label, init = groups)
# $F
# [1] "F" "C"
# $E
# [1] "E" "B" "A"
# $D
# [1] "D"

# groups <- data.frame(ID = ...)
# merge(df, groups, ...)

(and then the final groups <- data.frame(..) call from above). This works just as effectively. The only catch is that Reduce is using for (https://github.com/wch/r-source/blob/d22ee2fc0dc8142b23eed9f46edf76ea9d3ca69a/src/library/base/R/funprog.R) :-)

Upvotes: 4

Related Questions