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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Randomized FPT Approximation Algorithm for Sorting Unsigned Genomes by Translocations: Breaking the 1.375 Approximation Barrier

  • Chengcheng Sun,
  • Haitao Jiang,
  • Guojun Li,
  • Daming Zhu

摘要

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.