Abstract. In comparative genomics, a transposition is an operation that exchanges two consecutive sequences of genes in a genome. The transposition distance, that is, the minimum number of transpositions needed to transform a genome into another, is, according to numerous studies, a relevant evolutionary distance. The problem of computing this distance when genomes are represented by permutations, called the Sorting by Transpositions problem, has been introduced by Bafna and Pevzner [3] in 1995. It has naturally been the focus of a number of studies, but the computational complexity of this problem has remained undetermined for 15 years. In this paper, we answer this long-standing open question by proving that the Sorting by Transpositions problem is NP-hard. As a corollary of our result, we also prove that the following problem [8] is NP-hard: given a permutation π, is it possible to sort π using d b (π)/3 permutations, where d b (π) is the number of breakpoints of π?
Also, very recently, it has been proved that Sorting by Transpositions is NP-Hard REF .
Sorting by Transpositions is Difficult
ArXiv
ArXiv
Mathematics Computer Science