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

Resumo Técnico: Bloqueio Espacial Adaptativo para Inferência de Agrupamento Escalável

Definição do Problema
A análise de padrões de pontos espaciais, particularmente em proteômica espacial de alto rendimento, depende fortemente da função $K$ de Ripley para avaliar o agrupamento (clustering). No entanto, os métodos existentes baseados em $K$, incluindo o recentemente proposto framework $KAMP$ (Wrobel e Song, 2024), enfrentam gargalos computacionais severos quando aplicados a conjuntos de dados de grande escala contendo centenas de milhares a milhões de pontos. Testes de permutação tradicionais exigem cálculos de distância $O(n^2)$ e, mesmo o método analítico baseado em momentos do $KAMP$, embora mais rápido, ainda exige o armazenamento de distâncias pareadas para todos os pontos, levando ao uso proibitivo de memória e à complexidade computacional quadrática ($O(n^2)$) conforme o tamanho da amostra aumenta. Estratégias de subamostragem como o afinamento independente (thinning) oferecem uma solução parcial, mas resultam em uma perda significativa de informação espacial e poder estatístico, não resolvendo fundamentalmente a complexidade quadrática.

Metodologia
Para abordar esses desafios de escalabilidade, os autores propõem o B-KAMP (Block-based KAMP), um framework de inferência de agrupamento espacial construído sobre um algoritmo de bloqueio espacial adaptativo.

1. Algoritmo de Bloqueio Espacial Adaptativo:
   O núcleo do método é um algoritmo que particiona uma grande janela de observação em uma coleção de blocos retangulares disjuntos. O algoritmo opera em três estágios:

   • Representação em Grade: O domínio é discretizado em uma grade $R \times C$ onde cada célula contém, no máximo, $\sqrt{n}$ pontos.
   • Identificação de Blocos (Fases I & II): Usando uma abordagem baseada em histograma inspirada no problema do "maior retângulo em um histograma", o algoritmo identifica iterativamente subregiões retangulares que satisfazem restrições específicas:
     • Tamanho Mínimo: Os blocos devem conter pelo menos $\sqrt{m}$ pontos de interesse (POIs) e um número suficiente de pontos de fundo para garantir uma distribuição de permutação não degenerada.
     • Razão de Aspecto: Os blocos são limitados por uma razão de aspecto máxima $\rho$ para garantir estabilidade estatística (evitando formas altamente alongadas que enviesam estimadores com correção de borda).
     • O algoritmo prioriza a seleção de blocos com as menores contagens totais de pontos para maximizar o número de blocos disjuntos e manter a eficiência computacional.
   • Complemento de Bloco (Fase III): Células de grade residuais não atribuídas aos blocos são iterativamente mescladas em blocos adjacentes, expandindo as fronteiras dos blocos para o retângulo delimitador mínimo, desde que o bloco resultante permaneça disjunto de outros e satisfaça as restrições de razão de aspecto. Isso minimiza a perda de cobertura espacial.

2. Estatística de Teste Baseada em Blocos:
   Dentro de cada bloco identificado $i$, o método calcula uma estatística da função $K$ padronizada $Z_i(r)$ usando os momentos analíticos derivados do framework $KAMP$ sob uma distribuição nula de permutação de rótulos condicional.

   • A estatística de teste global $Z(r)$ é definida como uma soma ponderada das estatísticas de nível de bloco: $Z(r) = \sum w_i Z_i(r)$.
   • Os pesos $w_i$ são escolhidos proporcionais a $n_i/p_i$ (onde $n_i$ é o total de pontos e $p_i$ é a prevalência local de POIs no bloco) para dar maior peso a blocos com sinais esparsos.
   • Sob a nulidade de permutação por bloco condicional, os autores provam que, conforme o número de blocos $b \to \infty$, a estatística global $Z(r)$ converge em distribuição para uma distribuição normal padrão $\mathcal{N}(0,1)$ via Teorema do Limite Central de Lyapunov. Isso permite o cálculo rápido de valores-$p$ sem réplicas de permutação empíricas.

3. Extensão para Análise Bivariada:
   O framework é estendido para testar a colocalização espacial entre dois tipos de pontos (ex: células plasmáticas e macrófagos) usando um estimador de função $K$ bivariada, com padronização e agregação análogas ao nível de bloco.

Principais Contribuições

• Algoritmo Escalável: O desenvolvimento de um algoritmo de bloqueio espacial adaptativo $O(RC)$ que identifica eficientemente blocos retangulares válidos para padrões de pontos de grande escala, evitando a complexidade $O(n^2)$ de cálculos de pares em toda a janela.
• Framework Estatístico: A formulação de um teste de agrupamento baseado em blocos que agrega evidências locais através de uma soma ponderada, aproveitando a normalidade assintótica para inferência rápida.
• Implementação Prática: A provisão de uma estratégia de bloqueio de propósito geral aplicável a vários métodos de agrupamento escaláveis, com código disponibilizado via GitHub.

Resultados

• Estudos de Simulação:

  • Eficiência Computacional: O B-KAMP escala linearmente com o número de pontos e permanece viável para conjuntos de dados com até 100.000 pontos. Em contraste, o $KAMP$ de janela total falha devido a restrições de memória em $n \ge 40.000$, e o $KAMP$ com afinamento ($KAMP_{0.25}$) permanece computacionalmente caro. O B-KAMP é consistentemente o método mais rápido para $n$ grande.
  • Poder Estatístico: Embora os métodos de janela total geralmente alcancem o maior poder quando viáveis, o B-KAMP demonstra um poder competitivo, particularmente em raios $r \approx 0.15$ (relativo ao tamanho do bloco). Ele supera os métodos com afinamento pesado ($KAMP_{0.25}$) e mantém o controle válido do Erro Tipo I.
  • Robustez: O método mostra desempenho robusto através de variações na abundância de pontos e resoluções de grade.

• Aplicação em Dados Reais (Proteômica Espacial):

  • Aplicado a um conjunto de dados de tecido intestinal humano saudável (aprox. 2,6 milhões de células em 65 imagens).
  • O método detectou com sucesso a forte agregação espacial de células plasmáticas e a colocalização significativa entre células plasmáticas e macrófagos.
  • O B-KAMP forneceu evidência estatística mais forte (valores-$p$ menores) do que os baselines de $KAMP$ com afinamento para imagens grandes e escalou favoravelmente onde os métodos de janela total excederam a memória disponível.

Significância e Alegações
O artigo afirma que o B-KAMP oferece um equilíbrio favorável entre poder estatístico e eficiência computacional, permitindo a inferência de agrupamento espacial rigorosa para dados de proteômica espacial de alto rendimento que eram anteriormente computacionalmente proibitivos. Os autores posicionam o método não como um substituto para procedimentos de janela total em conjuntos de dados pequenos, mas como uma alternativa escalável necessária para imagens de grande escala onde os métodos tradicionais falham.

Os autores mantêm uma postura modesta quanto às limitações:

• O método é um teste por bloco condicional, o que significa que não utiliza relações espaciais através das fronteiras dos blocos, potencialmente atenuando padrões de agrupamento que abrangem múltiplos blocos e resultando em alguma perda de poder em comparação com métodos de janela total.
• O desempenho depende da resolução da grade inicial e da natureza gananciosa (greedy) do passo de complemento de bloco (Fase III).
• Trabalhos futuros sugeridos incluem a seleção de grade orientada por dados, otimização global para formas de blocos e extensões para dados espaciais 3D.