Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references

arXiv:2610.30776 · q-bio.PE · Submitted 2026-10-22 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Genomics Radio. Generated commentary on the latest computational biology and genomics papers.

Ines: I'm Ines.

Marcus: And I'm Marcus, here with Yuki.

Ines: We're looking at the paper: "Report the tolerance, not the count".

Marcus: Here's the gist of the paper. The gist: The minimum number of strictly interior sources required to explain a phylogenetic distance profile, considering incomplete references, is more informative than providing an exact count, as it reveals how much tolerance exists for errors in reference data Model and Main Results The model defines a distance from the whole mixture to each reference as a weighted average of source-to-reference tree distances The problem asks whether a given distance profile admits an explanation with at most K sources, and if so, what the smallest such explanation is The model involves exact rational data where sources sit at points in the interiors of original edges with positive weights and a positive mean pendant Exact Algorithm and Complexity Classification The paper provides an exact algorithm for a free positive mean pendant and any nonempty set of observed leaves on a positive-rational reduced tree, achieving 2 O(K) poly(B) bit complexity However, with arbitrary missing references and a prescribed pendant, the problem is W

1: -hard in the source budget K, even on strictly binary trees supplied with a strict explanation using at most K + 1 sources The complexity classification distinguishes between different information regimes: Any nonempty subset Free y > 0 has a deterministic algorithm using O(N)+ 2O(K) rational arithmetic operations and 2 O(K) poly(B) bit time The same bounds hold with prescribed positive pendant when at most one original leaf is unobserved All, or all but one Prescribed y0 > 0 has the same upper bound as the free-positive-pendant problem, being NP-complete and no subexponential K dependence under ETH Arbitrary subset Prescribed y0 = 1 is W

1: -hard in K, even with a supplied strict (K + 1)-source explanation The lower bound matches the linear order of the exponent in K, not an optimal exponential base Tree Geometry and Localization The paper analyzes the geometry using vertex potentials and a baseline definition It defines the lower Lipschitz envelope h(v) and baseline b, Y, which are used to bound the deficit term The lemma states that if at most K sources realize f, then S = ∅ for K = 1, and also for K = 2 when every nonleaf vertex has degree at least three For K ≥ 2, the assertion is that X v∈S (deg(v) − 2) ≤ K − 2 The inverse formulas provide expressions for m and y based on b, Y, and delta Incomplete References Cost The paper investigates how removing references affects the minimum source count, finding that "the direction is a theorem at every error tolerance and held without exception in 23,545 draws" Two adversarially chosen references suffice, at the median, to destroy uniqueness of the minimum explanation, and that number does not grow with panel size (Spearman 0.203) Discarding 7,931 of 10,575 references from a real 16S panel at random costs 1.8% of the tolerance at which one source suffices The phenomenon is not unobservable in practice Discussion The classification separates three effects: a small source count localizes the unknown potential, omitted subtrees require strict original-edge lifting, and fixing the mean pendant stops off-subtree distances from being freely absorbed The last permits a parameterized hardness construction even on positive binary trees with a supplied near-budget explanation What a distance profile does support is the tolerance at which an explanation of a given size exists, and that is what we would have methods report The second is which references are absent rather than how many, a distinction worth a factor of fifty on the stool backbone The paper concludes that the minimum compatible explanation therefore need not recover the generating composition The tolerance is computable from the observed distances alone, with no error model and no ground truth, so the first thing worth checking is whether a fitted mixture’s residual exceeds it.

Ines: The second is which references are absent rather than how many, a distinction worth a factor of fifty on the stool backbone.

Marcus: The tolerance is measurable on samples that have none.

Ines: The paper also notes that "the mixture inferred by the published heuristic reproduces real observations better than the configuration that generated them in 282 of 296 cases".

Title and authors: Ines: So, to get into the specifics of "Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references," we're looking at how they frame this whole problem. It’s about moving away from just trying to find a single source count and instead focusing on how much wiggle room exists in our reference data before we can no longer reliably tell if a certain number of sources is enough.

Marcus: Right, and the authors show this by creating different information regimes—they separate problems based on whether you have arbitrary missing references or if you’re given a prescribed pendant distance. That distinction really matters for understanding how hard the problem gets.

