On the Complexity of Sorting by Reversals and Transpositions Problems

Abstract

In comparative genomics, rearrangements are mutations that affect a stretch of DNA sequences. Reversals and transpositions are well-known rearrangements, and each has a vast literature. The reversal and transposition distance, that is, the minimum number of reversals and transpositions needed to transform one genome into another is a relevant evolutionary distance. The problem of computing this distance when genomes are represented by permutations was proposed >20 years ago and received the name of sorting by reversals and transpositions problem. It has been the focus of a number of studies, but the computational complexity has remained open until now. We hereby solve this question and prove that it is NP-hard no matter whether genomes are represented by signed or unsigned permutations. In addition, we prove that a usual generalization of this problem, which assigns weights w_ρ for reversals and w_τ for transpositions, is also NP-hard as long as w_τ/ w_ρ ≤ 1.5 for both signed and unsigned permutations.

1. Introduction

Genome rearrangements are mutations affecting large portions of a genome. One classical approach to compare genomes in computational biology is by computing the number of genome rearrangements that are necessary to transform one into the other.

Owing to the principle of parsimony, we assume that a sequence with the minimum number of genome rearrangements needed to perform this task is a good estimator to the real distance between two genomes.

To compute sequences of genome rearrangements between genomes, a widely used approach is to represent both genomes by permutations, where each element in the permutation represents a gene or a conserved block that exists on both genomes. This approach requires that both genomes share the same set of genes or conserved blocks and that no repeated genes or conserved blocks exist.

When the orientation of the genes on both genomes are known, we add a “+” or “−” sign to each element, representing its relative orientation on each genome, and we say that this permutation is signed. Otherwise, signs are omitted, and the permutation is unsigned.

Several genome rearrangements were proposed in the literature starting from the 1990s, and the topic has given rise to an extensive literature since then. The most studied genome rearrangements are reversals (or signed reversals on signed permutations), wherein a fragment of the genome is reversed (and the sign of each element in this fragment is flipped on signed permutations), and transpositions, where two adjacent fragments of the genome are exchanged.

Assuming that elements of one of these permutations are mapped as an ordered permutation (and with positive signs in case of signed permutations), our task of transforming one into the other reduces to a sorting problem.

Several approaches have been used in the genome rearrangement field. Some have considered only a single rearrangement event like the NP-hard sorting by transpositions problem (Bulteau et al., 2012) and the sorting by reversals problem, which is NP-hard on unsigned permutations (Caprara, 1999) and allows polynomial algorithms on signed permutations (Hannenhalli and Pevzner, 1999). Other variants allow both reversals and transpositions (Walter et al., 1998; Rahman et al., 2008), which led to many problems such that the complexity is still open.

Many other variants of genome rearrangement have been considered, notably considering different combinations and constraints for the set of rearrangements. One of these variants assigns weights for different rearrangements, which relies on the fact that specific rearrangements are more likely to occur than others in a particular population (Blanchette et al., 1996; Yancopoulos et al., 2005). Instead of seeking for the size of a minimum length sequence as in the classical approach, problems using this variant seek for a sequence of genome rearrangements of minimum weight sum.

Oliveira et al. (2019) developed an algorithm with an approximation factor of 1.5 when reversals have weight 1 and transpositions have weight 1.5, and also investigated approximation algorithms when reversals have weight 1 and transpositions have weight in the range between 1 and 3.

Using another genome rearrangement called transreversals, Eriksen (2002) developed an algorithm with an approximation factor of 7/6 when reversals have weight 1 and transpositions and transreversals have weight 2. Bader and Ohlebusch (2007) developed an algorithm of approximation factor of 1.5 when reversals have weight 1 and transpositions and transreversals have both the weight in the range between 1 and 2.

In this study, we show that four problems with open complexity in the literature are NP-hard. Two of them are from classical versions, namely sorting by reversals and transpositions, and sorting by signed reversals and transpositions. The other two are weighted versions, and we prove that sorting by weighted reversals and transpositions and sorting by weighted signed reversals and transpositions are NP-hard if the weight of transpositions is up to 50% higher than the weight of reversals.

