Suponha que um único indivíduo infectado esteja escondido em uma população de \(1.000\) pessoas. Quantos testes diagnósticos são necessários para identificar essa pessoa positiva com \(100\,\%\) de certeza?

O senso comum sugere testar todas as \(1.000\) pessoas uma a uma — exigindo \(1.000\) testes. No entanto, a matemática e a teoria da informação revelam algo surpreendente. Se pudermos misturar (agrupar ou fazer pooling de) amostras biológicas de modo que um único teste responda à pergunta binária «Há pelo menos uma amostra positiva nesta mistura?», então uma busca adaptativa por divisão binária requer apenas \(10\) testes. Mais impressionante ainda: mesmo que fixemos todo o padrão de mistura antecipadamente e executemos todos os testes simultaneamente em uma única rodada paralela (teste em grupo não adaptativo), apenas algumas dezenas de testes são suficientes para identificar o indivíduo positivo sem nenhum reteste.

O que parece mágica é um pilar da matemática discreta, estatística, teoria de códigos e teoria da informação conhecido como Group Testing (Teste em Grupo / Pooling) e busca combinatória (Combinatorial Search). Neste artigo, percorremos toda a sua estrutura matemática: desde o artigo histórico de Robert Dorfman em 1943 e os limites inferiores de entropia de Claude Shannon, passando pelo clássico problema das 12 moedas e a busca binária generalizada de Hwang, até as matrizes \(d\)-disjuntas (códigos sobrepostos) de Kautz e Singleton sobre corpos finitos (Reed-Solomon), o sensoriamento comprimido (Compressed Sensing) e a triagem genômica de alto rendimento (P-BEST).

1. O avanço de 1943: O pooling em duas etapas de Robert Dorfman

1.1 A Segunda Guerra Mundial e o gargalo do teste de Wassermann

A história matemática do Group Testing nasceu em dezembro de 1943, quando o estatístico norte-americano Robert Dorfman publicou no The Annals of Mathematical Statistics seu artigo clássico de seis páginas “The Detection of Defective Members of Large Populations”.

Durante a Segunda Guerra Mundial, o Exército dos EUA precisava testar milhões de recrutas para sífilis usando o exame de sangue de Wassermann. Como a prevalência \(p\) era baixa (tipicamente \(p \approx 0{,}01\) a \(p \approx 0{,}001\)), testar cada soldado individualmente desperdiçava mais de \(99\,\%\) dos testes apenas para confirmar resultados negativos.

Dorfman propôs um procedimento de agrupamento em duas etapas (Two-Stage Pooling): dividir os \(N\) indivíduos em grupos disjuntos (pools) de tamanho \(k\).

1. Etapa 1 (Teste do Pool): Misturar as \(k\) amostras do grupo e realizar \(1\) único teste na mistura combinada.
   • Se o pool testar Negativo (probabilidade \((1 - p)^k\)): todos os \(k\) indivíduos são declarados negativos de uma só vez, consumindo apenas \(1\) teste!
   • Se o pool testar Positivo (probabilidade \(1 - (1 - p)^k\)): pelo menos um membro é positivo; avança-se para a Etapa 2.
2. Etapa 2 (Reteste Individual): Testar individualmente cada uma das \(k\) amostras originais do pool positivo (consumindo \(1 + k\) testes no total para esse grupo).

  flowchart TD
    A["Dividir N amostras em pools disjuntos de tamanho k"] --> B["Etapa 1: Testar a mistura de k amostras (1 teste)"]
    B --> C{"Qual é o resultado do pool?"}
    C -- "Negativo: probabilidade (1 - p)^k" --> D["Todos os k indivíduos confirmados como negativos!<br/>(Total de testes consumidos: 1)"]
    C -- "Positivo: probabilidade 1 - (1 - p)^k" --> E["Etapa 2: Testar individualmente os k membros<br/>(Total de testes consumidos: 1 + k)"]

1.2 Derivação analítica do tamanho ótimo de pool \(k^*\)

Para um pool de tamanho \(k\), o número esperado de testes é \(\mathbb{E}[T_{\text{pool}}] = 1 \cdot (1 - p)^k + (1 + k)[1 - (1 - p)^k] = 1 + k[1 - (1 - p)^k]\). Dividindo por \(k\), obtemos o número esperado de testes por pessoa \(f(k) = \frac{\mathbb{E}[T]}{N}\):

Vejamos com números concretos o impacto dessa lei da raiz quadrada:

