Multi-Study Learned Distances for OTU Clustering

Microbiome studies begin by grouping millions of noisy DNA reads into bins called operational taxonomic units (OTUs). Each bin holds reads of a marker gene, usually 16S ribosomal RNA, that are at least, say, 97% identical, and each bin stands in for a species. Every later analysis, from diversity estimates to disease prediction, works on counts of these bins. The grouping rule is a plain string distance: every position in the gene counts equally, and one fixed cutoff applies everywhere. So a mutation in a conserved structural core weighs as much as one in a hypervariable loop that actually separates organisms. We propose to learn this distance instead. The idea is a weight for each position of the gene, fit jointly across many independent clinical cohorts and a reference taxonomy, so that the resulting bins are taxonomically coherent and predictive in cohorts the method has never seen. The learned object stays small and interpretable: a per-position weighting of the alignment cost. It plugs directly into existing fast greedy clustering tools.

Multi-task learning is the right lens because the failure is shared across studies. A single cohort is too small, and too confounded by its own lab protocol, to tell us which positions matter. If the same reweighting improves bins for colorectal cancer, inflammatory bowel disease and diabetes cohorts at once, it is probably capturing biology rather than one study's noise. That is the same shared-sparsity bet that downstream multi-study models already make, moved upstream into the clustering step. Training jointly on reference taxonomy as a separate task keeps the distance anchored to evolutionary relatedness, so phenotype supervision cannot quietly turn bins into disease detectors.

Core Claim

A per-position alignment weighting, learned jointly across many cohorts and anchored by a taxonomy task, will produce OTUs that do better on held-out studies' disease prediction than equal-weight OTUs with the same number of bins. It will do this without losing accuracy on mock communities with known composition. The test is decisive because the comparison controls for the number of bins, which is otherwise the main confound when comparing clusterings by their downstream usefulness. It is also decisive because a strong alternative exists: keep very fine bins and let a sparse downstream model do the merging. The experiments are designed so that this alternative can win.

Relation to Prior Work

The motivating evidence comes from two sides. Evaluation of 16S rRNA gene sequencing for species and strain-level microbiome analysis simulated short sub-region sequencing and found that the V4 region failed to classify 56% of sequences at species level. It also showed that small differences among a genome's multiple 16S copies distinguish E. coli K-12 from O157:H7, so equal-weight clustering throws away signal before any model sees it. Learning, visualizing and exploring 16S rRNA structure using an attention-based deep neural network (Read2Pheno) trained a convolutional-recurrent network with attention on raw reads for one task at a time. Its attention concentrated on hypervariable regions V2–V4, and it clustered intermediate embeddings after the fact into "pseudo OTUs." That is evidence that position importance is learnable and uneven.

We differ from Read2Pheno in three ways. We learn the distance under many tasks at once rather than one. Our bins are defined by an explicit sequence distance, not by a deep embedding that must be rerun on every read. And we evaluate on unseen cohorts rather than within one dataset.

The methods we reuse come from the clustering literature. Better Greedy Sequence Clustering with Fast Banded Alignment combines a trie that prunes candidates by edit distance with a fast banded alignment, and scales linearly to 57 million reads. 16S rRNA metagenome clustering and diversity estimation using locality sensitive hashing (LSH-Div) replaces all-pairs alignment with hashing. Both optimize unweighted string distance against a fixed cutoff, and neither accepts any supervision. Our weighted distance keeps the trie usable. If every weight lies in $[w_{\min}, w_{\max}]$ with $w_{\min}>0$, then $w_{\min}$ times the unweighted edit count lower-bounds the weighted cost, so trie pruning remains valid and only becomes looser.