This article is organized as follows. Section 2 introduces the notation we use. Section 3 gives the NP-hardness proofs for the four problems. Section 4 concludes our work.

2. Definitions

We represent a genome \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal G}$$ \end{document} with n conserved blocks as an n-tuple whose elements represent conserved blocks. If the orientation of genes is known, each element has a “+” or “−” sign indicating the orientation of the represented block.

Assuming no repeated block, this n-tuple is a permutation \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi = ( { \pi _1} \;{ \pi _2} \; \ldots \;{ \pi _n} )$$ \end{document} such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left\vert {{ \pi _i}} \right\vert \; \in \; [ 1..n ]$$ \end{document} and When elements of π have signs, we say that π is a signed permutation; π is an unsigned permutation otherwise.

We aim at finding the distance between two genomes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{ \cal G}_1}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{ \cal G}_2}$$ \end{document} represented by permutations π and σ. We can assume without loss of generality that σ is the identity permutation ι = (+1 + 2 … +n), and our goal is then to sort π.

In the following, we consider that every permutation \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi = ( { \pi _1} \; \ldots \;{ \pi _n} )$$ \end{document} has two extra elements: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \pi _0} = + 0$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \pi _{n + 1}} = + ( n + 1 ).$$ \end{document} Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi [ i..j ]$$ \end{document} denote the block of consecutive elements from π_i to π_j of π, with 1 ≤ i ≤ j ≤ n.

Definition 1. A reversal is an operation ρ(i, j) that when applied to an unsigned permutation \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi = ( { \pi _1} \; \ldots \;{ \pi _n} )$$ \end{document} reverses the order of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi [ i..j ] ,$$ \end{document} with 1 ≤ i < j ≤ n:

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \pi \cdot \rho ( i , j ) = ( { \pi _1} \; \ldots \; \;{ \pi _{i - 1}} \; \underline {{ \pi _j} \;{ \pi _{j - 1}} \; \ldots \;{ \pi _{i + 1}} \;{ \pi _i}} \;{ \pi _{j + 1}} \; \ldots \;{ \pi _n} ). \end{align*} \end{document}

Definition 2. A signed reversal is an operation that when applied to a signed permutation \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi = ( { \pi _1} \; \ldots \;{ \pi _n} )$$ \end{document} reverses the order of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi [ i..j ]$$ \end{document} and flips signs of each element in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi [ i..j ] ,$$ \end{document} with 1 ≤ i ≤ j ≤ n:

Definition 3. A transposition is an operation τ(i, j, k) that when applied to a signed or unsigned permutation \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi = ( { \pi _1} \; \ldots \;{ \pi _n} )$$ \end{document} exchanges the position of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi [ i..j - 1 ]$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi [ j..k - 1 ] ,$$ \end{document} with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$1 \le i < j < k \le n + 1:$$ \end{document}

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \pi \cdot \tau ( i , j , k ) = ( { \pi _1} \; \ldots \;{ \pi _{i - 1}} \; \underline {{ \pi _j} \; \ldots \;{ \pi _{k - 1}}} \; \underline {{ \pi _i} \; \ldots \;{ \pi _{j - 1}}} \;{ \pi _k} \; \ldots \;{ \pi _n} ). \end{align*} \end{document}

Note that transpositions never change signs.

2.1. Models and distances

A model \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathcal{M}$$ \end{document} defines which set of operations are allowed to sort permutations.

Definition 4. The distance of π, denoted by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${d_ \mathcal{M}} ( \pi ) ,$$ \end{document} is the size of a minimum length sequence of operations allowed by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathcal{M} ,$$ \end{document} such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \cdot {S_ \mathcal{M}} = \iota.$$ \end{document}

One can assign weights to each operation of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathcal{M}$$ \end{document} for modeling specific biological scenarios. For example, assuming different weights for different operations. For instance, if a model allows both reversals and transpositions, we might assume that reversals have weight w_ρ and transpositions have weight w_τ.