• Quando a prevalência é \(p = 0{,}01\) (\(1\,\%\)): o tamanho ótimo do pool é \(k^* \approx \frac{1}{\sqrt{0{,}01}} = 10\) (ótimo inteiro exato: \(k^* = 11\)), e o custo cai para \(\frac{\mathbb{E}[T]}{N} \approx 0{,}20\) teste por pessoa (exato: \(0{,}1956\)). Testar \(1.000\) pessoas exige apenas \(196\) testes em vez de \(1.000\) — uma redução imediata de \(80{,}4\,\%\)!
• Quando a prevalência é \(p = 0{,}0001\) (\(0{,}01\,\%\)): o tamanho ótimo é \(k^* = 100\) e o número esperado de testes cai para \(0{,}02\) por pessoa, eliminando \(98\,\%\) de todos os testes!

2. O Limite Inferior da Teoria da Informação (Counting Bound e Entropia de Shannon)

Qual é o número mínimo absoluto de testes exigido pelas leis da informação para qualquer algoritmo concebível?

1. Limite Combinatório de Contagem (Counting Bound): Se existem \(d\) positivos entre \(N\) itens (\(S \subset [N], |S| = d\)), há \(\binom{N}{d}\) subconjuntos possíveis. Como cada teste binário \(\{0, 1\}\) fornece no máximo \(1\) bit de informação de Shannon, \(T\) testes produzem no máximo \(2^T\) vetores de resultados distintos: \(2^T \ge \binom{N}{d} \implies T \ge \log_2 \binom{N}{d} \approx d \log_2 \frac{N}{d} + O(d)\)
2. Limite Probabilístico da Entropia de Shannon: Se cada item é positivo independentemente com probabilidade \(p\), a entropia conjunta do vetor de estado \(\mathbf{X} \in \{0, 1\}^N\) é \(N \cdot H_2(p)\), exigindo: \(\frac{\mathbb{E}[T]}{N} \ge H_2(p) = -p\log_2 p - (1-p)\log_2(1-p)\)

3. Group Testing Adaptativo vs. Não Adaptativo

3.1 Divisão Binária Adaptativa de Hwang e o Problema das 12 Moedas

No Group Testing adaptativo, cada pool é escolhido dinamicamente com base nos resultados anteriores:

• Para \(d = 1\), a busca binária (Binary Splitting) corta o espaço de candidatos pela metade a cada teste, atingindo exatamente \(\lceil \log_2 N \rceil\) testes (\(10\) testes para \(N = 1.000\)).
• Para \(d \ge 2\), o algoritmo de divisão binária generalizada de Frank K. Hwang (1972) testa subgrupos de tamanho \(2^\alpha \approx n/d\) para que as probabilidades de resultado positivo e negativo fiquem próximas de \(1/2\) (\(1\) bit de entropia por teste), alcançando o ótimo assintótico \(T = d \log_2(N/d) + O(d)\).

Esse mesmo princípio governa o famoso problema das 12 moedas e a balança de dois pratos (1945): entre \(12\) moedas há \(1\) moeda falsa, mais pesada ou mais leve (\(12 \times 2 = 24\) hipóteses). Uma balança fornece \(3\) resultados \(\{-1, 0, +1\}\), extraindo até \(\log_2 3 \approx 1{,}585\) bits por pesagem e distinguindo até \(3^3 = 27 \ge 24\) estados em \(3\) pesagens. Colocar \(6\) moedas contra \(6\) na primeira pesagem impede o equilíbrio (\(0\)), deixando \(12 > 3^2 = 9\) estados (impossível resolver!). É preciso colocar \(4\) moedas no prato esquerdo, \(4\) no direito e deixar \(4\) de fora, dividindo as \(24\) hipóteses em \(8 : 8 : 8\) e resolvendo o enigma em \(3\) pesagens.

O gargalo prático em PCR e genômica: Como cada ciclo de RT-PCR leva cerca de \(3\) horas, executar \(10\) etapas adaptativas em série levaria \(30\) horas! Por isso, laboratórios de diagnóstico em massa precisam do Group Testing não adaptativo (NAGT), onde todos os \(T\) testes rodam simultaneamente em uma única etapa.

4. Group Testing Não Adaptativo (NAGT) e Matrizes \(d\)-Disjuntas

4.1 A Matriz de Pooling \(\mathbf{M}\) e a Superposição OR Booleana

Kautz e Singleton (1964) formalizaram o teste não adaptativo por meio de uma matriz binária \(\mathbf{M} \in \{0, 1\}^{T \times N}\), onde \(M_{i, j} = 1\) indica que a amostra \(j\) entra no pool \(i\). O vetor de resultados \(\mathbf{y} \in \{0, 1\}^T\) é a superposição OR booleana das colunas do conjunto positivo \(S\) (\(|S| \le d\)):

