CS Paper Radar

Counting approximate breakpoint medians of random genomes

Poly H. da Silva, Arash Jamshidpey, David Sankoff

cs.CE cs.DSq-bio.PE ·submitted 2026-10-29 13:35 UTC · v1
theory

Abstract

Unsigned linear unichromosomal genomes with genes labeled 1, . . . , n are represented by permutations of these labels, whose adjacencies are the unordered pairs of genes occurring consecutively. The breakpoint distance counts the adjacencies of one genome that are absent from the other, and a breakpoint median minimizes the total breakpoint distance to a given set of genomes. Deciding whether a permutation is a median often requires a minimization over the whole symmetric group, which makes the median set resistant to exact counting. We replace this global condition by a local one: a c-approximate median is a genome having at most c adjacencies absent from all the input genomes. For a fixed genome we introduce its approximate median inverse, the set of ordered k-tuples of genomes ad- mitting it as a c-approximate median, and we construct and count this set explicitly. For k genomes chosen uniformly and independently at random, this gives the probability that a given genome is a c-approximate median and the expected number of such approximate medians. The relaxation is not only technical: approximate medians and near-optimal genomes co- incide up to a shift of the tolerance that remains bounded in probability as the number of genes grows. Finally, we derive an explicit upper bound on the probability that a given genome is an exact median, and on the expected number of exact breakpoint medians.

Comment
32 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

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

An Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance

cs.DS ·2026-09-21 ·Maria Constantin, Adrian Miclăuş, Alexandru Popa
similarity 0.60
Abstract

Translocations are genome rearrangement operations that exchange prefixes of two chromosomes. We study the non-uniform non-contiguous translocation distance problem, where every string produced during the computation remains available for reuse. Given an initial set of strings $A$ and a target set $B$, the objective is to produce all strings in $B$ using as few translocations as possible. We present the first polynomial-time approximation algorithm for this problem. For a single target string of length $n$, we obtain an $O(\log n)$-approximation, and we extend the result to arbitrary finite target sets with an $O(\log N)$-approximation, where $N$ is the total length of the targets not already present in the initial set. This resolves the approximability question for the non-uniform non-contiguous case left open by Constantin and Popa (TCS 2025).

0.08

Hardness, Approximation, and Parameterized Algorithms for Asynchronous Border Minimization

cs.DS ·2026-11-12 ·Giulian Buzatu, Adrian Miclăuş, Alexandru Popa
theory similarity 0.60
Abstract

In the Asynchronous Border Minimization Problem (BMP), a set of DNA probe strings is placed on a grid and synthesized using a common sequence of nucleotide-deposition steps. At each step, every cell may accept or skip the offered nucleotide. The cost is the total number of disagreements between neighboring cells over all steps. We study both free placement, where the probes may be rearranged, and fixed placement, where their positions are given. We show that free-placement BMP on a square grid is NP-complete over three symbols. For one-dimensional BMP, we prove APX-hardness over a binary alphabet, and NP-completeness even when every probe has length two. We also obtain an $8/7$-approximation for the latter restriction. For square grids, we give a randomized $O(n^{1/4}\log n)$-approximation, improving the earlier $O(n^{1/4}\log^2 n)$ guarantee. Both free- and fixed-placement BMP on rectangular grids are fixed-parameter tractable when parameterized only by the allowed border cost.

0.24

Source Assignment: Hardness, Approximation, and Parameterized Algorithms

cs.DS ·2026-11-10 ·Ruxandra Marinescu-Ghemeci, Adrian Miclăuş, Alexandru Popa
hot direction similarity 0.59
Abstract

In Source Assignment, each pointer represents a substring of a common reference string and may have several possible source occurrences. The goal is to choose one source for each pointer while minimizing the number of distinct reference boundaries used by the selected sources. The problem was introduced by Qiu and Kingsford (Bioinformatics 2021) in the context of compact genome-graph construction. We distinguish \emph{Explicit Source Assignment}, where admissible source sets are given explicitly, from \emph{Complete Source Assignment}, where all occurrences of each pointer string are available. We show that Explicit Source Assignment has an exact value-preserving formulation as cardinality Set Cover with Pairs. For every fixed $\varepsilon>0$, it cannot be approximated within $(1-\varepsilon)\ln p$ unless $\mathrm{P}=\mathrm{NP}$, even over a binary alphabet when all pointers have length one, while known algorithms for Minimum-Weight Multicolored Subgraph give an $O(\sqrt{q\log p})$-approximation for arbitrary pointer lengths. Our main hardness result proves that Complete Source Assignment is APX-hard even over a binary alphabet, with equal pointer lengths and at most two sources per pointer. For edge-disjoint equal-length instances, we give a $3/2$-approximation and a $1.12585$-approximation when each pointer has at most two sources. We also introduce the rainbow-path length $λ$: the problem is polynomial-time solvable for $λ\le2$, and for $λ\le3$ we obtain a $(9/8+\varepsilon)$-approximation. We further give a polynomial-time test for deciding whether abstract source sets can be realized exactly as complete occurrence sets over an unrestricted alphabet. Finally, we give exact fixed-parameter algorithms for several structural parameters, and show that Complete Source Assignment is fixed-parameter tractable in the alphabet size and maximum pointer length.

