arXiv preprint ·
Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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; 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Populations & Evolution
Earth embeddings are decomposable records of the land surface
LLM Evolution in a Simple Simulated Market
Counting approximate breakpoint medians of random genomes
Lossless Reductions and Hybrid Sampling for Phylogeny Using the Maximum Compatibility Criterion
Can AI Do Formal Demography? Why Vaccinating the Oldest Saves Both the Most Lives and the Most Years of Life
Get the few papers worth your time in Populations & Evolution every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.