CS Paper Radar

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

Mohammad-Hadi Foroughmand-Araabi, Sama Goliaei

cs.DS cs.CC ·submitted 2026-11-11 17:59 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DM q-bio.PE ·2026-10-10 ·Pavel Skums
similarity 0.66
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

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

cs.DM q-bio.PE ·2026-08-21 ·Takatora Suzuki
similarity 0.62
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

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

cs.DS q-bio.PE ·2026-10-22 ·Haotian Tang
code/data similarity 0.60
Abstract · 13 pages, 3 figures. Supplementary appendices (37 pages) are included as an ancillary file. Code, exact input fixtures and saved run records…

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.

0.43

Deep Generative Models for Phylogenetic Inference with Complex Evolutionary Processes

cs.LG q-bio.PE ·2026-10-13 ·Ethan Baron, Alan N. Amin, Andrew Gordon Wilson
top venue similarity 0.59
Abstract

Inference of phylogenetic trees from sequences plays a central role in understanding evolutionary relationships, with applications ranging from tracking pathogen spread to reconstructing the history of life. Conventionally, practitioners obtain posteriors over trees using likelihood-based methods like MCMC. However, likelihoods are only available for simple evolutionary models with restrictive assumptions. For realistic evolutionary models, inference using conventional methods is prohibitively expensive, inaccurate, or even impossible. In practice, practitioners settle for using as flexible a conventional method as possible, even though they expect it is misspecified. In principle, we could use simulation-based inference: simulate tree and sequence data from an evolutionary model and train a neural network to predict the posterior over trees given sequences. However it is a mathematical challenge to represent and train complex posterior distributions over trees. Here we present a flexible family of conditional generative models over trees. Our models iteratively build trees using three natural paradigms -- top-down, middle-out, or bottom-up -- and are trained using a discrete diffusion framework. For real and synthetic datasets of up to $65$ taxa and $>10^5$ tokens, our models recover MCMC posteriors much more accurately than the previous state-of-the-art simulation-based method Phyloformer 2. Finally, we compare to IQ-Tree, a popular flexible-but-misspecified conventional method. Our models match its tree estimates on simple data, but on more realistic data, our method is reliably more accurate.

0.40

Metropolis-Hastings Sampling of Phylogenetic Networks: Correcting for Symmetries

cs.DM math.CO ·2026-08-12 ·Leo van Iersel, Remie Janssen, Mark Jones, Yukihiro Murakami, Christopher Reichling
position similarity 0.59
Abstract · 33 pages, 6 figures

In phylogenetics, Metropolis-Hastings methods are commonly used to sample phylogenetic trees or networks, for example from Bayesian posteriors. These methods generally use transitions that distinguish all nodes involved, and thus require fully labelled representations of phylogenetic networks. We argue that sampling leaf-labelled phylogenetic networks demands a correction for the number of fully labelled representatives of a leaf-labelled network, or, equivalently, for its internal symmetry. Without correction, there is a danger of undersampling networks with internal symmetries. We show that this correction can be realized by a quotient construction on the Metropolis-Hastings Markov chain, which, in practice, requires the calculation of the size of the network's automorphism group. Using $μ$-vectors, we show that the automorphism group is trivial for orchard networks, and thus also for tree-child networks and trees. This implies that a correction for symmetry is not needed when sampling only from such network classes. More generally, using our Python implementation of the algorithms in this paper, we show that using $μ$-vectors can significantly speed up calculations of automorphism group sizes and thus of Metropolis-Hastings sampling of leaf-labelled networks.

0.10

Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing

cs.DS math.STstat.ML ·2026-11-01 ·Jiale Cheng, Ziao Wang, Lei Ying
similarity 0.58
Abstract · 67 pages, 3 figures

