How to group intervals which overlap by some amount?

Question

I have an algorithm that generates a list of intervals. The algorithm is run m times. Lets mark the intervals as tuples (s1, e1), (s2, e2), .., (sn, en). It is possible to add the run ID to the tuple (though I don't think it helps).

The goal is to "clean" spurious ranges (appearing in few runs) and to find groups of at least k almost perfectly overlapping intervals out of m runs of the algorithm, where k is close to m. E.g. if we have 10 runs, k will be 7-9.

By almost perfectly overlapping I mean >0.95 overlap, but exact requirement is user-defined (won't be 0.5 or such). The overlap should be between all intervals in the group (i.e. intersection). However, since I am trying to translate an eyeball analysis into exact requirements this requirement might be too strong ..

The differences in the intervals generated by multiple runs of the algorithm stem from a random factor (seed) as well as slightly different ranges may passing requirements, therefore there is some 'wiggling room' in the results. It also detects some ranges infrequently (think local minima), ranges which should be ignored as spurious.

The origin of the problem is running multiple times some algorithm that searches a range for "interesting" areas. By the nature of the algorithm, each run may return slightly different ranges as well as, at times, a range not seen before.

The intervals can be viewed as integers, though in reality the intervals I get may be real number in any range. I assume I can always use a min-max scaler to, for example, have the ranges have (approximated) integer values in the 0-1000 range or similar.

Below is a (very simple) example of the problem marked as I would do manually. The three green intervals and the three red intervals should be reported as groups, whereas the other three are a group on their own. The overlap of the blue interval is too small. The Yellow interval is not "similar" to the red ones in size.

There may be problems like in the diagram below which I am not sure how to address. The green (bottom) interval and the one above it are certainly "the same" as are the red one and the one below, however the green and red are already too far apart to be considered a group.

My initial idea was to build an interval graph. On that I can greedily find the point at which most intervals intersect, than somehow (no clear idea how yet) I would remove intervals which should not belong to the group. Once done I remove the group from the graph and repeat.

Another method I thought about, but which is O(N^3) (and not guaranteed to yield a good result) is to calculate the overlap of all pairs, selecting the best and merging (union? intersection? average start/end?) then repeating until there are no more "interesting" overlaps.

I consider an overlap interesting if it is larger than some percentage, e.g. 95%.

Are there any algorithms already achieving something similar? Any direction someone can point me in?

Answer 1

Here is one interpretation of your problem:

Given $n$ observed intervals $I_1,\dots,I_n$ and $k$, find $k$ disjoint inferred intervals $J_1,\dots,J_k$ that maximizes the number of observed intervals are covered by at least one of the inferred intervals. Say that $I_i$ is covered by $J_j$ if they have at least 95% overlap, where the overlap between $I_i,J_j$ is measured as $|I_i \cap J_j|/|J_j|$ where $|\cdot|$ denotes the length of an interval.

This problem can be solved with dynamic programming. Sort the endpoints of the observed intervals. For each endpoint $e$ and each $k_0$ with $0 \le k_0 \le k$, let $f(e,k_0)$ denote the maximum number of observed intervals that can be covered by $k_0$ disjoint inferred intervals that are all in $[-\infty,e]$. Then you can write a recurrence relation for $f$: in particular,

$$f(e',k_0) = \max(f(e^*,k_0), \max \{f(e,k_0-1) + \eta : e<e'\})$$

where $e^*$ is the endpoint immediately before $e$, and $\eta$ is the number of observed intervals that are covered by $[e+1,e']$.

---

That said, I suspect a more pragmatic approach might be to use some standard clustering algorithm, adapted for this problem. For instance, you might use k-means on the centers of the intervals. Given a set of intervals that have been clustered together, you might use the median of their left endpoints and median of their right endpoints to define a new interval that serves as the clusterhead. You can probably come up with other heuristics. It's plausible that this might be adequate in practice.