After antibiotic growth promoters were banned, farms lost their blanket chemical shield against gut pathogens in young animals. That shift makes it valuable to know, early and cheaply, which pens and which animals carry an emerging pathogenic lineage. Examples are an enterotoxigenic E. coli strain or Salmonella. With that knowledge, targeted alternatives such as bacteriophages or synbiotics can go where they are needed, instead of feeding antibiotics to everyone. Sequencing every animal costs too much. The obvious fix is to pool fecal samples and sequence the pools. Turning pooled counts back into per-animal answers is then a decoding problem, of the kind coding theorists analyze with density evolution: a method that predicts, for very large systems, the sharp prevalence threshold below which an iterative decoder recovers everything and above which it fails.
This note proposes treating pooled full-length 16S rRNA sequencing as a vector-valued counting group test. The 16S rRNA gene is the standard bacterial barcode gene. Many bacteria carry several slightly different copies of it, and the copy pattern differs between closely related strains. A pool sequenced across the full gene therefore returns a count for each copy variant, not a single number. We propose to design two-layer pooling graphs around this richer readout and to analyze them with density evolution. In these graphs, pen-level hubs forward cheap, undecoded measurements instead of making local calls, and a central sequencer resolves the copy-variant counts. The point of the two layers is to avoid the bottleneck that hierarchical retesting creates when each pen must be "decoded" before results move on.
Core Claim
Existing graph-based quantitative group testing assumes each test returns one integer: the number of positive items in the pool. The binary scheme is Low-Density Parity-Check Codes and Spatial Coupling for Quantitative Group Testing, and its non-binary bundled extension is LDPC Codes for Quantitative Group Testing with a Non-Binary Alphabet. Both analyze an ideal, noise-free adder channel. Separately, Evaluation of 16S rRNA gene sequencing for species and strain-level microbiome analysis showed two things. Full-length long-read 16S resolves within-genome copy variants that act as strain fingerprints, which separates E. coli K-12 from O157:H7. Short V4 reads fail to classify 56% of sequences at the species level.
We claim that combining these facts changes the decoding problem in a useful way. Suppose each target lineage $k$ has a known copy-variant fingerprint $\mathbf{c}_k$, a vector of how many copies of each 16S variant its genome carries. Then the reads from pool $j$ follow
$$\mathbf{y}_j \sim \mathrm{Multinomial}\Big(R_j,\ \propto\ \mathbf{b}_j + \textstyle\sum_{i \in \partial j}\sum_k x_{ik}\, a_{ik}\, \mathbf{c}_k\Big).$$
Here $R_j$ is the read depth, $\mathbf{b}_j$ is background reads from the resident community at those variants, $\partial j$ is the set of animals in the pool, $x_{ik}\in\{0,1\}$ says whether animal $i$ carries lineage $k$, and $a_{ik}$ is its abundance. Each check node in the decoding graph therefore sees a vector, and the vector is shared by lineages only through overlapping fingerprints. Density evolution for this check node should give a higher decodable-prevalence threshold than collapsing the reads to a scalar count. It should also let several lineages be screened at once, the way non-binary bundles raised thresholds in the Mashauri et al. work. The gain should hold under realistic read-sampling noise, which no existing quantitative group testing analysis includes.
The second ingredient borrows from relay coding. In decode-and-forward relaying, an intermediate node must fully decode before forwarding, so the end-to-end rate is capped by the weakest first hop and local errors propagate (Deniz Gunduz et al.; Kamel Tourki et al.). Classical Dorfman retesting has the same shape. A pen pool is called positive or negative locally, and only positive pens are retested. A missed call at the pen is final, and the decision delays everything downstream.
Cooperative Binning for Semideterministic Channels showed that relays can help without decoding by forwarding bin indices. Bilayer Low-Density Parity-Check Codes for Decode-and-Forward in Relay Channels built this as two-layer graph codes analyzed by "bilayer density evolution," reaching thresholds within 0.24 dB of two Shannon limits at once. We reuse that method, not its wireless setting. Pen hubs run a cheap, noisy scalar assay, such as quantitative PCR (qPCR) for the lineage. They then forward both the soft measurement and a physical aliquot into central sequencing pools defined by a second graph. The central decoder treats pen measurements and sequencing pools as two layers of one graph.
Research Program
The theoretical work extends density evolution to the vector multinomial check node. Messages are distributions over each animal's lineage state. Because the check output is continuous-ish and high-dimensional, we will use Monte Carlo (population) density evolution, the standard fallback when exact recursions are intractable. We will report its discretization error against large finite simulations, in the spirit of the concentration results of Häger et al..
We will then carry the bilayer recursion of the bilayer LDPC paper over to a graph with a low-degree qPCR layer and a sequencing layer. Pen layer degree, sequencing degree, and read depth per pool will be optimized for a fixed reagent budget. Spatial coupling along barn rows is a secondary design knob. Andriyanova et al. explain why coupling should push the iterative threshold toward the optimal one. The noise-free group testing results show it more than doubling the threshold, from 0.57% to 1.28% at variable-node degree 10.
The decoder is a peeling and belief-propagation hybrid. It adapts the lower/upper-bound message passing of the non-binary group testing work to vector checks. Fingerprints $\mathbf{c}_k$ and the error model, including homopolymer insertion and deletion errors, come from PacBio circular consensus sequencing of reference strains, following Johnson et al.
The application regime constrains the design honestly. 16S carriage tells us which lineage an animal carries. It does not say which resistance genes that lineage holds. The surveillance target is therefore pathogenic or emerging lineages whose presence should trigger targeted non-antibiotic interventions, such as bacteriophages (Zeng et al.) or synbiotics (Ding et al.). The method does not measure resistance directly.
Pooling also only pays at low prevalence. The threshold computation will tell us where the method stops being worthwhile, and that boundary is a deliverable in its own right.
Baselines
The naive reference point is individual testing: one full-length 16S library per animal. It is exact up to sequencing error, but it costs one test per animal. Every pooled design must beat it on tests per animal at matched false-negative and false-positive rates. A second naive point is individual short-read V3–V4 sequencing, the protocol used in the livestock trials. Examples are the Tibetan piglet FMT study (Zhang et al.) and the probiotic plus herbal medicine trial (Ji et al.). We include it to quantify how often short reads simply cannot tell the target lineage from commensals.
The strongest existing pooling method is single-layer graph-based quantitative group testing with the spatially coupled and bundled designs of Mashauri et al. Applied to sequencing, it collapses the reads at the target lineage into one scalar count per pool. Their reported numbers are noise-free thresholds. Spatial coupling at degree 10 raises the decodable prevalence from 0.57% to 1.28% (Low-Density Parity-Check Codes and Spatial Coupling for Quantitative Group Testing). Bundles of size 10 reach 0.774% versus 0.635% binary at a 5% test rate (LDPC Codes for Quantitative Group Testing with a Non-Binary Alphabet). We will re-run their designs under our multinomial read noise, with the same reagent budget, the same simulated herds, and the same degree-optimization effort. That re-run is the comparison that counts. Beating it means a higher noisy threshold at equal test rate, or fewer tests at equal error, for at least two simultaneous lineages.
The hierarchical competitor is Dorfman pen-then-animal retesting, the "decode-and-forward" analog, with its pen threshold tuned on held-out simulations. Two ablations isolate the key ingredients. The first replaces the vector check with the scalar total count over the same graph, which isolates the copy-variant fingerprint. The second removes the qPCR layer and gives its budget to extra sequencing pools, which isolates the bilayer relay design.
Why not just…?
Why not just use Dorfman pooling by pen? It is simple and widely trusted. At very low prevalence it may come close to our design. The cost is that every pen-level miss is permanent, and the retesting round adds a turnaround delay, mirroring the error-propagation and latency penalties of full decoding at relays (Sameer Pawar et al.). We will treat it as a real threat. If our two-layer design does not beat tuned Dorfman by a clear margin in tests per animal at matched sensitivity, for prevalence between roughly 0.1% and 2%, the relay ingredient should be dropped.
Why not just collapse reads to one count and use existing group testing decoders? This is exactly the scalar ablation. Collapsing throws away the copy-pattern information that distinguishes lineages sharing the most abundant variant, and it forces a separate test design per lineage. If the scalar version matches the vector version in density evolution and in the wet-lab pools, the operon claim is false. We would report the scalar design with an explicit noise model as the contribution.
Why not just decode pools with non-negative least squares, as WGSQuikr does for shotgun data? WGSQuikr reconstructs community proportions from $k$-mer vectors. It reports a genus-level $\ell_1$ error of 0.644 versus 0.984 for MetaPhlAn. But it estimates proportions within one sample. It does not attribute carriage to individual animals across a pooling graph, and it comes with no threshold theory for designing pools. We will still run a non-negative least squares joint decoder over our pooling matrix as a baseline. Because it is a convex method with no iteration-by-iteration prediction, density evolution cannot be used to design for it, and it is the most plausible "simpler decoder" threat.
Proposed Experiments
The simulation benchmark builds synthetic herds of 1,000 to 20,000 animals. Background community composition and abundance distributions come from the piglet 16S data of Ji et al. (NCBI SRA PRJNA1330057). The target lineages are the E. coli K-12, O157:H7, and Salmonella-like fingerprints taken from the full-length mock community of Johnson et al. Abundances follow the Proteobacteria bloom pattern seen after lincomycin in Zhang et al. We will compare the density evolution thresholds with finite-herd simulations, report the gap, and sweep prevalence, read depth, and fingerprint overlap.
The decisive empirical check is a physical one. We will individually sequence about 200 fecal samples, spiked with graded amounts of characterized strains, using full-length PacBio. We will then physically pool aliquots according to the optimized two-layer graph and the scalar and Dorfman designs. Decoded calls are scored against the individual-sequencing truth.
The proposal succeeds if three things hold. Measured error rates sit on the same side of the predicted threshold as density evolution says. The vector check beats the scalar ablation at equal budget. The two-layer design beats tuned Dorfman. If density evolution mispredicts the physical pools by more than finite-length effects can explain, it is not a usable design tool here, and that negative result is still informative.
References
- Low-Density Parity-Check Codes and Spatial Coupling for Quantitative Group Testing
- LDPC Codes for Quantitative Group Testing With a Non-Binary Alphabet
- Evaluation of 16S rRNA gene sequencing for species and strain-level microbiome analysis
- Lossy Source Transmission over the Relay Channel
- Accurate performance analysis of opportunistic decode-and-forward relaying
- Cooperative Binning for Semideterministic Channels
- Bilayer Low-Density Parity-Check Codes for Decode-and-Forward in Relay Channels
- Deterministic and ensemble-based spatially-coupled product codes
- Threshold Saturation for Nonbinary SC-LDPC Codes on the Binary Erasure Channel
- Bacteriophage as an Alternative to Antibiotics Promotes Growth Performance by Regulating Intestinal Inflammation, Intestinal Barrier Function and Gut Microbiota in Weaned Piglets
- Effects of Lactobacillus plantarum 15-1 and fructooligosaccharides on the response of broilers to pathogenic Escherichia coli O78 challenge
- Fecal microbiota transplantation alleviates weaning stress in Tibetan piglets by modulating gut microbiota–metabolite interactions
- Synergistic effects of multi-strain probiotics and Chinese herbal medicine on growth performance and gut health in weaned piglets
- Diversity-multiplexing tradeoff of the half-duplex relay channel
- WGSQuikr: Fast Whole-Genome Shotgun Metagenomic Classification