Yuki: That classification is important because it shows that the difficulty isn't uniform across all scenarios; it depends heavily on how much structural information you are given about those missing tree parts or those specific pendant distances.

Ines: They establish that for any non-empty subset with a free positive mean pendant, there's a deterministic algorithm using two O(K) poly(B) bit complexity to find the smallest number of sources.

Marcus: But then things become much harder when you consider arbitrary missing references combined with a prescribed pendant. In that specific case, the problem is classified as Wone-hard in terms of the source budget K, even if you're supplied with a strict explanation using at most K plus one sources <ref:2610.30776#pg1> supplied with a strict explanation using at most K.

The paper's summary: Yuki: So, putting that in simpler terms, what they’re really saying is that counting the exact number of sources is hard, but measuring the tolerance for error is much more tractable and gives us a way to quantify uncertainty in the inference process.

Ines: It’s about moving beyond just finding an exact count and instead figuring out how much wiggle room there is in our reference data before we can no longer reliably tell if a certain number of sources is sufficient.

Marcus: They introduce a specific geometric framework using vertex potentials and a baseline definition, defining things like the lower Lipschitz envelope h(v) and the baseline b, Y, which are used to bound that deficit term related to the sources.

Ines: They have this lemma that states if at most K sources realize f, then for K equals one it's empty, and also for K equals two when every nonleaf vertex has degree at least three.

Yuki: That lemma is important because it sets a very low bar for what’s possible with just one or two sources in a fairly complex tree structure, suggesting that with just one or two sources in a fairly complex tree structure, we can already rule out many configurations.

The paper's improvements: Marcus: One of the key contributions they make is investigating how removing references affects the minimum source count. They found that this direction is a theorem at every error tolerance and held without exception in twenty-three thousand five hundred forty-five draws <ref:2610.30776#pg1>.

Ines: What’s really interesting here, Marcus, is what happens when you remove references; it only ever lowers the minimum source count; it never raises it.

Yuki: That sounds like a strong statement about the stability of the inference process under data loss, which is something we need to consider when dealing with real biological samples that are inherently noisy.

Marcus: They also point out that two adversarially chosen references, at the median, can destroy uniqueness of the minimum explanation, and they noted that this number doesn't grow with panel size in Spearman’s correlation of zero point two zero three <ref:2610.30776#pg1>.

Ines: So what this means for us is that which references are absent matters way more than just how many references you miss; it points toward prioritizing specific reference data rather than just counting missing entries.

Conclusion: Yuki: So, to wrap up, the paper on "Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references" suggests that what we should actually be reporting is the tolerance at which an explanation of a given size exists.

Ines: I agree. It stops us from just trying to recover the generating composition perfectly when that might even not be possible, and it gives us a measurable criterion based only on the observed distances themselves, without needing some ground truth model.

Marcus: And they found that in real-world tests, the mixture inferred by published heuristics reproduced real observations better than the configuration that actually generated them in two hundred eighty-two of two hundred ninety-six cases <ref:2610.30776#pg1>.

Yuki: That suggests that this phenomenon isn't just a theoretical exercise; it’s observable in practice when we look at real data, and focusing on that tolerance is the practical way forward.

Ines: Exactly. The exact minimum they found in four hundred fifty of one thousand nine hundred sixty-eight draws on one hundred one real reference trees by up to six sources really solidifies this approach for measuring uncertainty in these distance profiles.

Marcus: So, the main message from "Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references" is that we need a way to report what size of explanation is possible given our data constraints.

Haotian Tang

Mohamed bin Zayed University of Artificial Intelligence

q-bio.PE

Submitted: 2026-10-22

Updated: 2026-10-22

Comments: 13 pages, 3 figures. Supplementary appendices (32 pages) are included as an ancillary file. Code, exact input fixtures and saved run records: https://github.com/Haotian-Tang/recomb2027-pdd

Code: https://github.com/Haotian-Tang/recomb2027-pdd

License: http://creativecommons.org/licenses/by/4.0/

The gist: The gist: The minimum number of strictly interior sources required to explain a phylogenetic distance profile, considering incomplete references, is more informative than providing an exact count, as

Key concepts

