Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references
Haotian Tang
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; the single-exponential dependence on K is tight under ETH, already with every leaf observed. 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, at every error tolerance. Which references are missing then matters far more than how many. Under nearest-to-source deletion a median of two references can be erased before the generating support stops being the unique smallest explanation, and that budget stays nearly flat as the panel grows (Spearman 0.10 over 20 to 361 references, against 0.82 for random loss). 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. The generating configuration's worst-leaf residual exceeds the one-source optimum in all 296 real ANI cases, and in 248 after refitting the common pendant. The phenomenon is not unobservable in practice. A point estimate of the count alone does not quantify it. Methods for this problem should report the tolerance at which an explanation of a given size exists.
尚无 AI 解读，展示原文摘要