Microbiome studies sort millions of DNA reads from one marker gene into bins called operational taxonomic units (OTUs), which stand in for species. The usual rule is a single similarity cutoff: reads that are 97% identical go in the same bin. That rule is wrong in a known way. Different lineages evolve at different rates, so one cutoff splits fast-evolving species into several bins and merges slow-evolving species into one. One bacterium can also carry several slightly different copies of the marker gene, and the cutoff counts those copies as separate organisms. Lexical semantics has faced the same problem with dictionaries that divide word meanings too finely, which researchers call "sense explosion." One answer from that field is a "tree cut": choose the level of a meaning hierarchy that best compresses observed usage data, under the Minimum Description Length (MDL) principle. MDL picks the model that gives the shortest total code for the model plus the data.
We propose to carry the tree cut over to sequence clustering, with one change that has no counterpart in the linguistic version. The cut has to compress both the sequences and how their abundances move together across samples. Two copies of the marker gene from the same genome appear in a fixed ratio in every sample. Two distinct species do not. A code that charges extra for varying within-unit proportions will therefore merge gene copies and split real species, separately in each lineage, and it needs no labeled reference sequences. If this works, the method gives OTU-like discrete features with adaptive resolution for uncultivated microbes, the regime where the current adaptive method cannot run.
Core Claim
The claim is that one unsupervised criterion can recover species-level units better than any single global threshold and approach the label-dependent VI-cut. The criterion is an MDL cut on a dendrogram of reads, scored jointly on sequence divergence and on the stability of member proportions across samples. The sample-covariation term is the key ingredient. It is what lets the cut collapse copies of the marker gene within one genome, a failure mode that thresholds cannot see. As a secondary claim, units chosen this way should make better features for downstream disease classifiers than 97% OTUs or a fixed genus rank, because over-splitting spreads one organism's signal across several sparse columns.
Where the Idea Comes From
The motivating evidence on the biology side comes from Alignment and clustering of phylogenetic markers - implications for microbial diversity studies. On 1,677 Ribosomal Database Project (RDP) sequences from 49 known species, that paper found that the distance threshold explains 56% of the variation in clustering quality. Even well-tuned standard pipelines produced 56 OTUs. The best species-level threshold ranged from 0.01 to 0.07 across clades within one dataset. The paper's fix, VI-cut, sets thresholds per branch, but it needs labeled reference sequences. That requirement is exactly what is missing for uncultivated lineages. We keep VI-cut's idea of cutting a hierarchy at variable depth and replace its supervision with a compression criterion.
The method itself comes from Tree-Cut and a Lexicon Based on Systematic Polysemy. That work chose a cut through WordNet by minimizing description length on corpus counts. It reduced verb polysemy from 3.57 to 2.82 senses per verb and recovered 89% of the manually listed related-sense ("cousin") relations. It also merged senses that recur together in a systematic way, such as bottle as a container and bottle as a unit of measure. Gene copies within one genome are the biological analogue of that systematic polysemy: one entity appearing at several leaves of the tree. The paper also reports a limitation, failures on true homonyms. We expect a matching failure from chimeric reads, which are sequencing artifacts stitched together from two organisms and which sit between distant clades. We treat these as a known risk.
The intermediate-node approach in GPLSI: Word Coarse-grained Disambiguation aided by Basic Level Concepts supports the general bet that mid-level units help. However, it chooses those nodes from hand-built WordNet relation density, and no equivalent exists for novel sequences.
Two lines of work act as design constraints. Bayesian nonparametric sense models such as AdaGram (Breaking Sticks and Ambiguities with Adaptive Skip-gram; Bartunov et al.; Chang et al.) over-split meanings and are sensitive to hyperparameters. That argues for a criterion with no granularity knob, which MDL provides in principle. Results on downstream tasks, such as fine-grained sense assignment making retrieval worse than plain keyword search (Word Sense Disambiguation for Information Retrieval) and coarse subjectivity groupings making disambiguation feasible (Akkaya et al.), warn that granularity errors carry into later stages. That is why we evaluate classifier performance, not just cluster agreement.
The Criterion
We build a hierarchical dendrogram $T$ over the unique reads, using alignment and average linkage, the combination the 2010 study found most consequential. Each internal node $v$ of $T$ chooses between two options, "stop" (all reads below it form one unit) and "split" (each child is handled separately). The total code length is
$$ L(\Gamma) = \sum_{v \in \Gamma} \Big[ L_{\text{model}}(v) + L_{\text{seq}}(v) + L_{\text{abund}}(v) \Big]. $$
Here $\Gamma$ is the set of nodes chosen as units. $L_{\text{model}}(v)$ is the cost of describing unit $v$: its consensus sequence and a per-unit substitution rate. $L_{\text{seq}}(v)$ is the cost of encoding each member read as differences from that consensus under the rate. $L_{\text{abund}}(v)$ is the cost of the sample-by-read count table restricted to $v$'s members, given the unit's total count in each sample.
The abundance term is the new part. When $v$ stops, its members must share one proportion vector across all samples, and we encode it as a multinomial with that fixed vector. When $v$ splits, each child receives its own count in each sample, and we encode those counts under a Dirichlet-multinomial with per-sample freedom. That extra freedom costs code length, and it pays off only when members really vary independently.
Gene copies within a genome co-vary almost perfectly, so stopping is cheap for them. Two species that bloom in different samples make the fixed-proportion code expensive, so the node splits. Because every cost is local to one node's decision, the best cut can be found exactly by bottom-up dynamic programming, the same way the lexical tree cut is computed. The method has no threshold to tune. The only modeling choices are the substitution model and the Dirichlet-multinomial prior, and we report sensitivity to both.
Research Program
The work has three parts. First, we implement the cut and two ablations. One ablation keeps only the sequence term, which tests whether MDL on divergence alone already gives adaptive thresholds. The other keeps only the abundance term.
Second, we build benchmarks with known ground truth that include the failure modes thresholds cannot detect. We start from the 49-species RDP set. Using the full-length sequences there and in Greengenes and the Human Oral Microbiome Database, we attach several copies of the marker gene to a subset of species. Where real distinct copies exist we use them, and otherwise we generate within-genome variants at divergences matched to published ranges. We then simulate between 50 and 500 samples by drawing species abundances from Dirichlet-multinomial community models with controlled cross-sample covariance. We include adversarial cases: pairs of distinct species with strongly correlated abundances, which break the method's assumption, and injected chimeras. We repeat everything on reads truncated to the V4 region. Evaluation of 16S rRNA gene sequencing for species and strain-level microbiome analysis showed that V4 reads leave 56% of sequences unclassified at species level, so this is where gains from sequence divergence alone should shrink and the abundance term should matter most.
Third, we test on real data. One dataset is the 490-subject stool cohort for screen-relevant colonic neoplasia (SRN) from A Framework for Effective Application of Machine Learning to Microbiome-Based Classification Problems. The other is the vaginal microbiome collections used for Edge PCA. In the vaginal data we know a clinically meaningful split, L. iners versus L. crispatus, which Edge Principal Components and Squash Clustering found on its second principal component, which carried 24% of variance. A useful cut has to keep that split while merging elsewhere.
Baselines
The naive reference point is the fixed 97% identity threshold applied to the same dendrogram, which is what most of the cited clinical studies use. A stronger version of the same idea is the oracle global threshold. We sweep the cutoff and keep the value with the best Variation of Information against the true species. Variation of Information (VI) is an information-theoretic distance between two clusterings, where lower means closer agreement. This oracle sees the labels, so beating it shows that adaptivity matters and not just good tuning. The 2010 study reports that well-tuned standard methods produce 56 OTUs for 49 species, and we will reproduce that figure as a calibration check.
The strongest existing competitor is VI-cut from Alignment and clustering of phylogenetic markers - implications for microbial diversity studies. It cuts the same kind of tree at variable depth using labeled references, which is the same goal as ours with supervision added. We will give it the same dendrogram and alignment, and vary the fraction of labeled sequences from 50% down to 0%. Within the file there is no reported VI value for VI-cut on the RDP set, only the qualitative finding that it reduces species inflation, so we will rerun it ourselves.
We count our method as succeeding if it matches VI-cut at moderate label fractions without using any labels, and beats it once labels cover less than about a quarter of clades. We expect such gaps in the uncultivated regime. Beating VI-cut when it has full labels is not the goal.
Two baselines isolate the key ingredient. The first is the sequence-only MDL ablation. The second is a post-hoc correlation merge, which first clusters reads at 97% and then merges any OTUs whose abundances across samples correlate above a tuned cutoff. Both get the same tuning budget, a grid search on held-out simulation seeds.
For downstream prediction we feed every feature set into L2-regularized logistic regression with identical cross-validation splits. On the SRN cohort, the cited paper reports a median AUROC of 0.680 for L2 logistic regression on standard OTUs and 0.695 for random forest. AUROC is the area under the receiver operating characteristic curve; 0.5 is chance and 1.0 is perfect. We will reproduce both, and count a win if our features raise logistic regression clearly above 0.680, toward or past the random forest, at a fraction of the random forest's 83.2-hour training cost. We also compare against collapsing features to the genus rank.
We include the hierarchical feature engineering approach surveyed in Application of Machine Learning in Microbiology. We found no reported result for it on Lacuna on SRN, so we will run it on the same splits.
Why not just…?
Why not just tune one global threshold better? The 2010 study already answers most of this. The best threshold ranges from 0.01 to 0.07 across clades in one dataset, so any single value over-splits some clades and merges others. Our oracle-threshold baseline gives this alternative the labels it would need to be at its best. Per-clade error breakdowns will show where it fails. If adaptivity brings no gain beyond the oracle, the central claim is wrong and we will report that.
Why not just use VI-cut with whatever references exist? Where good references exist, that is a reasonable choice, and we do not claim to beat it there. The label-fraction sweep is designed to locate the crossover point. If VI-cut stays ahead even with very few labels, our method's value shrinks to the operon-merging ability that VI-cut lacks, and the gene-copy benchmark tests that ability separately.
Why not just merge OTUs whose abundances are correlated? This is the most serious threat to the gene-copy part of the claim. The correlation merge can only merge, never split an over-merged 97% bin, and its correlation cutoff is one more global knob. On our adversarial benchmark, distinct species with correlated abundances should fool a correlation rule more than a joint code, because our code still charges for the sequence divergence between them. If the tuned correlation merge matches our method on gene copies and on VI, we will simplify the proposal to the sequence-only MDL cut followed by that merge.
Why not skip clustering and denoise to exact sequence variants? Exact-variant methods remove sequencing errors, but each distinct gene copy within a genome then becomes its own feature, so they make the copy-inflation problem worse. We found no reported result for exact-variant pipelines on these benchmarks on Lacuna. We will add denoised variants as an input to every method, including ours, rather than treating them as a rival.
Why not let a regularized or tree-aware classifier sort it out downstream? The cited results show that sparse linear models are competitive. Logistic regression comes within 0.015 AUROC of random forest. Hierarchical Sparse Bayesian Multitask Model with Scalable Inference for Microbiome Analysis reaches about 64% balanced accuracy at Family rank using very few features. That paper still fixes the rank in advance, though, and a regularizer cannot repair counts that were split or merged wrongly before it sees them. The downstream comparison runs the same regularized model on each feature set, so any gain comes from the units themselves. If gains appear only in cluster agreement and not in AUROC, we will say plainly that the method improves diversity estimates but not prediction.
Decisive Checks
Three results would settle the proposal. First, on the simulated benchmark with gene copies, the full criterion should give lower VI and a species count closer to 49 than the oracle global threshold. It should also beat the sequence-only ablation by a margin that grows on V4-truncated reads. Second, the method should beat the correlation-merge baseline on the adversarial species pairs with correlated abundances. Third, on real data it should keep L. iners and L. crispatus as separate units while compressing the vaginal feature table, and it should raise L2 logistic regression above the reported 0.680 median AUROC on SRN.
As a small check in the other direction, we will run the same abundance-aware cut on WordNet with SemCor document counts, treating documents as samples. This asks whether co-variation across documents reproduces Tomuro's systematic-polysemy merges. That would show the criterion is a general solution to granularity mismatch and not a tool that works only for microbiome data.
References
- Alignment and clustering of phylogenetic markers - implications for microbial diversity studies
- Tree-Cut and a Lexicon Based on Systematic Polysemy
- GPLSI: Word Coarse-grained Disambiguation aided by Basic Level Concepts
- Breaking Sticks and Ambiguities with Adaptive Skip-gram
- Inducing Word Sense with Automatically Learned Hidden Concepts
- Word Sense Disambiguation for Information Retrieval
- Subjectivity Word Sense Disambiguation
- Evaluation of 16S rRNA gene sequencing for species and strain-level microbiome analysis
- A Framework for Effective Application of Machine Learning to Microbiome-Based Classification Problems
- Edge Principal Components and Squash Clustering: Using the Special Structure of Phylogenetic Placement Data for Sample Comparison
- Application of Machine Learning in Microbiology
- Hierarchical Sparse Bayesian Multitask Model with Scalable Inference for Microbiome Analysis