Definition 5. Given a sequence of operations \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${S_ \mathcal{M}}$$ \end{document} allowed by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathcal{M}$$ \end{document} and weights \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${w_ \alpha }$$ \end{document} for each \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\alpha \in \mathcal{M} ,$$ \end{document} let k_α be the number of operations α in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${S_ \mathcal{M}}.$$ \end{document} We say that the cost of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${S_ \mathcal{M}}$$ \end{document} is equal to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\sum \limits_{ \alpha \in \mathcal{M}} {{w_ \alpha }} {k_ \alpha }.$$ \end{document}

Definition 6. The weighted distance of π, denoted by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d_ \mathcal{M}^w ( \pi ) ,$$ \end{document} is the minimum cost of a sequence of operations allowed by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathcal{M} ,$$ \end{document} denoted by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${S_ \mathcal{M}} ,$$ \end{document} such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \cdot {S_ \mathcal{M}} = \iota.$$ \end{document}

2.2. Breakpoints

Depending on the model, breakpoints are defined on two different ways. The number of breakpoints in a permutation π on model \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathcal{M}$$ \end{document} is denoted by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${b_ \mathcal{M}} ( \pi ).$$ \end{document}

Definition 7. Given a permutation π, a pair of elements π_i and π_i+1 from π, with 0 ≤ i ≤ n, is a breakpoint type one if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert { \pi _{i + 1}} - { \pi _i} \vert \ne 1.$$ \end{document}

Definition 8. Given a permutation π, a pair of elements π_i and π_i₊₁ from π, with 0 ≤ i ≤ n, is a breakpoint type two if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \pi _{i + 1}} - { \pi _i} \ne 1.$$ \end{document}

The following models use breakpoints from Definition 7: reversals (r) and reversals and transpositions (rt). The following models use breakpoints from Definition 8: transpositions (t), signed reversals and signed reversals and transpositions

For instance, given the extended unsigned permutation π = (0 3 2 4 5 1 6), we have that b_r(π) = 4, since the following pairs are breakpoints: (0, 3), (2, 4), (5, 1), and (1, 6). Besides, b_t(π) = 5, since the following pairs are breakpoints: (0, 3), (3, 2), (2, 4), (5, 1), and (1, 6). Given the extended signed permutation π = (+0 − 3 −2 + 1 −4 + 5 +6), we have that since the following pairs are breakpoints: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( + 0 , - 3 ) , \; ( - 2 , + 1 ) , \; ( + 1 , - 4 )$$ \end{document} , and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( - 4 , + 5 ).$$ \end{document}

Definition 9. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\Delta {b_ \mathcal{M}} ( \pi , \pi \cdot \alpha ) = {b_ \mathcal{M}} ( \pi \cdot \alpha ) - {b_ \mathcal{M}} ( \pi )$$ \end{document} denote the variation in the number of breakpoints on model \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathcal{M}$$ \end{document} after applying the genome rearrangement α allowed by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathcal{M}.$$ \end{document}

Since transpositions cut the permutation on three positions, if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathcal{M}$$ \end{document} allows transpositions \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\Delta {b_ \mathcal{M}} ( \pi , \pi \cdot \tau ) \in [ - 3..3 ].$$ \end{document} Reversals cut the permutation on two positions, so if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathcal{M}$$ \end{document} allows reversals \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\Delta {b_ \mathcal{M}} ( \pi , \pi \cdot \rho ) \in [ - 2..2 ] ,$$ \end{document} which results in the following lemma.

Lemma 10. On model rt we have that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${d_{rt}} \ge {b_{rt}} ( \pi ) / 3$$ \end{document} and given w_ρ and w_τ, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d_ { rt } ^w \ge \min \left\{ { \frac { { { w_ \rho } } } { 2 } , \frac { { { w_ \tau } } } { 3 } } \right\} { b_ { rt } } ( \pi ).$$ \end{document} On model we have that and given and w_τ,