4.2 Matrizes \(d\)-Disjuntas e Decodificação COMP em Tempo Linear

Uma matriz \(\mathbf{M}\) é chamada \(d\)-disjunta (\(d\)-Disjunct Matrix) se o suporte de nenhuma coluna \(j_0 \notin S\) estiver contido na união dos suportes de quaisquer outras \(d\) colunas \(S\):

Isto é, para cada indivíduo negativo \(j_0 \notin S\), existe pelo menos um «teste testemunha» (linha \(i^*\)) do qual \(j_0\) participa (\(M_{i^*, j_0} = 1\)), mas nenhum dos \(d\) positivos participa (\(y_{i^*} = 0\)).

  flowchart TD
    subgraph DisjunctPT["Estrutura Geométrica de uma Matriz d-Disjunta"]
        ColS["Superposição OR das d colunas positivas<br/>y = ⋁_{j ∈ S} M_{*, j}"]
        ColJ["Coluna de qualquer amostra negativa j0 ∉ S<br/>M_{*, j0}"]
        Witness["Linha testemunha garantida i*:<br/>M_{i*, j0} = 1 E y_{i*} = 0 (O teste i* dá Negativo!)"]
        ColS --> Witness
        ColJ --> Witness
        Witness --> Result["A amostra negativa j0 nunca é mascarada por S:<br/>Decodificação COMP em tempo O(TN) sem falsos positivos!"]
    end

Graças a essa propriedade, o algoritmo COMP (Combinatorial Orthogonal Matching Pursuit) decodifica \(\mathbf{y}\) em tempo linear \(O(TN)\): basta eliminar todas as amostras que participam de algum teste negativo; as amostras sobreviventes são exatamente as positivas! Enquanto o limite inferior combinatório de D’yachkov-Rykov / Ruszinkó / Füredi exige \(T = \Omega\left(\frac{d^2}{\log d} \log N\right)\) linhas, construções probabilísticas e algébricas atingem \(T = O(d^2 \log N)\).

4.3 Grade 2D («Falsos Positivos Fantasmas») e Polinômios de Reed-Solomon

Ao organizar \(N = 100\) amostras em uma grade \(10 \times 10\) (\(10\) pools de linha + \(10\) pools de coluna = \(20\) testes), \(d = 1\) positivo é identificado na interseção única (\(1\)-disjunta). Porém, se houver \(d = 2\) positivos em \((2, 4)\) e \((6, 9)\), as linhas \(R_2, R_6\) e colunas \(C_4, C_9\) positivam, criando dois «positivos fantasmas» (Ghost Positives) em \((2, 9)\) e \((6, 4)\)!

Kautz e Singleton eliminaram os fantasmas associando a cada amostra \(j\) um polinômio \(P_j(x) \in \mathbb{F}_q[x]\) de grau \(\le k-1\) sobre um corpo finito \(\mathbb{F}_q\) (código de Reed-Solomon, \(N = q^k\)) e formando pools segundo \(y = P_j(x_m) \pmod q\) em \(w \ge d(k-1)+1\) direções. Como dois polinômios distintos de grau \(\le k-1\) se cruzam em no máximo \(k-1\) pontos, a matriz resultante é estritamente \(d\)-disjunta!

5. Ruído, Sensoriamento Comprimido (Compressed Sensing) e P-BEST

1. Efeito de Diluição e Group Testing Ruidoso: Contra diluição viral e erros laboratoriais, matrizes \((d, 2e)\)-disjuntas garantem \(2e+1\) linhas testemunhas (decodificador NCOMP), aliadas à propagação de crença (Belief Propagation) e programação linear (LP).
2. Dualidade com o Compressed Sensing: O sensoriamento comprimido é o gêmeo algébrico contínuo em \(\mathbb{R}\) do Group Testing booleano.
3. Canais de Acesso Múltiplo e Triagem COVID-19 P-BEST: Da resolução de colisões sem fio (algoritmo em árvore de Capetanakis) e Count-Min Sketch em roteadores ao protocolo clínico P-BEST (Shental et al., Science Advances 2020), que usa uma matriz de Reed-Solomon \(48 \times 384\) para testar \(384\) pacientes em apenas \(48\) reações PCR simultâneas em uma única rodada (aumentando em \(8\) vezes a capacidade de testes), o Group Testing demonstra o poder extraordinário da matemática combinatória.