The multi-task side contributes the problem framing and its main risk. Hierarchical Sparse Bayesian Multitask Model with Scalable Inference for Microbiome Analysis (BayesMTL) treats each of 61 studies as a task and shares a sparsity prior across them. It takes a fixed abundance table as input and cannot repair upstream binning errors. We reuse its task definition and its model as the downstream predictor, but move the shared structure into the distance. Assisting Main Task Learning by Heterogeneous Auxiliary Tasks with Applications to Skin Cancer Screening showed, on dermoscopy images, that auxiliary tasks trained concurrently beat a two-step pipeline. That is the motivating precedent for joint rather than sequential training. RotoGrad: Gradient Homogenization in Multi-Task Learning constrains the design: it documents that tasks with large gradients drown out others and that opposing gradients cancel. We expect exactly this between taxonomy, which wants related sequences close, and phenotype, which may want a few-nucleotide pathogen variant pushed away from its commensal relative. We therefore measure the conflict directly rather than assume it away.

Method

Reads are placed onto the columns of the SILVA reference alignment, which gives every read, short or full-length, a shared coordinate system. The distance between reads $x$ and $y$ is

$$ d_w(x,y)=\sum_{p} w_p\,\mathbb{1}[x_p\neq y_p], $$

where $p$ indexes alignment columns, $w_p\in[w_{\min},w_{\max}]$ is the learned weight of column $p$, and $\mathbb{1}[\cdot]$ counts a mismatch or gap. Equal weights recover ordinary percent-identity clustering, so the method strictly contains the standard pipeline.

Training requires the binning step to be differentiable, so we relax it. Within each training batch, reads are softly assigned to a set of prototype sequences with probability proportional to $\exp(-d_w(x,c)/\tau)$, where $c$ is a prototype and $\tau$ a temperature. Each sample's abundance vector is the sum of its reads' soft assignments, transformed by centered log-ratio as in BayesMTL. Each study $t$ gets its own logistic head on these features, and an L1 penalty on the heads mimics the shared sparsity of BayesMTL.

The taxonomy task is a contrastive loss on SILVA sequences: pairs from the same genus should fall below the cutoff and pairs from different genera above it. The total objective is a weighted sum of the taxonomy loss and the per-study phenotype losses, plus a smoothness penalty on $w$ along the alignment. The penalty reflects that functional regions are contiguous.

At deployment the soft relaxation is discarded. The learned $w$ is plugged into the banded-alignment greedy clusterer with a hard cutoff, so production bins are ordinary hard OTUs. We record the cosine between taxonomy and phenotype gradients on $w$ throughout training. If it is persistently negative, we compare plain summation against RotoGrad-style magnitude balancing. Feature rotation does not transfer directly, because $w$ is a weight vector rather than a learned representation.

Research Program

The work has three stages.

The first builds the weighted clusterer and confirms two properties. With equal weights it reproduces standard OTU counts. With learned weights it keeps near-linear runtime on the 57-million-read collection used by Brubach et al.

The second fits $w$ on a training split of studies from the curated 61-study, 19-disease collection used by BayesMTL, together with SILVA genus labels. Studies are split, not samples, so every evaluated cohort is unseen both during weight learning and during bin construction. This split is what prevents circularity, where bins defined using disease labels would then be scored on those same labels. A dependency must be stated plainly: BayesMTL used fixed abundance tables, so we must reprocess raw reads for whichever of those studies have public raw data. The usable number of studies may be smaller than 61.

The third analyzes what the weights learned. We check whether mass concentrates in V2–V4 as Read2Pheno's attention did, and whether the learned weights split the intragenomic copy variants of E. coli K-12 and O157:H7 in the 36-species mock community and full-length data of Johnson et al.

Baselines

The naive reference point is equal-weight greedy clustering at 97% and at 99% identity using the banded-alignment tool of Brubach et al., followed by BayesMTL on the resulting tables. The strongest reported figure on the cohort collection is BayesMTL's roughly 64% balanced accuracy at Family rank (Hierarchical Sparse Bayesian Multitask Model with Scalable Inference for Microbiome Analysis). Our rerun on held-out studies with OTU features replaces that number as the operative bar, since the split and features differ. Beating it means a higher mean held-out balanced accuracy at the same number of bins, consistent across held-out studies rather than driven by one.

