4
$\begingroup$

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.

enter image description here

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.

enter image description here

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?

$\endgroup$
4
  • $\begingroup$ @D.W. I added (much) more detail on what I am trying to achieve. Hope this helps. $\endgroup$
    – mibm
    Aug 6, 2020 at 6:59
  • $\begingroup$ @D.W. I cleaned the post, hopefully clarifying it. I think overlap should be between all intervals in group, but I am trying to translate a visual analysis into an algorithm, so this requirement may be too strong. Naively I can measure intersection of multiple ranges using sets of integer values in them and intersect the sets. Unfortunately this would be O(n^2) worst case. Since each run should find mostly the same intervals I hope the groups I need to check intersection between would contain around the same number of intervals as runs (up to a factor of 2) $\endgroup$
    – mibm
    Aug 6, 2020 at 12:32
  • $\begingroup$ Thank you for all the edits! That helps. (I'm curious: does each run output a single interval, or multiple intervals? If multiple, is there some relationship, like that each run outputs about one interval for each group, or that each run outputs a bunch of intervals usually from the same group?) $\endgroup$
    – D.W.
    Aug 6, 2020 at 18:25
  • $\begingroup$ @D.W. Expected output is multiple intervals, about one per group (0-2 per group should be the common output), however I don't know how many groups are expected ahead of time. Also some (few) runs may add a unique interval or split one that other runs report as one. These intervals I would like to remove as "spurious". $\endgroup$
    – mibm
    Aug 9, 2020 at 7:06

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Interesting approach, I'll try it. For overlap I thought of using Jaccard distance (intersection/union). Using clustering might be a too big hammer for 1d data; another problem is getting a good approximation of the number of seeds (in most clustering algos). $\endgroup$
    – mibm
    Aug 11, 2020 at 8:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.