CS Paper Radar

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

Takatora Suzuki

cs.DM q-bio.PE ·submitted 2026-08-21 06:29 UTC · v1

Abstract

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.

Comment
12 pages, 6 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Algorithms for Soft Tree Containment on Tree-Child Networks

cs.DS q-bio.PE ·2026-11-08 ·Erdem Ugurlu, Louxin Zhang
similarity 0.66
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

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

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

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

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

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

A rooted tree framework for linear time ultrabubble detection

cs.DS ·2026-09-13 ·Athanasios E. Zisis, Pål Sætrom
similarity 0.60
Abstract · 21 pages, 3 figures

Pangenomics uses graphs to show genetic differences within or between species. In these graphs, a path can represent one genome, while regions with different paths show genetic variation. Biedged graphs use black edges for sequences and grey edges for links between them. Snarls are minimal subgraphs of a biedged graph that are separated from the rest of the graph by removing two black edges. Ultrabubbles are minimal acyclic and tip-free snarls and thus are important variant structures because they have finite paths and lack dead ends. In our previous work, we showed that in linear time every bidirected graph can be transformed to a rooted biedged bipartite one, and that in these graphs, ultrabubbles can be enumerated with a lowest common ancestor (LCA)-based method in $O(Kn)$ time, where $n$ and $K$ are the number of nodes and given snarls, respectively, of the graph. Here, we present a series of practical and theoretical improvements to our previous LCA-based approach. First, we present a hybrid method that selects between the LCA-based method and the naive approach for evaluating a snarl, depending on the size of the snarl in relation to the number of tips and cycle-closing nodes in the graph. Second, by using the theoretical framework from our previous paper, we show that all ultrabubbles can be found in $O(n + m + K)$ time, where $m$ is the number of edges, by traversing the breadth-first search (BFS) tree of the biedged bipartite graph. Third, we show that any two snarls that are candidate ultrabubbles and share a frontier node cannot be ultrabubbles; the resulting set of snarls is compatible, bound by $n$, and defines exclusive families of nested snarls. We combine these three results into six methods and present benchmarking results that illustrate how the above improvements affect practical run-times for identifying ultrabubbles.

0.24