CS Paper Radar

A rooted tree framework for linear time ultrabubble detection

Athanasios E. Zisis, Pål Sætrom

cs.DS ·submitted 2026-09-13 23:53 UTC · v1

Abstract

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.

Comment
21 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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

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

Tree-based Algorithms for Breakpoint Median and Near-Median Genomes

cs.DS q-bio.GNmath.CO ·2026-10-12 ·Poly H. da Silva, Arash Jamshidpey, David Sankoff
similarity 0.58
Abstract

Median genomes serve as candidates for ancestral reconstruction and help study the diversity of parsimonious rearrangement solutions. However, the breakpoint median problem is NP-hard for unichromosomal genomes, and medians are non-unique, making their diversity important to study. In this paper, we develop tree-based algorithms for studying breakpoint medians of linear unichromosomal genomes represented as unsigned permutations. The algorithms construct rooted labeled trees whose leaves encode candidate median genomes satisfying local adjacency constraints derived from the inputs. We show that the resulting reduced search spaces contain all breakpoint medians while being much smaller than the full permutation space. We investigate these reduced spaces experimentally for three-genome instances. Our method finds exact medians and many near-optimal approximations, while early sampling of leaves often produces near-medians quickly. We also introduce constrained sampling procedures for targeting balanced near-medians, whose distances to the input genomes are more evenly distributed and hence are particularly relevant for ancestral reconstruction. The resulting framework provides a unified method for exact enumeration, efficient sampling, and targeted exploration of median and near-median genomes. In contrast to Traveling Salesman Problem-based approaches, which typically return a single solution and do not reveal the diversity or balance of the median set, our method can enumerate all medians, sample near-medians early, and target structurally distinct candidates under the breakpoint distance.

0.25

Best Matches in Phylogenetic Networks

cs.DM q-bio.PE ·2026-09-18 ·Patricia A. Ebert, Peter F. Stadler, Marc Hellmuth
similarity 0.58
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

Generating pivot Gray codes for spanning arborescences of complete digraphs and split digraphs in constant amortized time

cs.DS ·2026-10-27 ·Bowie Liu, Dennis Wong
similarity 0.58
Abstract

We present the first known efficient algorithm to generate pivot Gray codes for spanning arborescences of complete digraphs, listing all spanning arborescences such that consecutive arborescences differ by reassigning the outgoing edge of exactly one vertex. Our recursive algorithm generates each spanning arborescence in constant amortized time using $O(n^2)$ space. We then extend our algorithm to generate the first known pivot Gray codes for spanning arborescences of split digraphs, achieving constant amortized time per arborescence using $ O(n^2) $ space. Finally, we further generalize our approach to proper interval digraphs. When the arborescences are rooted at the leftmost interval, our algorithm generates the pivot Gray code in constant amortized time per arborescence using $ {O}(n^2) $ space.

0.20

Reportable Shortcuts with RLBWTs

cs.DS ·2026-09-06 ·Travis Gagie
similarity 0.57
Abstract

Backward search over a run-length compressed Burrows-Wheeler transform (RLBWT) takes one step per pattern character, even when long stretches of the pattern match material that recurs throughout a highly repetitive collection. We describe shortcuts: for a precomputed set of pairs $(α,β)$ of strings, a backward search that has just matched $β$ and finds $α$ immediately to its left in the pattern can cross $α$ in one step. Since a shortcut is taken only after its pair has been recognized in the pattern, the search returns a report of the shortcuts it took along with the usual BWT interval. Our motivation is pangenome graphs, where such pairs mark the places where a pattern passes through a vertex, so the report gives the path a match takes through the graph. We work out the case of a single linear reference $R$, with $β$ ranging over the length-$\ell$ windows of $R$ starting at multiples of $\ell$, and $α$ over the $2^t \ell$ characters preceding such a window. We show that the search counts correctly, that under stated conditions it crosses a stretch of the pattern matching $m$ consecutive windows of $R$ with $O(\log m + m / 2^τ)$ shortcuts, where $2^τ\ell$ is the longest shortcut, and that the shortcuts can be built efficiently from the RLBWT. On the Pizza&Chili cere collection of 37 genomes, shortcuts make backward search 2.3 to 4.2 times faster on exact patterns of length 200 to 1000, and 1.7 to 2.0 times faster with 1% of the characters substituted, for 86% more space. On 11 gigabases of genomes of seven bacterial species, they make it 1.6 to 1.9 times faster on exact patterns for 32% more space. On whole chromosome 19 haplotypes against 16 to 64 others from the Human Pangenome Reference Consortium, shortcuts in both directions make Boyer-Moore-Li search for maximal exact matches of length at least 1000 about 8 times faster.

0.26

Pangenome Optimization via Elastic Degenerate Strings

cs.DS ·2026-09-22 ·Nicola Rizzo, Sebastian Visan-Draghicescu, Nadia Pisanti, Veli Mäkinen
code/data similarity 0.57
Abstract

An Elastic Degenerate String (EDS, or ED-string) is a sequence of string sets. A pangenome, consisting of variations observed in a population along the genome sequences, can be naturally encoded as an EDS. Pattern matching and comparison problems on pangenome representations such as EDSes have been widely studied in the literature, but optimizing the pangenome properties during its construction has been largely omitted. We fill this gap by showing how methods originally developed for the related problem of founder reconstruction can be adapted to minimize, in linear time, the total cardinality of the EDS sets or the total size of the EDS strings, given suitable multiple alignments representing the input data. We provide an implementation for the minimum-cardinality criterion in a tool mincard, and conduct the first experiments on scalable pangenome optimization via EDSes. The code and experiments are available at https://github.com/algbio/eds.

0.39

Constructive Arboricity in Almost-Linear Time for Dense Graphs

cs.DS ·2026-10-09 ·Iman Gholami, Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Alireza Kaviani, Soheil Mohammadkhani +1 more
similarity 0.55
Abstract

The arboricity of a graph is the minimum number of forests needed to partition its edges. We present an algorithm that computes the exact arboricity of a simple graph and constructs an optimal forest partition in $\min\{n^{2+o(1)},m^{4/3+o(1)}\}$ time, where $n$ and $m$ denote the numbers of vertices and edges. This improves the previous $O(m^{3/2}\log(n^2/m))$ bound of Gabow. In particular, it runs in almost-linear time, $m^{1+o(1)}$, on dense graphs with $m=Θ(n^2)$. We also give an algorithm that constructs a partition into at most one more forest than optimal in $m^{1+o(1)}$ time. To our knowledge, it is the first almost-linear time algorithm for this problem.

0.22