2.3. Strips

Strips are maximal sequences of consecutive elements without breakpoints. The first strip starts with element π₀, the last strip ends with element π_n₊₁, and the remaining strips are between breakpoints.

Definition 11. On signed permutations, a strip is called positive if all elements in the sequence have positive signs, and it is called negative otherwise.

Definition 12. On unsigned permutations a strip with more than one element is called increasing if its elements form an increasing sequence; it is called decreasing otherwise. A strip with only one element π_i is called a singleton, and it is defined as increasing if i \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\in \{ 0 , \;n + 1 \} ,$$ \end{document} and as decreasing otherwise.

For instance, the extended unsigned permutation π = (0 3 2 4 5 1 6) has five strips on model rt: two increasing singletons 〈0〉 and 〈6〉, one decreasing singleton 〈1〉, one decreasing strip 〈3 2〉, and one increasing strip 〈4 5〉. The extended signed permutation π = (+0 − 3 −2 + 1 −4 + 5 +6) has five strips on model the three positive strips 〈+0〉, 〈+1〉, and 〈+5 + 6〉; and two negative strips 〈−3 − 2〉 and 〈−4〉.

Definition 13. We say that a reversal ρ(i, j) cuts a strip when applied to π if (π_i₋₁, π_i) or (π_j, π_j₊₁) are not breakpoints, that is, at least one of these pairs has consecutive elements in the same strip.

3. NP-Hardness Proofs

In this section, we prove that four decision problems related to sorting by reversals and transpositions are NP-hard. Two of them are for signed permutations and the other two for unsigned permutations.

Let π be an unsigned permutation and k = b_t(π)/3, we define B3T as the problem to decide whether the equality d(π) = k is satisfied. Bulteau et al. (2012) proved that B3T is NP-hard.

To prove that the four decision problems related to sorting by reversals and transpositions are NP-hard, we use a reduction from the B3T problem.

3.1. Decision problems for signed permutations

In this section, we show that the following problems on signed permutations are NP-hard:

Sorting by signed reversals and transpositions (SRTs): given a signed permutation π and a non-negative integer k, decide whether it is possible to sort π using up to k operations.

Sorting by weighted signed reversals and transpositions (WSRTs): given a signed permutation π, weights and w_τ, and a non-negative real number k, decide whether it is possible to sort π with cost less than or equal to k.

Let us define a preliminary lemma that will be used later on the NP-hard proof. The following lemma establishes a family of signed permutations such that no signed reversal can remove breakpoints.

Lemma 14. If a signed permutation π has only positive strips, for any signed reversal

Proof. Since signed reversals change signs of elements, a signed reversal cannot remove breakpoints if pairs \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( { \pi _{i - 1}} , { \pi _j} )$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( { \pi _i} , { \pi _{j + 1}} )$$ \end{document} are both positive or both negative. Since π has only positive strips, which means that all elements of π have positive signs, the lemma follows. ■

Theorem 15. WSRT is NP-hard when

Now we show that an instance of B3T is satisfied iff

(⇒) Suppose that we have the unsigned permutation π and a sequence S_τ of k transpositions such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \cdot {S_ \tau } = \iota.$$ \end{document} Note that given the signed permutation π, we also have that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \cdot {S_ \tau } = \iota ,$$ \end{document} so the sequence S_τ with k transpositions has cost kw_τ, and

(⇐) Note that, on average, given a sequence of signed reversals and transpositions that sorts π, each breakpoint removed by signed reversals implies in a cost of at least added to [recall that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\Delta {b_ \mathcal{M}} ( \pi , \pi \cdot \rho ) \le 2$$ \end{document} ], and each breakpoint removed by transpositions implies in a cost of at least added to [recall that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\Delta {b_ \mathcal{M}} ( \pi , \pi \cdot \tau ) \le 3$$ \end{document} ]. It follows by Lemma 10 that costs at least

