CLUSTER and MERGE split contained intervals into separate clusters

[conradbzura]

Description

CLUSTER and MERGE produce incorrect results when an interval is fully contained within an earlier, wider interval. A later interval that overlaps the wide interval (but not the immediately preceding narrower one) is spuriously split into a new cluster / merged region.

Reproduction with intervals [0,100), [10,20), [30,40) (all on chr1):

GIQL   MERGE -> [(chr1, 0, 100), (chr1, 30, 40)]     # wrong
bioframe merge -> [(chr1, 0, 100)]                    # correct
bedtools merge -> chr1 0 100                          # correct

GIQL CLUSTER -> [0,100)=1, [10,20)=1, [30,40)=2       # wrong (30,40 should be cluster 1)

Discovered by the benchmark suite: on a 1e6 interval set, MERGE returns 847,897 regions vs the bedtools/bioframe oracle's 844,107 (~3,790 intervals, ~0.5%, wrongly split). Contained intervals are common in real genomic data (a gene containing its exons, a broad peak containing narrow sub-peaks), so this yields wrong results on realistic inputs.

Expected Behavior

MERGE and CLUSTER should treat an interval as part of the current cluster when it overlaps (or is book-ended with) the running union of the cluster so far — matching bedtools merge and bioframe.merge. Contained intervals never start a new cluster.

Root Cause

The shared __giql_lag_calc machinery (src/giql/expanders/cluster.py, src/giql/expanders/merge.py; flag CLUSTER_FLAG_COL = "__giql_is_new_cluster") emits:

CASE WHEN LAG("end") OVER (PARTITION BY "chrom" ORDER BY "start") >= "start" THEN 0 ELSE 1 END

LAG("end") is the immediately preceding row's end, not the maximum end seen so far in the cluster. With containment the preceding row's end can be smaller than the cluster's true right edge, so a still-overlapping interval is misclassified as a new cluster. For [0,100),[10,20),[30,40): at [30,40), LAG("end") is 20 (from [10,20)), and 20 >= 30 is false, so a new cluster starts — even though 30 < 100.

Proposed fix

Replace LAG("end") with the running maximum of end over the preceding rows:

CASE WHEN MAX("end") OVER (
  PARTITION BY "chrom" ORDER BY "start"
  ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING
) >= "start" THEN 0 ELSE 1 END

Validated: the containment case yields the correct single [0,100) region, and on the 1e6 set MERGE returns exactly 844,107 regions (matching the bedtools/bioframe oracle), at similar or better runtime. The distance-argument and predicate forms of CLUSTER/MERGE should get the same running-edge treatment where applicable — to be confirmed during implementation.

Existing CLUSTER/MERGE tests do not appear to cover containment; add coverage as part of the fix.