An Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance
En palabras de los autores
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 and a target set , the objective is to produce all strings in using as few translocations as possible. We present the first polynomial-time approximation algorithm for this problem. For a single target string of length , we obtain an -approximation, and we extend the result to arbitrary finite target sets with an -approximation, where 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).
Apareció: miércoles, 23 de septiembre. arXiv. Preprint, todavía sin revisión por pares.