Suppose now that there is a sorting sequence that costs exactly \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$k \prime.$$ \end{document} This means that every signed reversal should remove two breakpoints and every transposition should remove three breakpoints.

If , the cost added to to remove each breakpoint using signed reversals and transpositions from must be strictly less than . Since breakpoints removed by signed reversals add a cost of at least to this means that there is no signed reversals on .

If , the cost added to to remove each breakpoint using signed reversals and transpositions from must be But note that signed permutation π has only positive strips, and although transpositions are applied to this permutation, all elements will continue with positive signs. By Lemma 14, the first signed reversal applied will not decrease the number of breakpoints, so cannot cost exactly \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$k \prime$$ \end{document} if it has one signed reversal that does not remove breakpoints.

In both cases, since has only transpositions, we also have that and has transpositions. ■

The following lemma shows that SRT is also NP-hard.

Lemma 16. SRT is NP-hard.

Proof. Directly from Theorem 15, since SRT can be seen as WSRT with and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${w_ \tau } = 1.$$ \end{document} ■

3.2. Decision problems for unsigned permutations

In this section, we show that the following problems on unsigned permutations are NP-hard:

Sorting by Reversals and Transpositions (URT): given an unsigned permutation π and a non-negative integer k, decide whether it is possible to sort π using up to k operations.

Sorting by Weighted Reversals and Transpositions (WURT): given an unsigned permutation π, weights w_ρ, and w_τ and a non-negative real number k, decide whether it is possible to sort π with cost less than or equal to k.

As for signed permutations, let us define a preliminary lemma that will be used later on the NP-hard proof. The following lemma establishes a family of unsigned permutations such that no signed reversal can remove breakpoints.

Lemma 17. If an unsigned permutation π has only increasing strips, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\Delta {b_{rt}} ( \pi , \pi \cdot \rho ) \le 0$$ \end{document} for any reversal ρ(i, j).

Proof. Note that when a reversal ρ(i, j) is applied to an unsigned permutation π, any increasing strip \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S = \langle { \pi _a} \; \ldots \;{ \pi _b} \rangle$$ \end{document} such that a ≥ i and b ≤ j turns into a decreasing strip.

Suppose that π has only increasing strips, and suppose that there exists a reversal ρ(i, j) that removes at least one breakpoint when applied to π. Suppose without loss of generality that the breakpoint between elements π_i−₁ and π_i is removed by ρ(i, j), that is, π_j = π_i−₁ + 1. Let S be the strip that ends with element π_i−₁ and let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \prime = \pi \cdot \rho ( i , j ).$$ \end{document} Since ρ(i, j) removes the breakpoint \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( { \pi _{i - 1}} , { \pi _i} ) ,$$ \end{document} strip \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S = \langle \ldots { \pi _{i - 1}} \rangle$$ \end{document} from π becomes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S \prime = \langle \ldots \;{ \pi _{i - 1}} \;{ \pi _j} \; \ldots \rangle$$ \end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \prime.$$ \end{document} But note that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S \prime$$ \end{document} remains an increasing strip (π_i₋₁ < π_j), which contradicts the fact that all strips between π_i−₁ and π_j₊₁ are increasing, and the lemma follows. ■

Theorem 18. WURT is NP-hard when w_τ/w_ρ ≤ 1.5.

Proof. Given an instance \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi = ( { \pi _1} \; \ldots \;{ \pi _n} )$$ \end{document} of B3T, we construct an instance \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( \pi \prime , {w_ \rho } , {w_ \tau } , k \prime )$$ \end{document} for WURT by mapping each π_i with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$i \in [ 1..n ]$$ \end{document} to two values \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi { \prime _{2i - 1}} = 2{ \pi _i} - 1$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi { \prime _{2i}} = 2{ \pi _i}$$ \end{document} on \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \prime ,$$ \end{document} and let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$k \prime = k{w_ \tau } ,$$ \end{document} with

