# Clustering of Intervals or Clustering without Distance Matrices

I have the following problem with data points as intervals that I want to cluster. So I have my data which are pairs of intervals. I simply want to rule out random outcomes and determine the pairs of intervals that are significant in the data set (e.g., with a simple t-test). However I have got about 1.5-2 million of these intervals. Some of them even only differ by a few values. In the following picture this is illustrated. I have the whole region (1) and different pairs of intervals (2),(3),(4). To further complicate things I also have single intervals (5). So I need some kind of segmentation to conduct the significance test. Concretely I would just want to count the probability for a specific interval, multiply these to get the pdf and then model each pair of intervals with the multinomial distribution and assign p-values to see which ones of these intervals are not occurring by chance.

I thought to simply consider the start point of each interval and then cluster these based positions. However, as I have many of the intervals clustering with distance matrices is not feasible. Is there a other way to cluster this? Simply sort for both start position and cluster from there. Or is there even a way to cluster intervals efficiently? Or even another way to conduct a significance analysis of theses intervals?

Thanks

• I cannot fully follow your question how the clustering relates to the testing part. But GDBSCAN (G for generalized) could be used to cluster intervals based on overlap, or relative overlap without distance matrixes. It just needs a binary predicate 'should be in the same cluster' which you can define based on overlap, for example. – Anony-Mousse Feb 5 '18 at 20:31