Adaptive spatial blocking for scalable clustering inference with applications to high-throughput spatial proteomics

Technische Samenvatting: Adaptieve Ruimtelijke Blokvorming voor Schaalbare Clustering-inferentie

Probleemstelling
De analyse van ruimtelijke puntpatronen, met name in hoogdoorvoerspatiale proteomica, leunt zwaar op de Ripley's $K$-functie om clustering te beoordelen. Echter, bestaande op $K$ gebaseerde methoden, inclusief het recent voorgestelde $KAMP$-framework (Wrobel en Song, 2024), kampen met ernstige computationele knelpunten bij de toepassing op grootschalige datasets die honderdduizenden tot miljoenen punten bevatten. Traditionele permutatietests vereisen $O(n^2)$ afstandsberekeningen, en zelfs de analytische moment-gebaseerde $KAMP$-benadering, hoewel sneller, vereist nog steeds het opslaan van paarsgewijze afstanden voor alle punten, wat leidt tot excessief geheugengebruik en een kwadratische computationele complexiteit ($O(n^2)$) naarmate de steekproefomvang toeneemt. Subsampling-strategieën zoals onafhankelijke thinning bieden een gedeeltelijke oplossing, maar resulteren in een aanzienlijk verlies van ruimtelijke informatie en statistische kracht, waardoor ze het kwadratische complexiteitprobleem niet fundamenteel oplossen.

Methodologie
Om deze schaalbaarheidsuitdagingen aan te pakken, stellen de auteurs B-KAMP (Block-based KAMP) voor, een framework voor ruimtelijke clustering-inferentie gebouwd op een adaptief algoritme voor ruimtelijke blokvorming.

1. Adaptief Algoritme voor Ruimtelijke Blokvorming:
   De kern van de methode is een algoritme dat een grote observatievenster partitioneert in een verzameling disjuncte rechthoekige blokken. Het algoritme werkt in drie stadia:

   • Grid-representatie: Het domein wordt gediscretiseerd in een $R \times C$ rooster waarbij elke cel maximaal $\sqrt{n}$ punten bevat.
   • Blok-identificatie (Fases I & II): Met behulp van een histogram-gebaseerde aanpak, geïnspireerd door het "grootste rechthoek in een histogram"-probleem, identificeert het algoritme iteratief rechthoekige subregio's die aan specifieke beperkingen voldoen:
     • Minimale Grootte: Blokken moeten ten minste $\sqrt{m}$ punten van belang (Points of Interest, POIs) bevatten en een voldoende aantal achtergrondpunten om een niet-degeneratieve permutatieverdeling te garanderen.
     • Aspect Ratio: Blokken worden beperkt door een maximale aspect ratio $\rho$ om statistische stabiliteit te waarborgen (het vermijden van sterk uitgerekte vormen die edge-corrected estimators kunnen beïnvloeden).
     • Het algoritme geeft prioriteit aan het selecteren van blokken met de kleinste totale aantal punten om het aantal disjuncte blokken te maximaleren en computationele efficiëntie te handhaven.
   • Blok-complement (Fase III): Resterende gridcellen die niet aan blokken zijn toegewezen, worden iteratief samengevoegd met aangrenzende blokken door de grenzen van de blokken uit te breiden naar het minimale begrenzende rechthoek, mits de resulterende blokken disjunct blijven van andere blokken en aan de aspect ratio-beperkingen voldoen. Dit minimaliseert het verlies aan ruimtelijke dekking.

2. Blok-gebaseerde Teststatistiek:
   Binnen elk geïdentificeerd blok $i$ berekent de methode een gestandaardiseerde $K$-functiestatistiek $Z_i(r)$ met behulp van de analytische momenten afgeleid van het $KAMP$-framework onder een conditionele label-permutatie nulverdeling.

   • De globale teststatistiek $Z(r)$ wordt gedefinieerd als een gewogen som van de blok-niveau statistieken: $Z(r) = \sum w_i Z_i(r)$.
   • De gewichten $w_i$ worden gekozen proportioneel aan $n_i/p_i$ (waarbij $n_i$ het totaal aantal punten is en $p_i$ de lokale prevalentie van POIs in het blok) om blokken met schaarse signalen zwaarder te wegen.
   • Onder de conditionele blokwijze permutatie nulverdeling bewijzen de auteurs dat, naarmate het aantal blokken $b \to \infty$, de globale statistiek $Z(r)$ convergeert in distributie naar een standaard normale verdeling $\mathcal{N}(0,1)$ via de Lyapunov Centrale Limietstelling. Dit maakt snelle p-waarde berekening mogelijk zonder empirische permutatie-replicaten.

