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

기술 요약: 확장 가능한 클러스터링 추론을 위한 적응형 공간 블록화 (Adaptive Spatial Blocking)

문제 정의
고처리량 공간 단백질체학(high-throughput spatial proteomics)에서의 공간 점 패턴 분석은 클러스터링을 평가하기 위해 리플리 $K$-함수(Ripley's $K$-function)에 크게 의존한다. 그러나 최근 제안된 $KAMP$ 프레임워크(Wrobel and Song, 2024)를 포함한 기존의 $K$-기반 방법들은 수십만 개에서 수백만 개의 점을 포함하는 대규모 데이터셋에 적용될 때 심각한 계산 병목 현상에 직면한다. 전통적인 순열 검정(permutation tests)은 $O(n^2)$의 거리 계산을 요구하며, 더 빠른 방식인 분석적 모멘트 기반 $KAMP$조차도 모든 점에 대한 쌍별 거리(pairwise distances)를 저장해야 하므로, 샘플 크기가 증가함에 따라 기하급수적인 메모리 사용량과 이차 복잡도($O(n^2)$)를 초래한다. 독립적 희소화(independent thinning)와 같은 서브샘플링 전략은 부분적인 해결책이 될 수 있으나, 상당한 공간 정보 및 통계적 검정력의 손실을 야기하며, 이차 복잡도 문제를 근본적으로 해결하지 못한다.

방법론
이러한 확장성 문제를 해결하기 위해, 저자들은 적응형 공간 블록화 알고리즘을 기반으로 구축된 공간 클러스터링 추론 프레임워크인 B-KAMP(Block-based KAMP)를 제안한다.

1. 적응형 공간 블록화 알고리즘:
   본 방법의 핵심은 관측 창(observation window)을 서로 겹치지 않는 직사각형 블록들의 집합으로 분할하는 알고-리즘이다. 이 알고리즘은 세 단계로 작동한다:

   • 그리드 표현: 도메인을 각 셀에 최대 $\sqrt{n}$개의 점이 포함되도록 $R \times C$ 그리드로 이산화한다.
   • 블록 식별 (단계 I 및 II): "히스토그램에서의 가장 큰 직사각형" 문제에서 영감을 얻은 히스토그램 기반 접근 방식을 사용하여, 특정 제약 조건을 만족하는 직사각형 하위 영역을 반복적으로 식별한다:
     • 최소 크기: 블록은 최소 $\sqrt{m}$개의 관심 대상 점(POIs)과 비퇴화적 순열 분포를 보장하기 위한 충분한 배경 점을 포함해야 한다.
     • 종횡비: 통계적 안정성을 확보하기 위해(가장자리 보정 추정치를 편향시키는 길쭉한 형태를 피하기 위해) 블록은 최대 종횡비 $\rho$에 의해 제한된다.
     • 알고리즘은 블록의 수를 최대화하고 계산 효율성을 유지하기 위해 총 점의 개수가 가장 적은 블록을 우선적으로 선택한다.
   • 블록 보완 (단계 III): 블록에 할당되지 않은 잔여 그리드 셀들은, 결과적인 블록이 다른 블록과 겹치지 않고 종횡비 제약을 준수하는 한, 최소 경계 직사각형으로 블록 경계를 확장함으로써 인접한 블록으로 반복적으로 병합된다. 이는 공간적 커버리지 손실을 최소화한다.

2. 블록 기반 검정 통계량:
   각 식별된 블록 $i$ 내에서, 본 방법은 조건부 레이블 순열 무효 분포(conditional label-permutation null distribution) 하에서의 분석적 모멘트를 사용하여 표준화된 $K$-함수 통계량 $Z_i(r)$를 계산한다.

   • 전역 검정 통계량 $Z(r)$은 블록 수준 통계량의 가중 합으로 정의된다: $Z(r) = \sum w_i Z_i(r)$.
   • 가중치 $w_i$는 희소한 신호를 가진 블록에 가중치를 두기 위해 $n_i/p_i$ (여기서 $n_i$는 총 점의 개수, $p_i$는 블록 내 POIs의 국소적 유병률)에 비례하도록 선택된다.
   • 조건부 블록별 순열 무효 분포 하에서, 저자들은 블록의 수 $b \to \infty$일 때 전역 통계량 $Z(r)$이 리아푸노프 중심한계정리(Lyapunov Central Limit Theorem)를 통해 표준 정규 분포 $\mathcal{N}(0,1)$로 수렴함을 증명하였다. 이를 통해 경험적 순열 반복 없이도 빠른 $p$-값 계산이 가능하다.

3. 이변량 분석으로의 확장:
   본 프레임워크는 이변량 $K$-함수 추정기를 사용하여 두 가지 유형의 점(예: 형질 세포와 대식세포) 사이의 공간적 공국소화(colocalization)를 테스트하도록 확장되며, 유사한 블록 수준 표준화 및 집계 과정을 거친다.

주요 기여

• 확장 가능한 알고리히즘: 대규모 점 패턴에서 유효한 직사각형 블록을 효율적으로 식별하여, 전체 창(full-window) 쌍별 계산의 $O(n^2)$ 복잡도를 피하는 $O(RC)$ 적응형 공간 블록화 알고리즘을 개발하였다.
• 통계적 프레임워크: 점의 밀도가 낮은 곳에 가중치를 두는 가중 합을 통해 국소적 증거를 집계하고, 점근적 정규성을 활용하여 신속한 추론을 수행하는 블록 기반 클러스터링 검정을 정립하였다.
• 실제 구현: 다양한 확장 가능한 공간 방법론에 적용 가능한 범용적인 블록화 전략을 제공하며, 코드는 GitHub를 통해 공개된다.

결과

• 시뮬레이션 연구:

  • 계산 효율성: B-KAMP는 점의 개수에 따라 선형적으로 확장되며, 최대 100,000개의 점이 있는 데이터셋에서도 실행 가능하다. 반면, 전체 창 $KAMP$는$n \ge 40,000$에서 메모리 제약으로 인해 실패하며, 희소화된$KAMP$($KAMP_{0.25}$) 역시 계산 비용이 여전히 높다. B-KAMP는 일관되게 가장 빠른 방법이다.
  • 통계적 검정력: 전체 창 방법이 가능한 경우 일반적으로 가장 높은 검정력을 보이지만, B-KAMP는 특히 $r \approx 0.15$ (블록 크기 대비) 반경에서 경쟁력 있는 검정력을 보여준다. 이는 심하게 희소화된 방법들($KAMP_{0.25}$)보다 우수한 성능을 보이며 유효한 제1종 오류 제어를 유지한다.
  • 강건성: B-KAMP는 다양한 점의 풍부도와 그리드 해상도에 대해 강건한 성능을 보인다.

• 실제 데이터 적용 (공간 단백질체학):

  • 약 260만 개의 세포가 포함된 65개의 이미지(건강한 인간 장 조직 데이터)에 적용되었다.
  • 이 방법은 형질 세포의 강력한 공간적 응집과 형질 세포와 대식세포 사이의 유의미한 공국소화를 성공적으로 탐지하였다.
  • B-KAMP는 대형 이미지에서 희소화된 $KAMP$베이스라인보다 더 강력한 통계적 증거(더 낮은$p$-값)를 제공하였으며, 전체 창 방법이 가용 메모리를 초과하는 지점에서 유리하게 확장되었다.

의의 및 주장
본 논문은 B-KAMP가 통계적 검정력과 계산 효율성 사이의 유리한 균형을 제공하여, 기존에는 계산적으로 불가능했던 고처리량 공간 단백질체학 데이터에 대한 엄격한 공간 클러스터링 추론을 가능하게 한다고 주장한다. 저자들은 이 방법을 소규모 데이터셋을 위한 전체 창 절차의 대체재가 아니라, 전통적인 방법들이 실패하는 대규모 이미지에서의 필수적인 확장 가능 대안으로 위치시킨다.

저자들은 다음과 같은 한계점에 대해 신중한 입장을 유지한다:

• 이 방법은 조건부 블록별 검정이므로, 블록 경계를 가로지르는 공간적 관계를 활용하지 않는다. 이는 여러 블록에 걸쳐 있는 클러스터링 패턴을 약화시켜 전체 창 방법과 비교했을 때 검정력 손실을 초래할 수 있다.
• 성능은 초기 그리드 해상도와 단계 III의 탐욕적(greedy) 성격에 의존한다.
• 향-후 연구 과제로 데이터 기반 그리드 선택, 블록 모양의 전역 최적화, 그리고 3D 공간 데이터로의 확장이 제안되었다.