How Many Subjects Does a Clade Need? Tree-Wavelet Sparsity for 16S Phenotype Models

Most microbiome studies that sequence the 16S rRNA gene, a short bacterial "barcode" gene read to identify which bacteria are present, have dozens to a few hundred subjects and thousands of distinct sequence variants. The standard way to find which bacteria predict a disease is a sparse regression that assumes only a few variants matter. It treats every combination of variants as equally plausible a priori, so the number of subjects it needs grows with the logarithm of the total number of variants. Biology does not work that way. When a disease shifts the microbiome, it usually moves a whole lineage together, occasionally with a sub-lineage moving the opposite way. We propose to write disease signals in a "tree wavelet" basis built on the bacterial family tree: one coefficient per branching point, measuring how abundance splits between the two sub-lineages. We then require the nonzero coefficients to form connected ancestral paths. The claim is that this reduces the number of subjects needed to recover the right lineages from roughly "number of relevant variants × log(total variants)" to roughly "number of relevant branch points × log(number of branch points)". We also claim this reduction can be measured as a shift in the recovery phase transition on real 16S count data, not only on Gaussian toy problems.

The practical question is concrete. For a cohort of a given size and sequencing depth, can we tell whether a lineage-level effect is recoverable at all? And does the answer change depending on which tree we trust: a named taxonomy, a phylogeny inferred from the short sequenced region, or data-driven sequence groupings? A method that answers this is useful for study design as well as for analysis. It also directly answers the "why not just collapse to genus" objection, because within-genus sign flips are exactly the deeper tree coefficients that genus aggregation throws away.

Core Claim

Let $z_i \in \mathbb{R}^p$ be the log-abundance profile of subject $i$ over $p$ sequence variants (after a pseudocount), and let $y_i$ be a phenotype. We fit a log-contrast model $y_i \approx z_i^\top \beta$ with $\sum_j \beta_j = 0$. The zero-sum constraint makes the model invariant to each sample's arbitrary total read count, which is the usual fix for compositional data. We then reparameterize $\beta = H\theta$, where $H$ is the orthonormal tree-Haar basis. Each column of $H$ is attached to one internal node $v$ and contrasts the leaves under the node's left child against those under its right child. Under this basis a "whole clade shifts together" effect needs one or a few coefficients rather than one per variant, and any such $\beta$ automatically sums to zero. We estimate

$$\hat\theta = \arg\min_\theta \frac{1}{2n}\|y - ZH\theta\|_2^2 + \lambda \sum_{v} w_v \|\theta_{\mathcal{D}(v)}\|_2,$$

where $Z$ stacks the $n$ subjects' log-profiles, $\mathcal{D}(v)$ is the set of node coefficients in the subtree below and including $v$, and $w_v$ are depth-balancing weights of the kind introduced by Tree-Guided Group Lasso. Because these groups are nested rather than arbitrarily overlapping, the penalty zeroes out whole subtrees. A deep coefficient can therefore be active only if its ancestors are. This is the hierarchical persistence pattern that Convex Approaches to Model Wavelet Sparsity Patterns used for image wavelets. The nesting also lets the proximal step be computed by a single leaves-to-root pass of group shrinkages, with no variable duplication. That removes the memory blow-up the file flags for replicated overlapping groups at ASV scale.

The quantitative prediction comes from Universal Measurement Bounds for Structured Sparse Signal Recovery. For $k$ active groups out of $M$ with maximum size $B$, that paper shows exact recovery at about $(\sqrt{2\log(M-k)}+\sqrt{B})^2k + kB$ Gaussian measurements, and group Lasso matched this at about 380 measurements for $p=2000$ where plain Lasso failed. In our setting a measurement is a subject. The design is not Gaussian: it is log-transformed multinomial counts with 80–90% zeros. We therefore expect the threshold to scale in the same way as that bound, with a constant that grows as sequencing depth falls. Estimating that constant empirically on real data is itself a contribution.

Relation to Prior Work

Four lines of prior work matter here.