Tolerance at which an explanation exists: This is the key finding: instead of reporting a fixed number of sources, the paper reports the tolerance level. It tells researchers how much error or deviation from perfect data is still acceptable for a given source budget K to explain the observed distances.
Source Budget Complexity Classification: This classification categorizes problems based on whether they are solvable efficiently (deterministic) or computationally hard (W[1]-hard). It helps determine if a distance profile can be reliably explained by K sources, even when references are missing or constraints are imposed.
Incomplete References Cost: The study analyzes how the absence of reference data affects the required source count. It shows that removing just a few key references can significantly impact the tolerance needed for a solution, highlighting which data points are most critical for accurate reconstruction.

Summary

The gist: The minimum number of strictly interior sources required to explain a phylogenetic distance profile, considering incomplete references, is more informative than providing an exact count, as it reveals how much tolerance exists for errors in reference data

Model and Main Results

The model defines a distance from the whole mixture to each reference as a weighted average of source-to-reference tree distances The problem asks whether a given distance profile admits an explanation with at most K sources, and if so, what the smallest such explanation is The model involves exact rational data where sources sit at points in the interiors of original edges with positive weights and a positive mean pendant

Exact Algorithm and Complexity Classification

The paper provides an exact algorithm for a free positive mean pendant and any nonempty set of observed leaves on a positive-rational reduced tree, achieving 2 O(K) poly(B) bit complexity However, with arbitrary missing references and a prescribed pendant, the problem is W[1]-hard in the source budget K, even on strictly binary trees supplied with a strict explanation using at most K + 1 sources The complexity classification distinguishes between different information regimes:

** Any nonempty subset Free y > 0 has a deterministic algorithm using O(N)+ 2O(K) rational arithmetic operations and 2 O(K) poly(B) bit time The same bounds hold with prescribed positive pendant when at most one original leaf is unobserved **

** All, or all but one Prescribed y0 > 0 has the same upper bound as the free-positive-pendant problem, being NP-complete and no subexponential K dependence under ETH **

** Arbitrary subset Prescribed y0 = 1 is W[1]-hard in K, even with a supplied strict (K + 1)-source explanation The lower bound matches the linear order of the exponent in K, not an optimal exponential base **

Tree Geometry and Localization

The paper analyzes the geometry using vertex potentials and a baseline definition It defines the lower Lipschitz envelope h(v) and baseline b, Y, which are used to bound the deficit term The lemma states that if at most K sources realize f, then S = ∅ for K = 1, and also for K = 2 when every nonleaf vertex has degree at least three For K ≥ 2, the assertion is that X v∈S (deg(v) − 2) ≤ K − 2 The inverse formulas provide expressions for m and y based on b, Y, and delta

Incomplete References Cost

The paper investigates how removing references affects the minimum source count, finding that the direction is a theorem at every error tolerance and held without exception in 23,545 draws Two adversarially chosen references suffice, at the median, to destroy uniqueness of the minimum explanation, and that number does not grow with panel size (Spearman 0.203) Discarding 7,931 of 10,575 references from a real 16S panel at random costs 1.8% of the tolerance at which one source suffices The phenomenon is not unobservable in practice

Discussion

The classification separates three effects: a small source count localizes the unknown potential, omitted subtrees require strict original-edge lifting, and fixing the mean pendant stops off-subtree distances from being freely absorbed The last permits a parameterized hardness construction even on positive binary trees with a supplied near-budget explanation What a distance profile does support is the tolerance at which an explanation of a given size exists, and that is what we would have methods report The second is which references are absent rather than how many, a distinction worth a factor of fifty on the stool backbone

The paper concludes that the minimum compatible explanation therefore need not recover the generating composition The tolerance is computable from the observed distances alone, with no error model and no ground truth, so the first thing worth checking is whether a fitted mixture’s residual exceeds it. The second is which references are absent rather than how many, a distinction worth a factor of fifty on the stool backbone. The tolerance is measurable on samples that have none.

The paper also notes that the mixture inferred by the published heuristic reproduces real observations better than the configuration that generated them in 282 of 296 cases. This suggests that the phenomenon is not unobservable in practice. The exact minimum fell in 450 of 1,968 draws on 101 real reference trees, by up to six sources. It is the tolerance at which an explanation of a given size exists that should be reported.

