Papers for

software engineers in string algorithms

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Approximation algorithm cuts steps in complex genome reordering

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

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

Mon 21 SeptData Structures and Algorithms

The gist

The paper deals with a problem of rearranging parts of chromosomes by swapping prefixes, which is important in understanding genome changes. The authors focus on a situation where all intermediate genome pieces stay available for further use. They developed the first efficient method that approximates the minimal number of swaps needed to transform one set of chromosome pieces into another. Their approach works efficiently for both single and multiple target pieces, improving the understanding of how difficult these rearrangements are to approximate.

Open → 2609.25420v1