A Randomized FPT Approximation Algorithm for Sorting Unsigned Genomes by Translocations: Breaking the 1.375 Approximation Barrier
摘要
Comparing genomes based on gene order is a classical combinatorial optimization problem in computational biology, which seeks the minimum number of genome rearrangement operations required to transform one genome into another. The problem of sorting genomes by translocations has been extensively studied over the past few decades. Computing the translocation distance is NP-hard when the input genomes are unsigned, posing significant computational challenges. A widely adopted approach to approximating this problem involves decomposing the breakpoint graph into proper alternating cycles. However, this decomposition step becomes a bottleneck in calculating the corresponding rearrangement distances, hindering the ability to achieve approximation factors better than 1.375 in polynomial time. In this paper, we propose a novel FPT (fixed-parameter tractable) approximation algorithm for the problem of sorting genomes by translocations, improving the approximation factor to \(4/3 + \varepsilon \) , thereby surpassing the long-standing best ratio of 1.375, which has held since 2016 [12]. Our algorithm employs a new randomized method for decomposing the breakpoint graph, which succeeds with high probability, \(1 - \frac{1}{e^{O(n)}}\) , as guaranteed by the Chernoff Bound. The time complexity of the algorithm is \(O(2^{d^*}\cdot n^{O(\frac{1}{\epsilon })})\) , where n represents the length of each genome and \(d^*\) denotes the optimal translocation distance.