CS Paper Radar

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

Haotian Tang

cs.DS q-bio.PE ·submitted 2026-10-22 05:54 UTC · v2
code/data

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.

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

Closest papers

Nearest neighbours by meaning across the whole index.

Small Maximum Likelihood on Fixed Cavender-Farris-Neyman Trees: An Approximation Scheme and Limits to Fully Polynomial Approximation

cs.DS cs.CC ·2026-11-11 ·Mohammad-Hadi Foroughmand-Araabi, Sama Goliaei
similarity 0.60
Abstract

Small Maximum Likelihood fits the edge substitution probabilities of a given phylogenetic tree to an observed alignment, summing over the unobserved ancestral states. For the binary Cavender--Farris--Neyman model, we assume a uniform root and an edge-specific substitution probability $p_e\in[0,\tfrac12]$ for each edge $e$, shared across all alignment sites. We give a deterministic polynomial-time approximation scheme. The algorithm achieves a factor of $1+\varepsilon$ for both the negative log likelihood and the loss after subtracting the uniform-root contribution. Its main step fixes ancestral sequences at one periodically spaced class of depths while summing over all remaining ancestors. A posterior entropy bound controls the cost of this restriction, and dynamic programming optimizes the resulting components over a finite parameter grid. We also give a randomized reduction from Clique showing that an FPTAS returning feasible rational edge probabilities would imply $RP=NP$. These results separate fixed-accuracy approximation from fully polynomial approximation for the same fixed-tree model.

0.19

Source Assignment: Hardness, Approximation, and Parameterized Algorithms

cs.DS ·2026-11-10 ·Ruxandra Marinescu-Ghemeci, Adrian Miclăuş, Alexandru Popa
similarity 0.59
Abstract

In Source Assignment, each pointer represents a substring of a common reference string and may have several possible source occurrences. The goal is to choose one source for each pointer while minimizing the number of distinct reference boundaries used by the selected sources. The problem was introduced by Qiu and Kingsford (Bioinformatics 2021) in the context of compact genome-graph construction. We distinguish \emph{Explicit Source Assignment}, where admissible source sets are given explicitly, from \emph{Complete Source Assignment}, where all occurrences of each pointer string are available. We show that Explicit Source Assignment has an exact value-preserving formulation as cardinality Set Cover with Pairs. For every fixed $\varepsilon>0$, it cannot be approximated within $(1-\varepsilon)\ln p$ unless $\mathrm{P}=\mathrm{NP}$, even over a binary alphabet when all pointers have length one, while known algorithms for Minimum-Weight Multicolored Subgraph give an $O(\sqrt{q\log p})$-approximation for arbitrary pointer lengths. Our main hardness result proves that Complete Source Assignment is APX-hard even over a binary alphabet, with equal pointer lengths and at most two sources per pointer. For edge-disjoint equal-length instances, we give a $3/2$-approximation and a $1.12585$-approximation when each pointer has at most two sources. We also introduce the rainbow-path length $λ$: the problem is polynomial-time solvable for $λ\le2$, and for $λ\le3$ we obtain a $(9/8+\varepsilon)$-approximation. We further give a polynomial-time test for deciding whether abstract source sets can be realized exactly as complete occurrence sets over an unrestricted alphabet. Finally, we give exact fixed-parameter algorithms for several structural parameters, and show that Complete Source Assignment is fixed-parameter tractable in the alphabet size and maximum pointer length.

0.33

How many cherry-picking sequences are needed to reduce all subtrees of a phylogenetic tree?

cs.DM math.CO ·2026-08-20 ·Bálint Kollmann, Yukihiro Murakami, Takatora Suzuki
similarity 0.59
Abstract · 21 pages, 7 figures

Phylogenetic networks are graphs that represent the evolutionary history of species. Recently, the class of orchard phylogenetic networks, which can be reduced by so-called cherry-picking sequences, has gained attention for its computational and biological aspects. In this paper, we study a fundamental question on orchards and their cherry-picking sequences by considering the CoveringNumber problem: given an orchard network $N$, how many cherry-picking sequences are needed to reduce all subnetworks of $N$? We initiate this study by considering the problem for trees. We then show that the covering number can be computed for binary trees recursively using a similar but more fine-grained notion of survival covering number. We also give a recursive formula for the survival covering number of non-binary trees. However, computing the covering number for non-binary trees appears to be considerably more challenging. For this case, we show that the covering number of star trees (whose root is adjacent to all leaves) is equivalent to the so-called SubsetConnectivity problem, which we introduce in this paper. Finally, we show that if there is no restriction on the sequence length, a single sequence of minimum length $\binom{n}{2}$ suffices to reduce all subtrees of a tree on $n$ leaves.