0.34

NP-Hardness and a Fixed-Parameter Algorithm for Translocation Distance

cs.DS ·2026-09-16 ·Maria Constantin, Adrian Miclăuş, Alexandru Popa
theory similarity 0.59
Abstract

In this paper we study the genome rearrangements done by translocation events. Genome rearrangements were used to measure evolutionary distance between organisms since 1936 (Dobzhansky and Sturtevant). The chromosomes are represented as strings of DNA and the \emph{translocation operation} is defined as the exchange of prefixes between two strings. This operation results in the creation of two new strings (chromosomes) that can then be utilized in subsequent translocations. A translocation is referred to as \emph{contiguous} if the new strings are produced in a single copy, so each of them can be used in only one subsequent operation. When the words produced by a translocation operation are considered to have an infinite number of copies, the translocation is referred to as \emph{non-contiguous}. If the exchanged prefixes are of equal length, the translocation is called \emph{uniform}. Otherwise, the translocation is termed \emph{non-uniform}. The \emph{translocation distance} between two sets of strings, termed the input set and the target set, represents the minimum number of translocations necessary to obtain all the strings in the target set via translocation operations. We prove that both the non-uniform contiguous and the non-uniform non-contiguous translocation distance problems are NP-hard over arbitrary finite alphabets, where the alphabet is part of the input. For the case in which the target set consists of a single string, we give a fixed-parameter tractable algorithm parameterized by the length of the target string.

0.42

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

Streaming algorithms for computing coresets and $k$-median clustering in the Hamming space

cs.DS ·2026-08-25 ·Taha El Ghazi, Jonas Ellert, Chien-Chung Huang, Tatiana Starikovskaya
published similarity 0.58
Abstract · Accepted to WAOA 2026

Clustering is one of the most fundamental tools in data analysis, allowing large datasets to be summarized by a small number of representative points. Given a metric space $(\mathcal{X}, \mathbb{d})$ and a set $S$ of $n$ points in this space, the continuous $k$-median clustering problem asks to find a set $C$ of $k$ points that minimizes the objective function $\sum_{s\in S} \mathbb{d}(s,C)$. When $\mathcal{X} = Σ^\ell$ is the set of strings of length $\ell$ and $\mathbb{d}$ is the Hamming distance, the continuous $k$-median clustering problem is known to be W[1]-hard when parameterized by $k$. In this work, we present the first $(1+\varepsilon)$-approximation algorithm for this problem with FPT runtime $2^{\mathrm{poly}(\varepsilon^{-1},k)} \cdot n\ell \mathrm{polylog} \; n$. An additional feature of the algorithm is that it can be implemented in streaming, requiring only $\tilde{O}_\varepsilon(\ell k + k^2)$ space. As an auxiliary tool of independent interest, we show the first streaming algorithm for computing an $\varepsilon$-coreset for continuous $k$-median clustering under the Hamming

0.42

A Better-than-$2$ Approximation for $k$-Median Part II: Stable Instances

cs.DS ·2026-10-12 ·Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann, Anupam Gupta, Antoni Jubés Monforte +4 more
similarity 0.56
Abstract · 44 + 8 pages, 8 figures

We consider the $k$-median problem on general metric spaces, subject to the condition that the instances are $β$-stable (i.e., the optimal solution using $k-1$ centers has a cost at least $(1+β)$ times that of the optimal solution with $k$ centers). We give a $(1.89+ε)$-approximation algorithm for such instances running in time $\exp(1/(β\times \mathrm{poly}(ε)))\cdot \mathrm{poly}_ε(n)$. In particular, for $β=\mathrm{poly}(ε)/\log n$ and $ε$ a tiny constant, this is a polynomial-time algorithm. This improves on previous work showing a $(2 + ε)$-approximation algorithm with similar running time [CGL+25]. Combined with the pseudo-approximation algorithm in our companion work, this results in a better-than-$2$ approximation algorithm for general $k$-median instances. Our main technical contribution is a novel nuanced analysis of local search that allows us to isolate a subset of clients on which we lose essentially nothing compared to the optimal solution, while losing an approximation factor of $3$ on the rest of the clients. We complement this with an algorithm based on sampling and partial enumeration, achieving a better-than-$2$ approximation on the rest of the clients. Trading off these two algorithms yields our final approximation.

0.28