The strongest competitor on our actual question is very fine bins plus BayesMTL: exact sequences or 99% bins handed to a sparse multi-task model that is free to ignore and effectively merge features. It directly tests whether supervision belongs upstream at all. It gets the same studies, splits, and BayesMTL tuning budget.

The deep-embedding competitor is Read2Pheno-style pseudo OTUs: the network is trained on SILVA genus labels and its embeddings are clustered to the same number of bins. Read2Pheno reports 95.9% genus accuracy on SILVA against 97.6% for the RDP classifier. It also reports about 88% body-site accuracy on the American Gut Project against 83% for an OTU baseline. These are the reference numbers for that setting. No reported result was found on Lacuna for Gevers IBD classification.

Three ablations isolate the multi-task ingredient, all at matched bin counts. The first learns $w$ from taxonomy alone. The second learns $w$ from phenotype alone with no taxonomy anchor. The third learns $w$ from a single study. Clustering quality on mocks is compared against LSH-Div, which converged to the true 43 OTUs at a 4% cutoff on the 43-marker mock. Runtime is compared against the reported speedup of up to ten times over UCLUST at 99% similarity.

Why not just…?

Why not just cluster as finely as possible and let BayesMTL choose features? This is the real threat. A sparse model on exact sequences can in principle learn any merging that a learned distance would produce. Our counterargument is statistical. With small cohorts and thousands of rare fine features, abundance is split across near-duplicates, and the sparse model has too few samples per study to reassemble them. The fact that BayesMTL selected only 1.8% of genera shows how aggressively it discards signal it cannot pool. The fine-bins baseline settles the question. If it matches us on held-out studies, we will report that supervised clustering is unnecessary for prediction and restrict our claim to the strain-resolution and interpretability results.

Why not just learn the weights from reference taxonomy, with no phenotype tasks? This is the simpler single-task option, and it may recover most of the gain if hypervariable regions alone explain it. The taxonomy-only ablation tests this directly. The evidence that it may fall short is the Johnson et al. finding that strain-level differences relevant to pathogenicity sit within single species, where genus labels give no signal.

Why not just use Read2Pheno embeddings as pseudo OTUs? They are single-task and post hoc. They must be recomputed through a deep network for every read, and the authors report heavy cost at full gene length and weakness on rare taxa. The direct comparison at matched bin count will show whether a 1500-parameter weighting gives up any accuracy relative to the deep embedding, and the runtime comparison will show what it saves.

Why not just pretrain on taxonomy and fine-tune on each cohort? Fine-tuning gives one distance per cohort, so bins would no longer be comparable across studies, which defeats the purpose of OTUs. The single-study ablation approximates this and measures how much a cohort-specific distance overfits.

Proposed Experiments and Decisive Checks

The primary experiment is held-out-study disease classification on the reprocessed cohort collection, scored by balanced accuracy and AUROC at three matched bin counts. Supporting experiments cover four further settings. American Gut body-site prediction tests transfer to a non-disease phenotype. Gevers IBD tests Crohn's disease. The LSH-Div 43-marker mock and the Johnson 36-species mock measure adjusted Rand index against the known composition and recovery of the true number of organisms. The 57-million-read set measures runtime.

The result we would accept as a positive finding has three parts. First, learned weights beat both equal-weight OTUs and taxonomy-only weights on held-out studies at matched bin counts by a margin larger than the spread across random study splits. Second, mock-community accuracy does not degrade. Third, runtime stays within a small constant factor of the unweighted clusterer.

The result that would kill the idea is fine bins plus BayesMTL matching our learned-weight bins, or phenotype-only weights matching the joint weights. The latter would mean the taxonomy anchor and the multi-task sharing contribute nothing. Finally, the gradient-cosine logs tell us whether taxonomy and phenotype genuinely conflict on 16S. Whichever way that comes out, it is a finding the field currently lacks.