3. Extensie naar Bivariante Analyse:
   Het framework wordt uitgebreid om te testen op ruimtelijke colokalisatie tussen twee typen punten (bijv. plasmacellen en macrofagen) met behulp van een bivariante $K$-functie estimator, met een vergelijkbare blok-niveau standaardisatie en aggregatie.

Belangrijkste Bijdragen

• Schaalbaar Algoritme: De ontwikkeling van een $O(RC)$ adaptief ruimtelijk blokvormingsalgoritme dat efficiënt geldige rechthoekige blokken identificeert voor grootschalige puntpatronen, waardoor $O(n^2)$ complexiteit van volledige venster paarsgewijze berekeningen wordt vermeden.
• Statistisch Framework: De formulering van een blok-gebaseerde clusteringtest die lokale bewijsvoering aggregeert via een gewogen som, waarbij gebruik wordt gemaakt van asymptotische normaliteit voor snelle inferentie.
• Praktische Implementatie: De beschikbaarstelling van een algemeen bruikbare blokvormingsstrategie toepasbaar op diverse schaalbare ruimtelijke methoden, met code beschikbaar via GitHub.

Resultaten

• Simulatiestudies:

  • Computationele Efficiëntie: B-KAMP schaalt lineair met het aantal punten en blijft haalbaar voor datasets met tot 100.000 punten. In tegenstelling hiertoe faalt volledige venster $KAMP$ door geheugenbeperkingen bij $n \ge 40.000$, en blijft thinned $KAMP$($KAMP_{0.25}$) computationeel duur. B-KAMP is consistent de snelste methode voor grote $n$.
  • Statistische Kracht: Hoewel volledige venster methoden over het algemeen de hoogste kracht bereiken wanneer zij uitvoerbaar zijn, vertoont B-KAMP competitieve kracht, met name bij radii $r \approx 0.15$ (relatief tot de blokgrootte). Het presteert beter dan zwaar gethinned methoden ($KAMP_{0.25}$) en behoudt een geldige Type I fout controle.
  • Robuustheid: De methode vertoont een robuuste prestatie over variërende puntabundanties en gridresoluties.

• Toepassing op Real-world Data (Spatiale Proteomics):

  • Toegepast op een dataset van gezonde menselijke darmweefsel (ongeveer 2,6 miljoen cellen over 65 afbeeldingen).
  • De methode detecteerde succesvol sterke ruimtelijke aggregatie van plasmacellen en significante colokalisatie tussen plasmacellen en macrofagen.
  • B-KAMP leverde sterker statistisch bewijs (lagere p-waarden) dan de thinned $KAMP$ baselines voor grote afbeeldingen en schaalde gunstig daar waar volledige venster methoden de beschikbare geheugenlimieten overschreden.

Betekenis en Claims
Het artikel claimt dat B-KAMP een gunstige balans biedt tussen statistische kracht en computationele efficiëntie, wat rigoureuze ruimtelijke clustering-inferentie mogelijk maakt voor hoogdoorvoerspatiale proteomica data die voorheen computationeel onmogelijk was. De auteurs positioneren de methode niet als een vervanging voor volledige venster procedures voor kleine datasets, maar als een noodzakelijk schaalbaar alternatief voor grootschalige afbeeldingen waar traditionele methoden falen.

De auteurs hanteren een bescheiden standpunt met betrekking tot beperkingen:

• De methode is een conditionele blokwijze test, wat betekent dat deze geen ruimtelijke relaties over blokgrenzen heen gebruikt, wat potentieel clusteringpatronen die meerdere blokken overspannen kan dempen en resulteert in een bepaald verlies aan kracht vergeleken met volledige venster methoden.
• De prestaties hangen af van de initiële gridresolutie en het hebzuchtige karakter van de blok-complement stap (Fase III).
• Toekomstig werk suggereert dat er gekeken kan worden naar data-gedreven gridselectie, globale optimalisatie van blokvormen, en extensies naar 3D ruimtelijke data.