The code and data are available at https://github.com/Haotian-Tang/recomb2027-pdd The work provides a source-budget complexity classification and what it measures, not the PDD model or fixed-support optimization. The results are based on exact profiles where a missing entry is a removed coordinate, and from published estimated distances where the tolerance admitting an explanation of a given size is reported. The paper establishes that Position moves before magnitude when analyzing real distances The work is not a replacement for large-scale heuristic inference, but exact reference implementations.

The final conclusion is that the tolerance at which an explanation of a given size exists is what should be reported. The paper's findings are based on exact rational data and a known metric tree. The work establishes neither bounded-aspect-ratio hardness nor robustness to observational error.

The paper is published in arXiv as 2610.30776v1 on October 22, 2026 The work addresses the exact computational question of whether a given distance profile admits an explanation with at most K sources. The paper is a contribution to the field of computational molecular biology and bioinformatics.

The summary is based on the exact rational data and a known metric tree. The work establishes neither bounded-aspect-ratio hardness nor robustness to observational error. The paper is published in arXiv as 2610.30776v1 on October 22, 2026. The work addresses the exact computational question of whether a given distance profile admits an explanation with at most K sources. The paper is a contribution to the field of computational molecular biology and bioinformatics

Improvements for AI systems

Precise tolerance estimation for mixture inference allows AI systems to report the tolerance at which an explanation of a given size exists, moving beyond point estimates of source counts that are unobservable in practice. This enables better quantification of uncertainty in distance-based biological inferences.
Improved source budget complexity classification provides a framework to determine if a given distance profile admits an explanation with at most K sources, even on arbitrary missing leaves and a prescribed pendant. This helps AI systems classify the difficulty of inferring mixture compositions based on observed data constraints.
Ability to distinguish between different types of reference removal costs (e.g., whole-clade removal costs 90% versus random removal costing 1.8% at the tolerance threshold) allows AI tools to prioritize which genomic references are most critical for accurate reconstruction, rather than just counting the number of missing references.
The exact algorithm provides a deterministic method using O(N)+ 2O(K) rational arithmetic operations and 2O(K) poly(B) bit time for finding the minimum source count within a budget K. This guarantees exact, efficient computation for problems involving mixture-to-reference distances on positive-rational trees.
Implementation of the lower Lipschitz envelope and baseline filters allows AI systems to reject infeasible configurations efficiently by checking if h(r) = dr for observed leaves, effectively filtering out incorrect explanations. This acts as a measurable criterion for biological plausibility in distance profiles.
The algorithm can be used as an instrument to test the quality of existing heuristic models by checking if published distance estimates exceed it in 296 of 296 cases, providing a practical measure of how well a mixture is reproduced compared to its generating configuration.

Abstract

Phylogenetic distance deconvolution represents mixture-to-reference distances by weighted sources placed on a reference tree. We study the minimum number of strictly interior sources that explains a distance profile, and what incomplete references cost. On a positive-rational reduced tree we give an exact algorithm with 2 O(K) poly(B) bit complexity for a free positive mean pendant and any nonempty set of observed leaves. With arbitrary missing references and a prescribed pendant the problem is W[1]-hard in the source budget K, even on positive binary trees supplied with a strict explanation using at most K+1 sources. We then use the algorithm as an instrument. Removing references can only lower the minimum source count, never raise it. The direction is a theorem at every error tolerance and held without exception in 23,545 draws, so which references are missing matters more than how many. Two adversarially chosen references suffice, at the median, to destroy uniqueness of the minimum explanation, and that number does not grow with panel size (Spearman 0.203, p = 0.15, over 20 to 353 references) where random loss scales linearly. Discarding 7,931 of 10,575 references from a real 16S panel at random costs 1.8% of the tolerance at which one source suffices. Discarding comparably many as whole clades costs 90%. That tolerance needs neither ground truth nor an error model, which makes the model measurable on real data. Published distance estimates exceed it in 296 of 296 cases. The mixture inferred by the published heuristic reproduces real observations better than the configuration that generated them in 282 of 296. The phenomenon is not unobservable in practice. It is unobservable through a point estimate of the count. Methods for this problem should report the tolerance at which an explanation of a given size exists.