On Sorting by Unsigned Symmetric Reversals
摘要
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.