0.37

Finding Tree-Like Substructures in Phylogenetic Networks: ILP Approaches and Their Application

cs.DM q-bio.PE ·2026-08-21 ·Takatora Suzuki
similarity 0.58
Abstract · 12 pages, 6 figures

Phylogenetic networks model evolutionary histories that involve reticulate events, but their structural complexity makes them difficult to interpret. Extracting their simple substructures both clarifies the evolutionary pathways and quantifies the complexity of the networks themselves. For a given rooted almost-binary phylogenetic network, the Level Minimization problem asks for a spanning subgraph that has the same root and leaf-set and whose level is minimum, i.e., which is as close to a tree as possible. Networks for which the minimum level is zero are known as tree-based networks and can be recognized in linear time. However, Level Minimization is NP-hard in general. State-of-the-art algorithms rely on exhaustive searches of the solution spaces and hence apply only to networks of limited size. In this paper, we propose two methods for Level Minimization using integer linear programming: an exact formulation for finding such a subgraph of level at most one, and a heuristic formulation for the general case. Computational experiments confirmed the practicality of both formulations. An application to ancestral recombination graphs suggests that the minimum level provides an alternative measure of the topological complexity of an inferred network.

0.24

A Compact Weight-Space Integer Programming Formulation for Balanced Minimum Evolution

cs.DM ·2026-10-08 ·Leonid Chindelevitch, Matthew Penn, Samir Bhatt
benchmark similarity 0.58
Abstract · 44 pages, 1 figure

Balanced Minimum Evolution (BME) reconstructs an unrooted binary phylogenetic tree from a distance matrix $D$ by minimizing the length $\sum_{i<j}D_{ij}w_{ij}$, which is linear in the weights $w_{ij}=2^{-d_T{ij}}$. We study the formulation of BME in these $\binom{n}{2}$ weight variables. Theoretical results. (i) For a fixed topology $T$, the Kraft equalities, the cut equalities $\{W[S]=\tfrac12\}$ of $T$, and the single convex constraint $\sum w_{ij} \log_2 w_{ij} \leq \tfrac{3}{2}-n$ admit exactly one point, the tree's weight vector. (ii) For every tree and every bipartition, the cut value $W_T[S]$ lies in $\{\tfrac{1}{2}\} \cup \{\tfrac{3}{4}\} \cup [\tfrac{7}{8}, \infty)$; the value $\tfrac{3}{4}$ is attained exactly by the $2(n-3)$ bipartitions created by one nearest-neighbour interchange; and the number of bipartitions with $W_T[S]\le1$ is $2n^2-10n+15$ for every binary topology. (iii) The crossing graph of nontrivial bipartitions has an edge clique cover with $O(n^4)$ cliques, and every edge clique cover needs $Ω(n^2)$. (iv) The necessary conditions of Catanzaro et al. for a path-length matrix, without the four-point condition, are sufficient for $n \leq 11$ and first fail at $n=12$. Computational results. A compact branch-and-bound solver built on these results, which commits and forbids splits and imposes the convex constraint exactly, certifies optimality on benchmark instances with up to $n=20$ taxa within an hour. It is faster than the distance-indexed model of Catanzaro et al. on two of these instances and slower on the others; that model, whose root bound is tighter, certifies 13 of 14 benchmark instances with $n \leq 30$ within an hour in every seed. Although the compact solver does not improve on the computational state of the art overall, we explain why, and we discuss the open problems that our results raise.

0.30

Load Balancing with Item Fragmentation and More Bins than Items: Linear-Time and Exact

cs.DS cs.DC ·2026-11-06 ·Ben Bals, Tomáš Flouri, Kassian Kobert, Solon P. Pissis, Leen Stougie
theory similarity 0.57
Abstract