This paper presents a near-quadratic-time algorithm that correctly matches almost all nodes of two correlated Erdős-Rényi graphs without any incorrect matches. Each graph has average degree $λ$ and its edges are subsampled from a common parent Erdős-Rényi graph with $n$ nodes, with subsampling probability $s$. The nodes of one graph are then relabeled by an unknown permutation. The algorithm is built on a test for correlated versus independent Galton-Watson trees with approximated likelihood ratios. For every constant $s>\sqrt{C_{\mathrm{Otter}}}$, where $C_{\mathrm{Otter}}\approx0.338$ is Otter's tree-counting constant, and every $λ=ω(1)$ with $λ=(\log n)^{O(1)}$, the algorithm outputs a partial matching of size $n-o(n)$ that contains no incorrect matches with high probability. If, in addition, $λs\ge(1+ε)\log n$ for a constant $ε>0$, a seeded completion step recovers the permutation exactly. In both cases, the time complexity of the algorithm is $n^{2+o(1)}$ with high probability, whereas previous polynomial-time algorithms with the same guarantees either have a time-complexity bound whose exponent goes to $\infty$ as $s$ approaches $\sqrt{C_{\mathrm{Otter}}}$ from above, or apply only when $s$ is close to $1$.

0.31

Tree Search With Distributional Predictions

cs.DS ·2026-09-26 ·Michael Dinitz, Bob Dong
theory similarity 0.57
Abstract

Learning-augmented algorithms use machine-learned predictions to improve classical algorithmic guarantees when the predictions are accurate, while retaining rigorous performance guarantees when they are not. We study this paradigm for search on trees. Given a tree $T$ containing an unknown target vertex $t$, an algorithm may query any vertex $v$ and learn which neighbor of $v$ lies on the unique path from $v$ to $t$. The goal is to find $t$ using as few queries as possible. We consider the distributional setting, in which the target is drawn from an unknown distribution $p$ and the algorithm is given a predicted distribution $\widehat p$ of unknown quality. We give an algorithm with expected query complexity $O\left(H(p)+k\log η\right)$, where $H(p)$ is the Shannon entropy of the true distribution and $η$ is the earth mover's distance between $p$ and $\widehat p$ in the tree metric. We also provide a matching lower bound that shows our algorithm is asymptotically tight. Finally, experiments on real-world and synthetic trees show that our prediction-based algorithm can use substantially fewer queries than a simple baseline that trusts the prediction completely.

0.26

Tree Edit Distance: Near-Linear-Time Approximate, Sublinear, and Dynamic

cs.DS ·2026-10-15 ·Bingbing Hu, Tomasz Kociumaka, Jakob Nogler, Barna Saha
published similarity 0.57
Abstract · SODA 2027

Tree edit distance (TED), the analog of string edit distance (ED) for hierarchical data, is the minimum number of node insertions, deletions, and substitutions transforming one labeled rooted ordered tree into another. We narrow polynomial gaps between TED and ED in near-linear-time approximation, sublinear algorithms, and dynamic algorithms. We give an $n^{o(1)}$-approximation in $O(n)$ time and, for every $0<δ<1$, a $(\log n)^{O(1/δ)}$-approximation in $O(n^{1+δ})$ time. This improves the previous near-linear-time $O(\sqrt n)$-approximation [Boroujeni et al., STOC'19] and brings TED to parity with ED in this regime up to polylogarithmic factors. With query access to the balanced-parentheses (Euler-tour) representation of the input trees, we give the first sublinear-time TED algorithm: for every $τ\in[1,n]$, it computes a $τn^{o(1)}$-approximation of $1+\mathrm{ted}$ in $O(n/τ)$ time. For dynamic TED, we give an exact algorithm with amortized update time $\tilde{O}(k^7)$ and a $(1+\varepsilon)$-approximation with amortized update time $\tilde{O}_{\varepsilon}(k)$, where $k$ caps the distance that must be reported. The exact algorithm is the first to beat recomputation in a nontrivial parameter regime. The approximation improves prior dynamic guarantees [Das et al., FOCS'25] and cannot be significantly improved in any parameter regime without a breakthrough for static $(1+\varepsilon)$-approximation of ED. All results use dynamic programming on a new hierarchical tree decomposition, analogous to partitioning strings into blocks of geometrically decreasing sizes. It combines structural properties previously achieved only in isolation, providing a framework for transferring algorithmic ideas from ED to TED, with additional ingredients addressing the obstacles in each computational setting.

0.34