The analysis of genomes evolving by inversions has led to a famous problem of sorting a permutation by reversals. On the other hand, during the evolution of many genomes, the involvement of repeated segments is unavoidable, which has inspired new interests on the model of sorting by signed/unsigned symmetric reversals. Recently, the signed version of this problem has been investigated. In this paper, we focus on the problem of Sorting by Unsigned Symmetric Reversals, which requires a series of unsigned symmetric reversals to transform a chromosome A into chromosome B, where chromosomes are represented by a sequence of unsigned symbols (possibly with repetitions). Our main result is on the special case where each symbol appears at most twice in a chromosome. We give a sufficient and necessary condition to answer the decision problem, and design an algorithm with approximation factor 1.5 for the corresponding optimization problem, which runs in \(O(n^4)\) time.

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

On Sorting by Unsigned Symmetric Reversals

  • Wenfeng Lai,
  • Haitao Jiang,
  • Daming Zhu,
  • Binhai Zhu

摘要

The analysis of genomes evolving by inversions has led to a famous problem of sorting a permutation by reversals. On the other hand, during the evolution of many genomes, the involvement of repeated segments is unavoidable, which has inspired new interests on the model of sorting by signed/unsigned symmetric reversals. Recently, the signed version of this problem has been investigated. In this paper, we focus on the problem of Sorting by Unsigned Symmetric Reversals, which requires a series of unsigned symmetric reversals to transform a chromosome A into chromosome B, where chromosomes are represented by a sequence of unsigned symbols (possibly with repetitions). Our main result is on the special case where each symbol appears at most twice in a chromosome. We give a sufficient and necessary condition to answer the decision problem, and design an algorithm with approximation factor 1.5 for the corresponding optimization problem, which runs in \(O(n^4)\) time.