The closest microbiome work uses the tree but not as a sample-efficiency device. The Logistic-Tree Normal model, A tree-based model for addressing sparsity and taxa covariance in microbiome compositional count data, splits counts along the tree's binary branchings and observes that signal concentrates at ancestral nodes, which it compares to Haar wavelets. That observation motivates us. However, LTN is a Bayesian differential-abundance model with no statement of how many subjects are needed and no predictive sparse estimator. We turn its energy-concentration observation into a sparsity assumption and test it for sample complexity. PGLasso weights a graphical lasso by pairwise phylogenetic distance and gains substantially in community recovery (ARI 0.194 vs 0.022 for plain GLasso on buccal mucosa). This supports the value of the tree, but it uses a pairwise penalty on networks, not hierarchical support on a phenotype model. Tree-Guided Group Lasso places its tree over response tasks rather than input features, and it warns that tree errors hurt. We reuse its weighting scheme and take its warning as a required experiment.

The second line supplies theory and algorithms. Beyond the universal bound above, Learning with dynamic group sparsity shows that clustered supports with unknown cluster locations need $O(k + q\log(n/q))$ measurements. It provides our hedge for when the tree is wrong: a tree-free, neighbor-aware alternative whose "neighbors" come from sequence similarity. All of this theory assumes linear Gaussian sensing, and our job is to find out how much of it survives count data.

The third line is predictive models that use the tree heuristically. PopPhy-CNN lays the tree onto a grid for a convolutional net and edges out Random Forest. Sequence-based biomarkers group ASVs by shared nucleotide variants and feed the groups to Random Forest. Both beat flat baselines, but neither offers sparse, lineage-level supports or a sample-size account. SBB groupings are also a candidate alternative "tree" in our misspecification study.

The fourth line constrains our design. The taxonomic-resolution literature, Overcoming Taxonomic Resolution Limits, documents opposite-acting strains within a single genus. That rules out any design that forces within-clade coefficients to be equal. The Haar basis is chosen because it allows exactly those deeper sign flips.

Research Program

We will build a solver for the nested tree-Haar group penalty with the zero-sum log-contrast model, for both linear and logistic losses, that scales to trees with several thousand ASV leaves. We will pair it with a semi-synthetic benchmark that plants lineage effects into real 16S count tables.

The benchmark works as follows. We take real control-group count tables, from DIABIMMUNE controls and the HMP body-site data, which keep their true sparsity, depth variation and taxon covariance. We generate phenotypes from planted $\theta$ supports with $k$ active branch points, including some within-genus sign-flip configurations. We then subsample subjects and rarefy reads to chart recovery probability against $n$ and depth. This gives an empirical phase-transition diagram. From it we fit the constant relating the observed threshold to the Recht-style formula, and we check whether the threshold tracks $\log M$ or $\log p$ as the tree is refined from genus down to ASV level.

Tree misspecification gets its own experiment. We fit the same planted signals using four trees: a taxonomy tree, a phylogeny inferred from the sequenced V3/V4 region only, an SBB-derived hierarchical grouping, and trees with increasing fractions of randomly swapped subtrees. The planted signal is always defined on a reference phylogeny, so every other tree is wrong to a measured degree. We will also fit a hedged penalty that adds a small plain-$\ell_1$ term on $\beta$. It should degrade gracefully when the tree is wrong, and the question is how much sample efficiency it gives up when the tree is right.

Baselines

The naive reference point is predicting the training-set majority class or mean. This gives AUC 0.5 for classification and recovers no support. Every method must also clear a permutation-null version of itself. To do so, we rerun each method on shuffled phenotypes and report the recovery and AUC it attains by chance.

The structure-blind competitor is the zero-sum log-contrast Lasso on ASV log-abundances. It is the direct counterpart of our model with the tree removed, and it is the fairest single test of the claim. It gets the same features, the same cross-validation folds, and an equally sized grid for $\lambda$. We beat it if, on the semi-synthetic benchmark, the subject count at which 90% support recovery is reached is materially lower. Our pre-registered target is a reduction of at least a quarter; for reference, Bayesian structured spike-and-slab priors report about 35% data savings from structure. We also require no loss in held-out AUC on real cohorts.

The aggregation baseline collapses reads to genus and family and then runs the same log-contrast Lasso. It is the practitioner's default. It should win when true effects are genus-uniform and lose on the sign-flip configurations, and we report the two regimes separately.