We study a fundamental load-balancing problem in which $N$ items of strictly positive integer sizes with total size $W$ must be assigned to $B$ bins, with items allowed to be divided into integer-size fragments across bins. Each bin must receive a load of either $\lfloor W/B \rfloor$ or $\lceil W/B \rceil$, ensuring that the loads of any two bins differ by at most one unit. Under this constraint, the objective is to minimize the maximum number of distinct item fragments placed into any single bin. This problem is NP-hard and there exists an $(\mathrm{OPT}+1)$-approximation algorithm that runs in $O(N \log N + B)$ time [Kobert et al., 2014]. The existing algorithm is employed by several widely used production codes for phylogenetic reconstruction. Here, we focus on the case $B \ge N$, that is, bins are at least as numerous as items. This setting arises pervasively in modern parallel and distributed systems, as well as in iterative algorithms that rebalance their workload at every step. In this context, bins are machines or machine cores, and items represent computational tasks (jobs). Our central contribution is a remarkably simple $O(N)$-time algorithm that computes an optimal assignment in this setting; this assignment is encoded using $O(N)$ space. In particular, we prove that an optimum always exists in which every bin receives at most two fragments and provide a characterization of when one fragment per bin suffices. Our result strictly improves the $(\mathrm{OPT}+1)$-approximation of Kobert et al. in the many-bins setting and, together with it, yields a strongly polynomial-time $(\mathrm{OPT}+1)$-approximation algorithm for the general setting, as it removes the dependency on the number $B$ of bins.

0.26

Algorithms for Soft Tree Containment on Tree-Child Networks

cs.DS q-bio.PE ·2026-11-08 ·Erdem Ugurlu, Louxin Zhang
similarity 0.56
Abstract · 38 pages, 8 figures

Phylogenetic networks generalize evolutionary trees by allowing lineages to merge. The Tree Containment problem asks whether a network $N$ displays a tree $T$ on the same taxa. When the polytomies of $T$ reflect uncertainty rather than simultaneous divergence, the relevant notion is soft display, in which $N$ may refine the polytomies of $T$. We take it in its asymmetric reading. Soft Tree Containment is NP-hard on reticulation-visible networks even at reticulation indegree three, and it was open for a non-binary tree and a tree-child network with multifurcating tree nodes or reticulations of indegree above two. We solve this case. A cluster characterization reduces soft display to realizing all clusters of $T$ by one switching, and in a tree-child network the vertices that can realize a cluster lie on a single chain. The per-cluster requirements then form a constraint network of width one, which arc consistency decides without search, and a $2$-SAT instance when $N$ is binary. This yields, to our knowledge, the first polynomial-time algorithm for soft Tree Containment on single-labelled tree-child networks of arbitrary reticulation indegree, and a linear-time algorithm when $T$ is binary. The same method decides the symmetric variant of the problem, in which the polytomies of $N$ may be resolved as well.

0.21

2-Adic Tree Embeddings: A Modeling and Optimization Framework for Computational Phylogenetics

cs.DM q-bio.PE ·2026-10-10 ·Pavel Skums
similarity 0.56
Abstract

Phylogenetic inference is a fundamental problem in computational biology, with applications ranging from epidemiology and oncology to developmental biology and comparative genomics. Many major phylogenetic problems are NP-hard; consequently, existing methods often explore tree space using local search or MCMC based on a limited repertoire of combinatorial rearrangements. However, the size and ruggedness of tree space make it difficult for such heuristics to reliably reach optimal or near-optimal solutions. Recently, there has been growing interest in alternative approaches that embed trees into numerical spaces and apply numerical optimization techniques. However, such methods are still limited in practical applicability. We propose a new approach to phylogenetic inference based on embeddings of trees into the non-Archimedean space of $2$-adic numbers. The hierarchical organization of $2$-adic space naturally encodes tree topologies, while its rich topological, algebraic, and measure-theoretic structure provides a natural foundation for a coherent theory of tree calculus and optimization. Here, we introduce 2-adic tree embedding, establish their basic topological, probabilistic, and algebraic properties, and show that they support natural representations of tree distributions, algebraic operations, and broad classes of tree rearrangements extending standard operations such as NNI, SPR, and TBR. Building on these results, we introduce a general local search framework in which tree neighborhoods are generated by parametric families of $2$-adic polynomials. We show that even infinitely many transformations induce only quadratically many distinct neighboring trees, which can be generated in polynomial time. These results suggest a new mathematically rigorous and flexible approach to representing and exploring tree space.

0.20