CS Paper Radar

Metropolis-Hastings Sampling of Phylogenetic Networks: Correcting for Symmetries

Leo van Iersel, Remie Janssen, Mark Jones, Yukihiro Murakami, Christopher Reichling

cs.DM math.CO ·submitted 2026-08-12 12:07 UTC · v1
position

Abstract

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.

Comment
33 pages, 6 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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

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

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.59
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

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.58
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

Generalizing Metropolis-Hastings for DAG Sampling

cs.LG cs.AIstat.CO ·2026-10-21 ·Daniele Nikzad, Mikko Koivisto
similarity 0.58
Abstract

A fundamental challenge in Bayesian network structure learning lies in efficiently approximating the posterior distribution of directed acyclic graphs (DAGs). For large, high-dimensional datasets, the task remains beyond the capabilities of current methods. This work advances Markov chain Monte Carlo algorithms by introducing novel moves that simultaneously resample the parents for multiple nodes of the DAG. At the core of these moves is duet sampling, a new generalization of the Metropolis-Hastings algorithm that selects two proposal distributions from a pool at each iteration. One is used for generating a candidate state of the Markov chain and another for evaluating the return to the current state; both are ingredients of an appropriately crafted acceptance criterion. Pairing different proposal distributions provides additional freedom and enables constructing Markov chains that mix more efficiently than their basic Metropolis-Hastings counterparts, at no additional computational cost. Experiments show that our new moves, both individually and in combination, outperform the previous state of the art, which relies on a more restrictive pool of moves. This advantage persists even when letting the previous methods leverage duet sampling to enhance their performance.

0.20

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

Episode Clustering in Phylogenetic Networks

cs.DS q-bio.PE ·2026-08-24 ·Paweł Górecki, Agnieszka Mykowiecka, Jarosław Paszek
published similarity 0.54
Abstract · Preprint version submitted to ECCB 2026 before peer review. A revised version has been accepted for publication in Bioinformatics as part of…

The classical duplication episode clustering (EC) model introduced by Guigó et al. in the 1990s provides a foundational approach for inferring genomic duplication events crucial to understanding genome evolution. This model clusters single gene duplications from a collection of gene trees at locations in the species tree to minimize the total number of such locations, called duplication episodes. Here, we introduce NetEC, a novel extension of this problem to phylogenetic networks. To solve NetEC, we first develop a polynomial-time dynamic programming (DP) algorithm for testing whether a given set of network nodes can serve as episode locations. We then propose a main inference algorithm that utilizes this DP component to optimize the episode count; while the feasibility test runs in polynomial time, the full optimization has exponential worst-case complexity, and an optional heuristic mode is provided for larger instances. We also propose an extended episode analysis procedure that identifies additional genomic duplication candidates below reticulation nodes, complementing the main algorithm by resolving potential upward clustering of duplications induced by reticulation. We evaluate our method on simulated data and on an empirical Pandanales dataset comprising over 29,000 gene trees, demonstrating exact and accurate inference of genomic duplication events even in the presence of multiple reticulations.

0.28

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.54
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

Best Matches in Phylogenetic Networks

cs.DM q-bio.PE ·2026-09-18 ·Patricia A. Ebert, Peter F. Stadler, Marc Hellmuth
similarity 0.54
Abstract

Best match graphs (BMGs) were introduced in mathematical phylogenetics to describe the concept of closest relatives for related genes (leaves of rooted tree) in different organisms (defining leaf colors). We generalize this concept here to leaf-colored rooted networks, where least common ancestors are in general neither unique nor comparable. We characterize BMGs of rooted networks as those vertex-colored digraphs that are properly colored and satisfy an easy-to-check condition that we call the sicor-in-hub property. BMGs can be recognized in linear time and an explaining network can be constructed in quadratic time. Analogous results are obtained for reciprocal best match graphs (RBMGs), where an edge $\{x,y\}$ corresponds to pairs of vertices with different color that are mutually closest relatives.

0.15