The strongest existing predictive methods are Random Forest on SBB features and PopPhy-CNN. On real cohorts, Improved detection of disease-associated gut microbes using 16S sequence-based biomarkers reports ROC-AUC 0.64 for autism (115 sibling pairs, V4) and 0.84 for obesity (196 obese and 61 lean twins, V3, 3-locus SBBs). PopPhy-CNN reports mean AUC 0.940 on cirrhosis versus 0.932 for Random Forest. The cirrhosis data are metagenomic rather than 16S, so we treat that comparison as secondary. We will rerun all of these under our own cross-validation splits with matched hyperparameter search budgets, and we will also quote the published numbers. We do not expect to beat Random Forest decisively on AUC. The claim is matching it, within the cross-validation standard error, while returning a sparse lineage-level support that is stable across folds, which we measure by support overlap across bootstrap resamples.

For differential-abundance-style support recovery, LTN is the strongest structured competitor. On the semi-synthetic benchmark we score it by ranking nodes by its posterior evidence. We found no reported numeric AUC on Lacuna for LTN's simulations; the file gives only a qualitative advantage over MaAsLin2 and DirFactor.

Two ablations isolate the key ingredient. The first applies a plain $\ell_1$ penalty in the Haar coordinates, which keeps the change of basis but removes the ancestral-path constraint. The second runs the full method on a tree with leaves randomly permuted, which keeps $M$ and $B$ but destroys the biology. If the gain comes from the basis alone, or survives on the shuffled tree, the claim fails.

Why not just…?

Why not just run a log-contrast Lasso on ASVs? On Gaussian problems, the file's evidence is that structure-blind Lasso fails where group methods succeed at the same measurement count: Universal Measurement Bounds and the Cameraman results in Convex Approaches to Model Wavelet Sparsity Patterns, with MSE 0.0043 vs 0.0031. But this evidence is not on count data. Heavy zero-inflation may make the log-abundance design so ill-conditioned that neither method recovers anything at realistic $n$. The phase-transition diagram settles this directly. If the Lasso and our method have the same threshold, the proposal's central claim is false.

Why not just aggregate to genus and use standard tools? If effects really are genus-uniform, aggregation is a cheap special case of our model: it keeps only the upper-tree coefficients. It should do nearly as well there, and we expect to show this. It cannot represent opposite-acting strains within a genus, which the resolution literature (Zhao et al., Yu et al.) documents. Our sign-flip plants quantify how much signal aggregation erases. Our method picks the depth adaptively instead of fixing it in advance.

Why not just use Random Forest or PopPhy-CNN, which already predict well? On AUC alone they are a real threat, and we may not beat them. Their output, however, is a feature-importance ranking with no support guarantee and no statement of how many subjects are needed. The question here is recoverability and study sizing, not a leaderboard. We will report honestly if nonlinear models dominate on AUC. Separately, a phase-transition analysis of Random Forest importance rankings on the same planted benchmark tests whether they recover lineages as sample-efficiently.

Why not just use LTN? LTN already exploits ancestral energy concentration. It may match us on support recovery at the cost of MCMC runtime. If it does, the contribution narrows to the sample-size theory and the fast convex solver, and the head-to-head recovery curves will show which is the case.

Proposed Experiments

The decisive experiment is the semi-synthetic phase transition on DIABIMMUNE and HMP control tables, run across trees refined from family down to ASV level. If structure helps as claimed, the tree-Haar method's threshold in $n$ should grow roughly with $\log M$ and stay nearly flat as ASV count rises, while the ASV Lasso's threshold grows with $\log p$. Both thresholds should inflate as rarefaction depth falls. The shuffled-tree ablation should collapse our method's threshold to the Lasso's.

The second check is misspecification. We plot threshold against the fraction of swapped subtrees for the pure and hedged penalties. This lets us report the point at which a wrong tree becomes worse than no tree, and whether SBB groupings or region-specific phylogenies land closer to the reference.

The third check is the real autism and obesity cohorts. Methods are compared on held-out AUC against the SBB Random Forest figures of 0.64 and 0.84, and on bootstrap stability of the selected lineages. For DIABIMMUNE, we check whether the recovered supports include the Bacteroides, Parabacteroides and Firmicutes/Bacteroidetes splits that LTN reported, which is an external consistency test rather than a ground truth.