Summary: In comparative genomics, a transposition is an operation that exchanges two consecutive sequences of genes in a genome. The transposition distance between two genomes, 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 is called the sorting by transpositions problem, and has been introduced by [V. Bafna and P. Pevzner, in: Proceedings of the 6th annual ACM-SIAM symposium on discrete algorithms. San Francisco, CA, USA: SIAM, 614–623 (1995; Zbl 0846.92007)].
It has naturally been the focus of a number of studies (see, for instance, [G. Fertin et al., Combinatorics of genome rearrangements (2009; Zbl 1170.92022)]), 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, first described in [D. A. Christie, Genome rearrangement problems. Glasgow, Scotland: University of Glasgow (Dissertation) (1998)], is NP-hard: given a permutation \(\pi\), is it possible to sort \(\pi\) using exactly \(d_b(\pi)/3\) transpositions, where \(d_b(\pi)\) is the number of breakpoints of \(\pi\)?