Double cut and join (abbreviated as DCJ) is a popular rearrangement operation, and the problem of sorting permutations by DCJs can be used to approximately estimate the evolutionary distance between two genomes. Although this problem has been widely studied, most of the existing work on sorting permutations by DCJs didn’t consider repeats around the breakpoints. Recent studies revealed that the breakpoints of rearrangement events are closely related to repetitive segments. To better mimic the rearrangement operations between genomes in reality, here we present a new rearrangement model called flanked DCJ, which requires the two breakpoints of a DCJ to be cut at the same relative side of a pair of repeats. We first investigate the decision problem of sorting signed permutations by flanked DCJs, which asks to check if a genome can be transformed into another by a series of flanked DCJs, and give an \(O(n^2)\) time decision algorithm. Then, for the optimization version of sorting signed permutations by the minimum flanked DCJs, we show that it can be solved in \(O(n^2)\) when each repeat appears at most three times, and prove the NP-hardness of the general case.

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

On Sorting Signed Permutations by Flanked DCJs

  • Xin Tong,
  • Haitao Jiang,
  • Daming Zhu,
  • Lianrong Pu

摘要

Double cut and join (abbreviated as DCJ) is a popular rearrangement operation, and the problem of sorting permutations by DCJs can be used to approximately estimate the evolutionary distance between two genomes. Although this problem has been widely studied, most of the existing work on sorting permutations by DCJs didn’t consider repeats around the breakpoints. Recent studies revealed that the breakpoints of rearrangement events are closely related to repetitive segments. To better mimic the rearrangement operations between genomes in reality, here we present a new rearrangement model called flanked DCJ, which requires the two breakpoints of a DCJ to be cut at the same relative side of a pair of repeats. We first investigate the decision problem of sorting signed permutations by flanked DCJs, which asks to check if a genome can be transformed into another by a series of flanked DCJs, and give an \(O(n^2)\) time decision algorithm. Then, for the optimization version of sorting signed permutations by the minimum flanked DCJs, we show that it can be solved in \(O(n^2)\) when each repeat appears at most three times, and prove the NP-hardness of the general case.