Note that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \prime$$ \end{document} has twice the number of elements in π, and except for π₀ every element on even positions is the element on its left plus one. This means that (1) except for the first and last strips, any other strip in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \prime$$ \end{document} must have at least two elements, that is, there is no singleton on this permutation and (2) every strip of π is increasing.

Besides, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${b_{rt}} ( \pi \prime ) = {b_t} ( \pi )$$ \end{document} because (1) if the pair \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( { \pi _i} , { \pi _{i + 1}} )$$ \end{document} is a breakpoint on π, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( \pi { \prime _{2i}} , \; \pi { \prime _{2i + 1}} )$$ \end{document} must be a breakpoint on \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \prime ,$$ \end{document} with i ∈ [0..n], and (2) pairs \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( \pi { \prime _{2i - 1}} , \pi { \prime _{2i}} )$$ \end{document} are never breakpoints, for i ∈[1..n].

Now we show that an instance of B3T is satisfied iff \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d_{rt}^w ( \pi \prime ) = k \prime$$ \end{document} .

(⇒) Suppose that we have a sequence S_τ of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$k = {{{b_t} ( \pi ) } \mathord{ \left/ { \vphantom {{{b_t} ( \pi ) } 3}} \right. \kern- \nulldelimiterspace} 3}$$ \end{document} transpositions such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \cdot {S_ \tau } = \iota.$$ \end{document} Since each \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \pi _i} \in \pi$$ \end{document} was mapped as two consecutive values on \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \prime ,$$ \end{document} we can transform indices of each \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\tau ( i , j , k ) \in {S_ \tau }$$ \end{document} as \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\tau ( 2i - 1 , 2j - 1 , 2k - 1 ) \in S{ \prime _ \tau }$$ \end{document} such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \prime \cdot S{ \prime _ \tau } = \iota.$$ \end{document} It follows that the sequence \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S{ \prime _ \tau }$$ \end{document} with k transpositions has cost kw_τ, and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d_{rt}^w ( \pi \prime ) \le k{w_ \tau } = k \prime$$ \end{document} .

(⇐) As in the signed case, each breakpoint removed by reversals implies in a cost of at least w_ρ/2 added to S_ρτ, and each breakpoint removed by transpositions implies in a cost of at least w_τ/3 ≤ 1.5w_ρ/3 = w_ρ/2 added to S_ρτ. It follows by Lemma 10 that any sequence of reversals and transpositions S_ρτ such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \prime \cdot {S_{ \rho \tau }} = \iota$$ \end{document} costs at least \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${b_{rt}} ( \pi \prime ) {w_ \tau } / 3 = k{w_ \tau } = k \prime.$$ \end{document}

Suppose now that there is a sorting sequence S_ρτ that costs exactly \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$k \prime$$ \end{document} , which implies that every reversal from S_ρτ should remove two breakpoints and every transposition from S_ρτ should remove three breakpoints.

If w_τ < 1.5w_ρ, the cost added to S_ρτ to remove each breakpoint using reversals and transpositions from S_ρτ must be strictly less than w_ρ/2. Since breakpoints removed by reversals add a cost of at least w_ρ/2 to S_ρτ, this means that S_ρτ has no reversals.

If w_τ = 1.5w_ρ, the cost added to S_ρτ to remove each breakpoint using reversals and transpositions from S_ρτ is w_ρ/2. But note that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \prime$$ \end{document} has only increasing strips, and no strip can turn into singleton while transpositions are applied over breakpoints only, so all strips remain increasing. By Lemma 17, the first reversal applied cannot decrease the number of breakpoints, and S_ρτ must cost more than \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$k \prime$$ \end{document} if it has a reversal that does not remove any breakpoint.

