CS Paper Radar

Best Matches in Phylogenetic Networks

Patricia A. Ebert, Peter F. Stadler, Marc Hellmuth

cs.DM q-bio.PE ·submitted 2026-09-18 12:35 UTC · v1

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.

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

Colored Interaction-Profile Realization: Complexity of Matching-Match on Spiders

cs.DS ·2026-09-12 ·Ilie Dumitru, Adrian Miclaus, Alexandru Popa
theory similarity 0.60
Abstract

Network motifs and colored local interaction patterns provide a useful way to describe the structure of complex networks. Motivated by an inverse realization perspective, we study the problem of assigning colors to the vertices of a fixed graph so that its edges realize a prescribed multiset of colored pairwise interactions. This problem is formalized by the Matching-Match Puzzle, introduced by Iburi and Uehara. We investigate how its computational complexity depends on the number of colors and on the structure of the host graph. We first prove that Matching-Match is NP-complete with only two colors, even when no vertex is precolored and the graph has maximum degree three. We then focus on spiders. We show that the problem is W[1]-hard parameterized by the number of colors even on spiders with only the body precolored. In contrast, for spiders whose legs have length at most two, we give a fixed-parameter tractable algorithm parameterized by the number of colors, allowing arbitrary precoloring. Finally, we prove NP-completeness for spiders whose legs all have length exactly three when precoloring is allowed.

0.41

Algorithms for Soft Tree Containment on Tree-Child Networks

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

A rooted tree framework for linear time ultrabubble detection

cs.DS ·2026-09-13 ·Athanasios E. Zisis, Pål Sætrom
similarity 0.58
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

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

Generalized Graph Search Trees

cs.DM cs.DS ·2026-09-08 ·Florian Krowiorz, Robert Scheffler
similarity 0.54
Abstract

Graph search algorithms and their corresponding graph search trees are commonly used in algorithmic graph theory. In recent years, the recognition problem of these graph search trees has received significant attention. So far, the research has focused on two types of search trees: first-in trees that behave like BFS-trees and last-in trees that behave like DFS-trees. The search tree paradigms differ from each other by the parent a vertex is connected to. In first-in trees, it is the first visited neighbor, while in last-in trees it is the last neighbor visited before that vertex. Here, we will generalize these concepts of graph search trees by allowing every preceding neighbor of a vertex to be the parent. We study the complexity of the recognition problem of these generalized graph search trees. We present NP-completeness proofs for most searches. We also show that the problem is trivial for Generic Search and polynomial-time solvable for several searches on bipartite graphs and chordal graphs. We also study the question how fixing the start vertex influences the complexity of the problem.

0.19

Pangenome Peeling: Decomposing Weighted Adjacencies into Path-Forest Genomes

cs.DM q-bio.GN ·2026-11-06 ·Alitzel López Sánchez, Jiazhen Leng, Natasha Ivanova, Lingling Jin, David Sankoff
theory similarity 0.54
Abstract · This is an extended version of the article of the same name submitted to the RECOMB 2027 conference

One aspect of pangenome analysis that has received little attention is the recovery of the individual genomes that gave rise to a pangenome graph. While substantial effort has focused on constructing pangenomes from collections of genomes, the inverse problem remains largely unexplored: given a pangenome represented as a set of weighted adjacencies, can we reconstruct the constituent linear genomes that underlie it? Thus we introduce the pangenome peeling problem, which seeks to decompose a weighted adjacency graph into a collection of linear genomes whose combined adjacencies reproduce the observed edge weights. This problem is particularly relevant when considering ancestral pangenomes, where the graph structure may be known or inferred, but the underlying genomes are not. As a first step toward addressing this problem, we formally define pangenome peeling and derive a lower bound on the minimum number of genomes required to explain a given weighted adjacency graph. We then present two reconstruction methods: one based on the sequential addition of edges and a second based on extracting maximum-spanning-tree structures. Both methods produce genome collections that exactly explain the input adjacency data. To evaluate the recovered sets of genomes, we compare them to the set of input genomes using a maximum-weight matching framework based on the double-cut-and-join distance with indels. Here the maximum-spanning tree approach is superior, producing sets of constituent genomes close to the simulations while the sequential addition of edges approach yields constituent genomes increasingly divergent from the input as genomes sizes increase.

0.16

Edge-wise Graph Alignments

cs.DS math.CO ·2026-11-12 ·Akbar Davoodi, Christoph Flamm, Daniel Merkle, Peter F. Stadler
similarity 0.54
Abstract

Pairwise graph ``alignments'', usually defined as maximum common subgraphs, have been considered in many application domains, including the comparison of molecular structures. Most commonly, the problem is formulated as maximum common induced subgraph (MCIS) or maximum common edge subgraph (MCES) problems. Sometimes these formulations are restricted to connected common subgraphs. Common subgraph problems readily generalize to more than two input graphs. However, this concept is fundamentally distinct from the notion of multiple sequence alignments. Abstractly, alignments are defined as super-structures from which the individual input objects are recovered via structure-preserving projections. While the mathematical construction readily applies to common induced subgraphs, it does not fully encompass the common edge subgraph problem, which is the variant more commonly employed in cheminformatics applications. In order to consistently define multiple edge-based alignments of graphs we represent a graph $G$ as E-graph $(E,\mathscr{V})$, where $E$ is the edge set of $G$ and $\mathscr{V}$ is the set of sets of incident edges. This representation implicitly encodes the vertices in terms of edge data. Alignments of E-graphs are themselves E-graphs that contain the input (E-)graphs as subgraphs. Maximum edge subgraphs correspond to maximum induced sub-E-graphs, and they can thus be computed using a slightly modified version of the VF2 algorithm without the need to switch from graphs to line graphs. Furthermore, multiple alignments of (E-)graphs yield a natural definition of a consensus graph that is ``on average'' present in the input without having to be a subgraph of every (and in fact of any) input graph.

0.33