In both cases, since S_ρτ has only transpositions, we can map each transposition \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\tau ( i , j , k ) \in {S_{ \rho \tau }}$$ \end{document} as \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\tau \left( { \frac { { i + 1 } } { 2 } , \frac { { j + 1 } } { 2 } , \frac { { k + 1 } } { 2 } } \right) \in { S \prime _ \tau } $$ \end{document} such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \cdot {S \prime _ \iota } = \iota ,$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${S \prime _ \tau }$$ \end{document} has \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{k \prime } \mathord{ \left/ { \vphantom {{k \prime } {{w_ \tau }}}} \right. \kern- \nulldelimiterspace} {{w_ \tau }}} = {{{b_{rt}} ( \pi \prime ) } \mathord{ \left/ { \vphantom {{{b_{rt}} ( \pi \prime ) } 3}} \right. \kern- \nulldelimiterspace} 3} = {{{b_t} ( \pi ) } \mathord{ \left/ { \vphantom {{{b_t} ( \pi ) } {3 = k}}} \right. \kern- \nulldelimiterspace} {3 = k}}$$ \end{document} transpositions. ■

The following lemma shows that URT is also NP-hard.

Lemma 19. URT is NP-hard.

Proof. Directly from Theorem 18, since URT can be seen as WURT with w_ρ = 1 and w_τ = 1. ■

4. Conclusion

This article shows that four sorting problems are NP-hard, namely sorting by reversals and transpositions; sorting by signed reversals and transpositions; sorting by weighted reversals and transpositions; and sorting by weighted signed reversals and transpositions. It is important to notice, however, that we proved that the weighted versions are NP-hard only when \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{{w_ \tau }} \mathord{ \left/ { \vphantom {{{w_ \tau }} {{w_ \rho } \le 1.5}}} \right. \kern- \nulldelimiterspace} {{w_ \rho } \le 1.5}} ,$$ \end{document} where w_ρ is the weight of a reversal and w_τ is the weight of a transposition. The complexity of sorting problems where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{{w_ \tau }} \mathord{ \left/ { \vphantom {{{w_ \tau }} {{w_ \rho } \le 1.5}}} \right. \kern- \nulldelimiterspace} {{w_ \rho } \le 1.5}}$$ \end{document} remain with open complexity.

Footnotes

Acknowledgments

This study was supported by the National Council for Scientific and Technological Development—CNPq (Grant Nos. 400487/2016-0, 425340/2016-3, and 140466/2018-5), the São Paulo Research Foundation—FAPESP (Grant Nos. 2013/08293-7, 2015/11937-9, 2017/12646-3, and 2017/16246-0), and the Brazilian Federal Agency for the support and evaluation of graduate education, CAPES, and the CAPES/COFECUB program (Grant No. 831/15).

Author Disclosure Statement

The authors declare there are no competing financial interests.

References

Bader

, and Ohlebusch

2007. Sorting by weighted reversals, transpositions, and inverted transpositions. J. Comput. Biol. 14, 615–636.

Blanchette

, Kunisawa

, and Sankoff

1996. Parametric genome rearrangement. Gene, 172, GC11–GC17.

Bulteau

, Fertin

, and Rusu

2012. Sorting by transpositions is difficult. SIAM J. Comput. 26, 1148–1180.

Caprara

1999. Sorting permutations by reversals and eulerian cycle decompositions. SIAM J. Discrete Math. 12, 91–110.

Eriksen

2002. (1+∈)-approximation of sorting by reversals and transpositions. Theor Comput Sci, 289, 517–529.

Hannenhalli

, and Pevzner

P.A.

1999. Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals. J. ACM, 46, 1–27.

Oliveira

A.R.

, Brito

K.L.

, Dias

, et al. 2019. Sorting by weighted reversals and transpositions. J. Comput. Biol. 26(PP), 1–12.

Rahman

, Shatabda

, and Hasan

2008. An approximation algorithm for sorting by reversals and transpositions. J. Discrete Algorithms, 6, 449–457.

Walter

M.E.M.T.

, Dias

, and Meidanis

1998. Reversal and transposition distance of linear chromosomes. In Proceedings of the 5th International Symposium on String Processing and Information Retrieval (SPIRE'1998). IEEE Computer Society, Los Alamitos, CA, pp. 96–102.

10.

Yancopoulos

, Attie

, and Friedberg

2005. Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics, 21, 3340–3346.