# Men Can’t Always be Transformed into Mice: Decision Algorithms and
Complexity for Sorting by Symmetric Reversals

Xin Tong111College of Computer Science and Technology, Shandong University,
Qingdao, China. Email<EMAIL_ADDRESS>Yixiao Yu222College of Computer
Science and Technology, Shandong University, Qingdao, China. Email:
<EMAIL_ADDRESS>Ziyi Fang333College of Computer Science and
Technology, Shandong University, Qingdao, China. Email:
<EMAIL_ADDRESS>Haitao Jiang444College of Computer Science and
Technology, Shandong University, Qingdao, China. Email<EMAIL_ADDRESS>Lusheng Wang555Department of Computer Science, City University of Hong Kong,
Kowloon, Hong Kong, China. Email<EMAIL_ADDRESS>Binhai Zhu666Gianforte
School of Computing, Montana State University, Bozeman, MT 59717, USA. Email:
<EMAIL_ADDRESS>Daming Zhu777College of Computer Science and Technology,
Shandong University, Qingdao, China. Email<EMAIL_ADDRESS>
###### Abstract

Sorting a permutation by reversals is a famous problem in genome
rearrangements, and has been well studied over the past thirty years. But the
involvement of repeated segments is inevitable during genome evolution,
especially in reversal events. Since 1997, quite some biological evidence were
found that in many genomes the reversed regions are usually flanked by a pair
of inverted repeats. For example, a reversal will transform $+a+x-y-z-a$ into
$+a+z+y-x-a$, where $+a$ and $-a$ form a pair of inverted repeats.

This type of reversals are called symmetric reversals, which, unfortunately,
were largely ignored until recently. In this paper, we investigate the problem
of sorting by symmetric reversals, which requires a series of symmetric
reversals to transform one chromosome $A$ into the another chromosome $B$. The
decision problem of sorting by symmetric reversals is referred to as SSR (when
the input chromosomes $A$ and $B$ are given, we use SSR(A,B), similarly for
the following optimization version) and the corresponding optimization version
(i.e., when the answer for SSR(A,B) is yes, using the minimum number of
symmetric reversals to convert $A$ to $B$), is referred to as SMSR(A,B). The
main results of this paper are summarized as follows, where the input is a
pair of chromosomes $A$ and $B$ with $n$ repeats.

  1. 1.

We present an $O(n^{2})$ time algorithm to solve the decision problem
SSR(A,B), i.e., determine whether a chromosome $A$ can be transformed into $B$
by a series of symmetric reversals. This result is achieved by converting the
problem to the circle graph, which has been augmented significantly from the
traditional circle graph and a list of combinatorial properties must be proved
to successfully answer the decision question.

  2. 2.

We design an $O(n^{2})$ time algorithm for a special 2-balanced case of
SMSR(A,B), where chromosomes $A$ and $B$ both have duplication number 2 and
every repeat appears twice in different orientations in $A$ and $B$.

  3. 3.

We show that SMSR is NP-hard even if the duplication number of the input
chromosomes are at most 2, hence showing that the above positive optimization
result is the best possible. As a by-product, we show that the _minimum
Steiner tree_ problem on _circle graphs_ is NP-hard, settling the complexity
status of a 38-year old open problem.

##  1 Introduction

In the 1980s, quite some evidence was found that some species have essentially
the same set of genes, but their gene order differs [HP94, PH86]. Since then,
sorting permutations with rearrangement operations has gained a lot of
interest in the area of computational biology in the last thirty years.
Sankoff et al. formally defined the genome rearrangement events with some
basic operations on genomes, e.g., reversals, transpositions and
translocations [SLA92], where the reversal operation is adopted the most
frequently [KS95, FLR09, WPR19].

The complexity of the problem of sorting permutations by reversals is closely
related to whether the genes are signed or not. Watterson et al. pioneered the
research on sorting an unsigned permutation by reversals [WEH82]. In 1997,
Caprara established the NP-hardness of this problem [Cap99]. Soon after,
Berman et al. showed it to be APX-hard [BK99]. Kececioglu and Sankoff
presented the first polynomial time approximation for this problem with a
factor of 2 [KS95]. The approximation ratio was improved to 1.5 by Christie
[Chr98]. So far as we know, the best approximation ratio for the problem of
sorting an unsigned permutation by reversals is 1.375 [BHK02]. As for the more
realistic problem of sorting signed permutations by reversals, Hannenhalli and
Pevzner proposed an $O(n^{4})$ time exact algorithm for this problem, where
$n$ is the number of genes in the given permutation (genomes) [HP99]. The time
complexity was later improved to $O(n^{2})$ by Kaplan et al. [KST00]. The
current best running time is $O(n^{1.5}\sqrt{\log n})$ by Tannier et al.
[TBS07].

On the other hand, some evidence has been found that the breakpoints where
reversals occur could have some special property in the genomes [LCG09,
San09]. As early as in 1997, some studies showed that the breakpoints are
often associated with repetitive elements on mammals and drosophila genomes
[TVO11, BBK04, APC03, SIW97]. In fact, the well-known “site-specific
recombination”, which has an important application in “gene knock out” [Sau87,
SH88, OCM92], also fulfills this rule. However, it was still not clear why and
how repetitive elements play important roles in genome rearrangement.
Recently, Wang et al. conducted a systematic study on comparing different
strains of various bacteria such as Pseudomonas aeruginosa, Escherichia coli,
Mycobacterium tuberculosis and Shewanella [WW18, WLG17]. Their study further
illustrated that repeats are associated with the ends of rearrangement
segments for various rearrangement events such as reversal, transposition,
inverted block interchange, etc, so that the left and right neighborhoods of
those repeats remain unchanged after the rearrangement events. Focusing on
reversal events, the reversed regions are usually flanked by a pair of
inverted repeats [SIW97]. The following real example is from Pseudomonas
aeruginosa strains in [WLG17]. Such a phenomenon can also better explain why
the famous “breakpoint reuse” (which were an interesting finding and discussed
in details when comparing human with mouse) happen [PT03].

Figure 1: Three symmetric reversals use the repeat ‘$+B$’ three times.

In this paper, we propose a new model called sorting by symmetric reversals,
which requires each inverted region on the chromosomes being flanked by a pair
of mutually inverted repeats. We investigate the decision problem of sorting
by symmetric reversals (SSR for short), which asks whether a chromosome can be
transformed into the other by a series of symmetric reversals. We devise an
$O(n^{2})$ time algorithm to solve this decision problem. We also study the
optimization version (referred to as SMSR) that uses a minimum number of
symmetric reversals to transform one chromosome into the other. We design an
$O(n^{2})$ time algorithm for a special 2-balanced case of SMSR, where
chromosomes have duplication number 2 and every repeat appears twice in
different orientations in each chromosome. We finally show that the
optimization problem SMSR is NP-hard even if each repeat has at most 2
duplications in each of the input chromosome.

In the NP-hardness proof, we set up the relationship between our problem and
the _minimum Steiner tree_ problem on _circle graphs_. The minimum Steiner
tree problem on circle graphs has been considered to be in $P$ as indicated by
Johnson in 1985 [Joh85]. Recently, Figueiredo et al. revisited Johnson’s table
and still marked the problem as in $P$ [FMS22], while leaving the reference as
“ongoing”. Here we clarify that the _minimum Steiner tree_ problem on _circle
graphs_ is in fact NP-hard, settling this 38-year old open problem.

This paper is organized as follows. In Section 2, we give some definitions. We
then present an algorithm to solve SSR under a special case, where the
duplication number of the input chromosomes is 2 in Section 3. In Section 4,
we present a polynomial algorithm for SMSR for the special 2-balanced case. In
Section 5, we present an algorithm to solve SSR for the general case. In
Section 6, we show that SMSR is NP-hard for the case that chromosomes have
duplication number 2, with the help of the new NP-hardness result on the
minimum Steiner tree problem on circle graphs. Finally, conclusions are given
in Section 7.

##  2 Preliminaries

In the literature of genome rearrangement, we always have a set of integers
$\Sigma_{1}=\\{1,\cdots,g\\}$, where each integer stands for a long DNA
sequence (syntenic block or a gene). For simplicity, we use “gene” hereafter.
Since we will study symmetric reversals, we define
$\Sigma_{2}=\\{r_{0},r_{1},r_{2},\cdots,r_{t}\\}$ to be a set of symbols, each
of them is referred to as a repeat and represents a relative shorter DNA
sequence compared with genes. We then set $\Sigma=\Sigma_{1}\cup\Sigma_{2}$ to
be the alphabet for the whole chromosome.

Since reversal operations work on a chromosome internally, a genome can be
considered as a chromosome for our purpose, i.e., each genome is a singleton
and contains only one chromosome. Here we assume that each gene appears
exactly once on a chromosome, on the other hand, by name, a repeat could
appear multiple times. A gene/repeat $x$ on a chromosome may appear in two
different orientations, i.e., either as $+x$ or $-x$. Thus, each chromosome of
interest is presented by a sequence of signed integers/symbols.

The number of occurrences of a gene/repeat $x$ in both orientations is called
the duplication number of $x$ on the chromosome $\pi$, denoted by $dp[x,\pi]$.
The duplication number of a chromosome $\pi$, denoted by $dp[\pi]$, is the
maximum duplication number of the repeats on it. For example, chromosome
$\pi=[+r_{0},+1,-r,+2,$ $+r,-r_{0}]$, $dp[1,\pi]=dp[2,\pi]=1$,
$dp[r_{0},\pi]=dp[r,\pi]=2$, and $dp[\pi]=2$. Two chromosomes $\pi_{1}$ and
$\pi_{2}$ are _related_ if their duplication numbers for all genes and repeats
are identical. Let $|x|\in\Sigma$ be an integer or symbol, and $+|x|$ and
$-|x|$ be two occurrences of $|x|$, where the orientations of $+|x|$ and
$-|x|$ are different. A chromosome of $n$ genes/repeats is denoted as
$\pi=[x_{1},x_{2},\dots,x_{n-1},x_{n}]$. A linear chromosome has two ends, and
it can be read from either end to the other, so the chromosome
$\pi=[x_{1},x_{2},\dots,x_{n-1},x_{n}]$ can also be described as
$[-x_{n},-x_{n-1},\dots,-x_{2},-x_{1}]$, which is called the reversed and
negated form of $\pi$.

A _reversal_ is an operation that reverses a segment of continuous integers
(or symbols) on the chromosome. A _symmetric reversal_ is a reversal, where
the reversed segment is flanked by pair of identical repeats with different
orientations, i.e, either $(+r,\cdots,-r)$ or $(-r,\cdots,+r)$ for some
$r\in\Sigma_{2}$. In other words, let $\pi=[x_{1},x_{2},\dots,x_{n}]$ be a
chromosome. The reversal $\rho(i,j)$ ($1\leq i<j\leq n$) reverses the segment
$[x_{i},x_{i+1},\dots,x_{j-1},x_{j}]$, and yields
$\pi^{\prime}=[x_{1},x_{2},\dots,x_{i-1},-x_{j},-x_{j-1}$,
$\dots,-x_{i+1},-x_{i},x_{j+1},$ $\dots,x_{n}]$. If $x_{i}=-x_{j}$, we say
that $\rho(i,j)$ is a symmetric reversal on $|x_{i}|$. Reversing a whole
chromosome will not change the relative order of the integers but their signs,
so we assume that each chromosome is flanked by $+r_{0}$ and $-r_{0}$, then a
chromosome will turn into its reversed and negated form by performing a
symmetric reversal between $+r_{0}$ and $-r_{0}$.

Again, as a simple example, let
$\pi=[+r_{0},+1,-r_{1},+2,+r_{2},+r_{1},+r_{2},-r_{0}]$, then a symmetric
reversal on $r_{1}$ yields
$\pi^{\prime}=[+r_{0},+1,-r_{1},-r_{2},-2,+r_{1},+r_{2},-r_{0}]$.

Now, we formally define the problems to be investigated in this paper.

###### Definition 2.1

Sorting by Symmetric Reversals, SSR for short.

Instance: Two related chromosomes $\pi$ and $\tau$, such that
$dp[\pi]=dp[\tau]\geq 2$.

Question: Is there a sequence of symmetric reversals that transform $\pi$ into
$\tau$?.

###### Definition 2.2

Sorting by the Minimum Symmetric Reversals, SMSR for short.

Instance: Two related chromosomes $\pi$ and $\tau$ with $dp[\pi]=dp[\tau]\geq
2$, and an integer $m$.

Question: Is there a sequence of symmetric reversals
$\rho_{1},\rho_{2},\dots,\rho_{m}$ that transform $\pi$ into $\tau$, such that
$m$ is minimized?

There is a standard way to make a signed gene/repeat unsigned. Let
$\pi=[x_{0},x_{1},\dots,x_{n+1}]$ be a chromosome, each occurrence of
gene/repeat of $\pi$, say $x_{i}$ ($0\leq i\leq n+1$), is represented by a
pair of ordered nodes, $l(x_{i})$ and $r(x_{i})$. If the sign of $x_{i}$ is +,
then $l(x_{i})=|x_{i}|^{h}$ and $r(x_{i})=|x_{i}|^{t}$; otherwise,
$l(x_{i})=|x_{i}|^{t}$ and $r(x_{i})=|x_{i}|^{h}$. Note that, if $x_{i}$ and
$x_{j}$ ($i\neq j$) are different occurrences of the same repeat, i.e.,
$|x_{i}|=|x_{j}|$, $l(x_{i})$, $l(x_{j})$, $r(x_{i})$ and $r(x_{j})$
correspond to two nodes $|x_{i}|^{h}$ and $|x_{i}|^{t}$ only. Consequently,
$\pi$ will also be described as
$[l(x_{0}),r(x_{0}),l(x_{1}),r(x_{1}),\dots,l(x_{n+1}),r(x_{n+1})]$. We say
that $r(x_{i})$ and $l(x_{i+1})$, for $0\leq i\leq n$, form an _adjacency_ ,
denoted by $\langle r(x_{i}),l(x_{i+1})\rangle$. (Note that in the signed
representation of a chromosome $\pi$, we simply say that $\langle
x_{i},x_{i+1}\rangle$ forms an adjacency; moreover, $\langle
x_{i},x_{i+1}\rangle=\langle-x_{i+1},-x_{i}\rangle$.) Also, we say that the
adjacency $\langle r(x_{i}),l(x_{i+1})\rangle$ is associated with $x_{i}$ and
$x_{i+1}$. Let $\mathcal{A}[\pi]$ represent the multi-set of adjacencies of
$\pi$. We take the chromosome $\pi=[+r_{0},+1,-r_{1},+2,+r_{1},-r_{0}]$ as an
example to explain the above notations. The multi-set of adjacencies is
$\mathcal{A}[\pi]=\\{\langle r_{0}^{t},1^{h}\rangle$, $\langle
1^{t},r_{1}^{t}\rangle$, $\langle r_{1}^{h},2^{h}\rangle$, $\langle
2^{t},r_{1}^{h}\rangle$, $\langle r_{1}^{t},r_{0}^{t}\rangle\\}$, $\pi$ can
also be viewed as
$[r_{0}^{h},r_{0}^{t},1^{h},1^{t},r_{1}^{t},r_{1}^{h},2^{h},2^{t},r_{1}^{h},r_{1}^{t},r_{0}^{t},r_{0}^{h}]$.

###### Lemma 2.1

Let $\pi$ be a chromosome and $\pi^{\prime}$ is obtained from $\pi$ by
performing a symmetric reversal. Then
$\mathcal{A}[\pi]=\mathcal{A}[\pi^{\prime}]$.

_Proof._ It is apparent that performing the symmetric reversal between
$+r_{0}$ and $-r_{0}$ will not change $\mathcal{A}[\pi]$. Assume that the
symmetric reversal $\rho(i,j)$ is performed on the chromosome
$\pi=[x_{0},x_{1},\dots,x_{n+1}]$, such that $x_{i}=-x_{j}$, where $1\leq
i<j\leq n$, and yields
$\pi^{\prime}=\pi\bullet\rho(i,j)=[x_{0},x_{1},\dots,x_{i-1},-x_{j},-x_{j-1},\dots$,
$-x_{i+1},-x_{i},x_{j+1},\dots,x_{n+1}]$. Then $\rho(i,j)$ breaks two
adjacencies $\langle r(x_{i-1}),l(x_{i})\rangle$ and $\langle
r(x_{j}),l(x_{j+1})\rangle$, and creates two new adjacencies $\langle
r(x_{i-1}),l(-x_{j})\rangle$ and $\langle r(-x_{i}),l(x_{j+1})\rangle$. Since
$x_{i}=-x_{j}$, $l(x_{i})=l(-x_{j})$ and $r(x_{j})=r(-x_{i})$, thus $\langle
r(x_{i-1}),l(x_{i})\rangle=\langle r(x_{i-1}),l(-x_{j})\rangle$ and $\langle
r(x_{j}),l(x_{j+1})\rangle=\langle r(-x_{i}),l(x_{j+1})\rangle$. Consequently,
$\mathcal{A}[\pi]=\mathcal{A}[\pi^{\prime}]$. $\sqcap$$\sqcup$

Actually, Lemma 2.1 implies a necessary condition for answering the decision
question of SSR.

###### Theorem 2.1

Chromosome $\pi$ cannot be transformed into $\tau$ by a series of symmetric
reversals if $\mathcal{A}[\pi]\neq\mathcal{A}[\tau]$.

A simple negative example would be $\pi=[+r_{0}$, $+r_{1}$, $-2$, $+r_{1}$,
$-1$, $-r_{0}]$ and $\tau=[+r_{0}$,$-r_{1}$,$+2$,$-r_{1},$ $+1$,$-r_{0}]$. One
can easily check that $\mathcal{A}[\pi]\neq\mathcal{A}[\tau]$, which means
that there is no way to convert $\pi$ to $\tau$ using symmetric reversals. In
the next section, as a warm-up, we first solve the case when each repeat
appears at most twice in $\pi$ and $\tau$. Even though the method is not
extremely hard, we hope the presentation and some of the concepts can help
readers understand the details for the general case in Section 5 better.

##  3 An $O(n^{2})$ Algorithm for SSR with Duplication Number 2

In this section, we consider a special case, where the duplication numbers for
the two related chromosomes $\pi$ and $\tau$ are both $2$. That is,
$\mathcal{A}[\pi]=\mathcal{A}[\tau]$ and $dp[\pi]=dp[\tau]=2$. We will design
an algorithm with running time $O(n^{2})$ to determine if there is a sequence
of symmetric reversals that transform $\pi$ into $\tau$.

Note that $\mathcal{A}[\pi]$ is a multi-set, where an adjacency may appear
more than once. When the duplication number of each repeat in the chromosome
is at most 2, the same adjacency can appear at most twice in
$\mathcal{A}[\pi]$.

Let $\pi=[x_{0},x_{1},\dots,x_{n+1}]$ be a chromosome. Let $x_{i}$ and $x_{j}$
be the two occurrences of a repeat $x$, and $x_{i+1}$ and $x_{j+1}$ the two
occurrences of the other repeat $x^{\prime}$ in $\pi$. We say that $|x_{i}|$
and $|x_{i+1}|$ are redundant, if $r(x_{i})=r(x_{j})$ and
$l(x_{i+1})=l(x_{j+1})$ (or $r(x_{i})=l(x_{j})$ and $l(x_{i+1})=r(x_{j-1})$).
In this case, the adjacency $\langle r(x_{i}),l(x_{i+1}\rangle$ appears twice.
In fact, it is the only case that an adjacency can appear twice. An example is
as follows: $\pi=[+r_{0},+r_{1},-r_{2},+1,+r_{2},-r_{1},-r_{0}]$, where the
adjacency $\langle+r_{1},-r_{2}\rangle$ appears twice (the second negatively),
hence $r_{1}$ and $r_{2}$ are redundant. The following lemma tells us that if
$x_{i}$ and $x_{j}$ are redundant, we only need to use one of them to do
reversals and the other can be deleted from the chromosome so that each
adjacency appears only once.

###### Lemma 3.1

Given two chromosomes $\pi=[x_{0},x_{1},\dots,x_{n+1}]$ and $\tau$, such that
$\mathcal{A}[\pi]=\mathcal{A}[\tau]$. Let $|x_{i}|$ and $|x_{i+1}|$ be two
repeats in $\pi$ that are redundant. Let $\pi^{\prime}$ and $\tau^{\prime}$ be
the chromosomes after deleting the two occurrences of $|x_{i+1}|$ from both
$\pi$ and $\tau$, respectively. Then $\pi$ can be transformed into $\tau$ by a
series of symmetric reversals if and only if $\pi^{\prime}$ can be transformed
into $\tau^{\prime}$ by a series of symmetric reversals.

_Proof._ Without loss of generality, we assume that
$r(x_{i})=r(x_{j})=|x_{i}|^{a}$ and $l(x_{i+1})=l(x_{j+1})=|x_{i+1}|^{b}$,
where $a,b\in\\{h,t\\}$. The proof of the other case is similar.

$(\Rightarrow)$ Assume that there is a series of symmetric reversals,
$\rho_{1},\rho_{2},\dots,\rho_{m}$, that transforms $\pi$ into $\tau$, to be
specific, $\pi_{0}=\pi$, $\pi_{k}=\pi_{k-1}\bullet\rho_{k}$ for each $1\leq
k\leq m$, and $\pi_{m}=\tau$. Suppose that there exists a symmetric reversal
$\rho_{k}$($1\leq k\leq m$), which is on $|x_{i+1}|$. Lemma 2.1 guarantees
that $\langle|x_{i}|^{a},|x_{i+1}|^{b}\rangle$ still appears twice in
$\mathcal{A}[\pi_{k-1}]$. Because the two occurrences of $|x_{i+1}|$ have
distinct sign in $\pi_{k-1}$, the two $|x_{i}|^{a}$s are located at different
sides of the two $|x_{i+1}|^{b}$s respectively, which implies that some
$|x_{i}|^{a}$ is the left node of some occurrence of $|x_{i}|$ and the other
$|x_{i}|^{a}$ is the right node of the other occurrence of $|x_{i}|$.
Therefore the signs of the two occurrences of $|x_{i}|$ are also distinct in
$\pi_{k-1}$. It is apparent that performing the symmetric reversal on
$|x_{i}|$ would also transform $\pi_{k-1}$ into $\pi_{k}$.

$(\Leftarrow)$ Assume that there is a series of symmetric reversals,
$\rho^{\prime}_{1},\rho^{\prime}_{2},\dots,\rho^{\prime}_{m^{\prime}}$ which
transforms $\pi^{\prime}$ into $\tau^{\prime}$. Let the corresponding
chromosomes be $\pi^{\prime}_{0}=\pi^{\prime}$, $\pi^{\prime}_{1}$, $\dots$,
$\pi^{\prime}_{m^{\prime}}=\tau^{\prime}$, where
$\pi_{k^{\prime}}=\pi_{k^{\prime}-1}\bullet\rho^{\prime}_{k^{\prime}}$ for
each $1\leq k^{\prime}\leq m^{\prime}$. We can obtain
$\overline{\pi^{\prime}}_{k^{\prime}}$ by substituting $x_{i}$ with
$[x_{i},x_{i+1}]$ and $-x_{i}$ with $[-x_{i+1},-x_{i}]$ in
$\pi^{\prime}_{k^{\prime}}$. Clearly, $\overline{\pi^{\prime}}_{0}=\pi$ and
$\overline{\pi^{\prime}}_{m^{\prime}}=\tau$. For each $1\leq k^{\prime}\leq
m^{\prime}$, $\rho^{\prime}_{k^{\prime}}$ is applicable to
$\overline{\pi^{\prime}}_{k^{\prime}-1}$, since all the elements on
$\overline{\pi^{\prime}}_{k^{\prime}-1}$ have the same signs with those on
$\pi^{\prime}_{k^{\prime}-1}$; also,
$\overline{\pi^{\prime}}_{k^{\prime}}=\overline{\pi^{\prime}}_{k^{\prime}-1}\bullet\rho^{\prime}_{k^{\prime}}$,
since the two adjacencies of the form
$\langle|x_{i}|^{a},|x_{i+1}|^{b}\rangle$ can not be changed by
$\rho^{\prime}_{k^{\prime}}$. $\sqcap$$\sqcup$

Regarding the previous example,
$\pi=[+r_{0},+r_{1},-r_{2},+1,+r_{2},-r_{1},-r_{0}]$, where $r_{1}$ and
$r_{2}$ are redundant, following the above lemma, one can obtain
$\pi^{\prime}=[+r_{0},+r_{1},+1,-r_{1},-r_{0}]$. This is in fact equivalent to
replacing the adjacency $\langle+r_{1},-r_{2}\rangle$ by $r_{1}$, and
$\langle+r_{2},-r_{1}\rangle$ by $-r_{1}$.

A chromosome $\pi$ is _simple_ if every adjacency in $\mathcal{A}[\pi]$
appears only once. Based on Lemma 3.1, we can remove the two occurrences of a
redundant repeat from the chromosomes. Thus, if $dp[\pi]=dp[\tau]=2$, we can
always assume that both $\pi$ and $\tau$ are simple. Consequently, there is a
unique bijection between two corresponding adjacency sets $\mathcal{A}[\pi]$
and $\mathcal{A}[\tau]$. We say that any pair of identical adjacencies are
matched to each other.

For each repeat $x$ with $dp[\pi,x]=dp[\tau,x]=2$, let $x_{i}$, $x_{j}$ be the
two occurrences of $x$ in $\pi$, and $y_{i^{\prime}}$, $y_{j^{\prime}}$ be the
two occurrences of $x$ in $\tau$, there are four adjacencies associated with
$x_{i}$ and $x_{j}$ in $\pi$: $\langle r(x_{i-1}),l(x_{i})\rangle$, $\langle
r(x_{i}),l(x_{i+1})\rangle$, $\langle r(x_{j-1}),l(x_{j})\rangle$, $\langle
r(x_{j}),l(x_{j+1})\rangle$. Similarly, there are four adjacencies associated
with $y_{i^{\prime}}$ and $y_{j^{\prime}}$ in $\tau$. We say that $x$ is an
_neighbor-consistent_ repeat, if $\langle r(x_{i-1}),l(x_{i})\rangle$ and
$\langle r(x_{i}),l(x_{i+1})\rangle$ are matched to two adjacencies both
associated with $y_{i^{\prime}}$ or both associated with $y_{j^{\prime}}$.
That is, the left and right neighbors of $x_{i}$ are identical in both
chromosomes. Note that $\mathcal{A}[\pi]=\mathcal{A}[\tau]$ also implies that
the left and right neighbors of the other occurrences $x_{j}$ are also
identical in both two chromosomes if $x$ is neighbor-consistent. If $\langle
r(x_{i-1}),l(x_{i})\rangle$ and $\langle r(x_{i}),l(x_{i+1})\rangle$ are
matched to two adjacencies, one of which is associated with $y_{i^{\prime}}$
and the other is associated with $y_{j^{\prime}}$, then $x$ is an _neighbor-
inconsistent_ repeat. The genes and the repeats which appear once in $\pi$ are
also defined to be neighbor-consistent. (See Figure 2 for an example.) By
definition and the fact that $\mathcal{A}[\pi]=\mathcal{A}[\tau]$, we have

###### Proposition 3.1

Performing a symmetric reversal on a repeat will turn the repeat from
neighbor-consistent to neighbor-inconsistent or vice versa. (See Figure 2.)

Figure 2: $x_{i}$, $x_{j}$ are the two occurrences of $x$ in $\pi$ with
$x_{i}=-x_{j}$, and $y_{i^{\prime}}$, $y_{j^{\prime}}$ be the two occurrences
of $x$ in $\tau$. Case ($a$): $x$ is neighbor-consistent, and will turn to
neighbor-inconsistent by a reversal on itself. Case ($b$): $x$ is neighbor-
inconsistent, and will turn to neighbor-consistent by a reversal on itself.

###### Theorem 3.1

Given two simple related chromosomes $\pi^{*}$ and $\tau$ with
$dp[\pi^{*}]=dp[\tau]=2$, $\pi^{*}=\tau$ if and only if
$\mathcal{A}[\pi^{*}]=\mathcal{A}[\tau]$ and every repeat is neighbor-
consistent.

_Proof._ Assume that $\pi^{*}=[x_{0},x_{1},\dots,x_{n},x_{n+1}]$ and
$\tau=[y_{0},y_{1},\dots,y_{n},y_{n+1}]$, where $x_{0}=y_{0}=+r_{0}$ and
$x_{n+1}=y_{n+1}=-r_{0}$.

The sufficiency part is surely true, since we have $x_{i}=y_{i}$ for $0\leq
i\leq n+1$.

Now we prove the necessity inductively. Our inductive hypothesis is that
$x_{i}=y_{i}$ for $0\leq i\leq n+1$. Initially, we have $x_{0}=y_{0}=+r_{0}$
and $x_{1}=y_{1}$ since $\langle r_{0}^{t},l(x_{1})\rangle=\langle
r_{0}^{t},l(y_{1})\rangle$. For the inductive step, consider $x_{i+1}$.
Because $\mathcal{A}[\pi^{*}]=\mathcal{A}[\tau]$, the adjacency $\langle
r(x_{i}),l(x_{i+1})\rangle$ appears in both $\mathcal{A}[\pi^{*}]$, and
$\mathcal{A}[\tau]$. Since $|x_{i}|$ is even, the two adjacencies $\langle
r(x_{i-1}),l(x_{i})\rangle$ and $\langle r(x_{i}),l(x_{i+1})\rangle$ must be
matched to two adjacencies which are associated with a single occurrence of
$|x_{i}|$ in $\tau$. From the inductive hypothesis, $x_{i-1}=y_{i-1}$ and
$x_{i}=y_{i}$, $\langle r(x_{i-1}),l(x_{i})\rangle$ has been matched to
$\langle r(y_{i-1}),l(y_{i})\rangle$, Thus, $\langle
r(x_{i}),l(x_{i+1})\rangle$ must be matched to $\langle
r(y_{i}),l(y_{i+1})\rangle$, together with $x_{i}=y_{i}$, we have,
$l(x_{i+1})=l(y_{i+1})$ and $x_{i+1}=y_{i+1}$. $\sqcap$$\sqcup$

Based on proposition 3.1 and Theorem 3.1, to transform $\pi$ into $\tau$, it
is sufficient to perform an odd number (at least 1) of symmetric reversals on
each neighbor-inconsistent repeat, and an even number (might be 0) of
symmetric reversals on each neighbor-consistent repeat. Hereafter, we also
refer an neighbor-consistent (resp. neighbor-inconsistent) repeat as an even
(resp. odd) repeat.

The main difficulty to find a sequence of symmetric reversals between $\pi$
and $\tau$ is to choose a ”correct” symmetric reversal at a time. Note that,
for a pair of occurrences $(x_{i},,x_{j})$ of a repeat $x$, the orientations
may be the same at present and after some reversals, the orientations of
$x_{i}$ and $x_{j}$ may differ. We can only perform a reversal on a pair of
occurrences of a repeat with different orientations. Thus, it is crucial to
choose a ”correct” symmetric reversal at the right time. In the following, We
will use ”intersection” graph to handle this.

Suppose that we are given two simple related chromosomes $\pi$ and $\tau$ with
$dp[\pi]=dp[\tau]=2$ and $\mathcal{A}[\pi]=\mathcal{A}[\tau]$. In this case,
each repeat in the chromosomes represent an interval indicated by the two
occurrences of the repeat. Thus, we can construct an _intersection graph_
$IG(\pi,\tau)=(V[\pi],E[\pi])$. For each repeat $x$ with $dp[\pi,x]=2$,
construct a vertex $x\in V_{\pi}$, and set its weight, $\omega(x)=2$ if $x$ is
even, and $\omega(x)=1$ if $x$ is odd; set the color of $x$ black if the signs
of the two occurrences of $x$ in $\pi$ are different, and white otherwise.
Construct an edge between two vertices $x$ and $y$ if and only if the
occurrences of $x$ and $y$ appear alternatively in $\pi$, i.e., let $x_{i}$
and $x_{j}$ ($i<j$) be the two occurrences of $x$, and $x_{k}$ and $x_{l}$
($k<l$) be the two occurrences of $y$ in $\pi$, there will be an edge between
the vertices $x$ and $y$ if and only if $i<k<j<l$ or $k<i<l<j$. There are
three types of vertices in $V[{\pi}]$: black vertices (denoted as
$V_{b}[\pi]$), white vertices of weight 1 (denoted as $V_{w}^{1}[\pi]$) and
white vertices of weight 2 (denoted as $V_{w}^{2}[\pi]$). Thus,
$V[{\pi}]=V_{b}[\pi]\cup V_{w}^{1}[\pi]\cup V_{w}^{2}[\pi]$. In fact, the
intersection graph is a circle graph while ignoring the weight and color of
all the vertices.

###### Lemma 3.2

A single white vertex of weight 1 cannot be a connected component in
$IG(\pi,\tau)$ .

_Proof._ We prove it by contradiction. Assume that $x$ is a white vertex of
weight 1, which forms a connected component of $IG(\pi,\tau)$. Let the two
occurrences of $x$ be $x_{i}$ and $x_{j}$ ($i<j$) in $\pi$, and $y_{k}$ and
$y_{l}$ in $\tau$. Since $x$ is odd, w.l.o.g, assume that $\langle
r(x_{i}),l(x_{i+1})\rangle$ and $\langle r(x_{j-1}),l(x_{j})\rangle$ are
matched to two adjacencies both associated with $y_{k}$. Because $x$ is an
isolated vertex in $IG(\pi,\tau)$, all the other occurrences of
$|x_{i+1}|,\dots,|x_{j-1}|$ must also locate in between $x_{i}$ and $x_{j}$ in
$\pi$.

Note that each adjacency is unique in $\mathcal{A}[\pi]$, as well as in
$\mathcal{A}[\tau]$. In case that $y_{k+1}$ is an occurrence of $|x_{i+1}|$,
the adjacency $\langle r(y_{k+1}),l(y_{k+2})\rangle$ must be matched to an
adjacency located in between $x_{i}$ and $x_{j}$ in $\pi$, thus, an occurrence
of $|y_{k+2}|$ also locates in between $x_{i}$ and $x_{j}$ in $\pi$, so does
the other occurrence of $|y_{k+2}|$ (if exist), hence, all the adjacencies
associate with the occurrences of $|y_{k+2}|$ locate in between $x_{i}$ and
$x_{j}$ in $\pi$, which implies that $y_{k+3}$ exists. The recursion can not
terminate until there is some $y_{k+t}$ which is an occurrence of $|x_{j}|$,
also the adjacency $\langle r(y_{k+t}),l(y_{k+t+1})\rangle=\langle
r(x_{j-1}),l(x_{j})\rangle$. It is a contradiction since $\langle
r(y_{k-1}),l(y_{k})\rangle=\langle r(x_{i-1}),l(x_{i})\rangle$.

The argument when $y_{k+1}$ is an occurrence of $|x_{j-1}|$ is similar.
$\sqcap$$\sqcup$

For each vertex $x$ in $IG(\pi,\tau)$, let $N(x)$ denote the set of vertices
incident to $x$. For a black vertex, say $x$, in $IG(\pi,\tau)$, performing a
symmetric reversal of $x$ in $\pi$, yields $\pi^{\prime}$, where the
intersection graph $IG(\pi^{\prime})=(V[\pi^{\prime}],E[\pi^{\prime}])$ can be
derived from $IG(\pi,\tau)$ following the three rules:

  * •

rule-I: for each vertex $v\in N(x)$ in $IG(\pi,\tau)$, change its color from
black to white, and vice versa.

  * •

rule-II: for each pair of vertices $u,v\in N(x)$ of $IG(\pi,\tau)$, if
$(u,v)\in E[\pi]$, then $E[\pi^{\prime}]=E[\pi]-\\{(u,v)\\}$; and if
$(u,v)\notin E[\pi]$, then $E[\pi^{\prime}]=E[\pi]\cup\\{(u,v)\\}$.

  * •

rule-III: subtract the weight of $x$ by one, if $\omega(x)>0$, then
$V[\pi^{\prime}]=V[\pi]$; and if $\omega(x)=0$, then
$V[\pi^{\prime}]=V[\pi]-\\{x\\}$.

Figure 3:
$\pi=[+r_{0},+r_{1},+1,+r_{2},+r_{3},+r_{1},-r_{2},-2,+r_{3},-r_{0}]$, and
$\tau=[+r_{0},+r_{1},-r_{2},-2,+r_{3},+r_{1},+1,+r_{2},+r_{3},-r_{0}]$.
$\mathcal{A}[\pi]=\mathcal{A}[\tau]=$$\\{\langle r_{0}^{t},r_{1}^{h}\rangle$,
$\langle r_{1}^{t},1^{h}\rangle$, $\langle 1^{t},r_{2}^{h}\rangle$, $\langle
r_{2}^{t},r_{3}^{h}\rangle$, $\langle r_{3}^{t},r_{1}^{h}\rangle$, $\langle
r_{1}^{t},r_{2}^{t}\rangle$, $\langle r_{2}^{h},2^{t}\rangle$, $\langle
2^{h},r_{3}^{h}\rangle$, $\langle r_{3}^{t},r_{0}^{t}\rangle\\}$. The repeats
$r_{1}$ and $r_{3}$ are odd, while the repeat $r_{2}$ is even. ($a$) The
intersection graph $IG(\pi,\tau)$, performing the symmetric reversal on repeat
$r_{2}$ will transform $\pi$ into $\pi^{\prime}=$$[+r_{0}$, $+r_{1}$, $+1$,
$+r_{2}$, $-r_{1}$, $-r_{3}$, $-r_{2}$, $-2$, $+r_{3}$, $-r_{0}]$, ($b$) The
intersection graph $IG(\pi^{\prime},\tau)$. ($c$) The intersection graph after
performing the symmetric reversal on the repeat $r_{1}$. ($d$) The
intersection graph after performing the symmetric reversal on the repeat
$r_{3}$.

If $x$ is a black vertex in $IG(\pi,\tau)$ and $\omega(x)=1$, then performing
the symmetric reversal of $x$ in $\pi$ yields $\pi^{\prime}$. Let
$C_{1},C_{2},\dots,C_{m}$ be the connected components introduced by the
deletion of $x$ in $IG(\pi^{\prime},\tau)$, we go through some properties of
performing this symmetric reversal.

###### Lemma 3.3

In each $C_{i}$ ($1\leq i\leq m$), there is at least one vertex $z_{i}$ such
that $z_{i}\in N(x)$ in $IG(\pi,\tau)$.

_Proof._ Consider the scenario of $IG(\pi^{\prime},\tau)$ just prior to
deleting $x$, all the connected components $C_{1},C_{2},\dots,C_{m}$ are in a
single connected component, which also contains $x$. But immediately after
deleting $x$, they become $m$ separate connected components. $\sqcap$$\sqcup$

###### Lemma 3.4

Let $x^{\prime}$ be a black vertex, $\omega(x)=\omega(x^{\prime})=1$, and
$x^{\prime}\in N(x)$ in $IG(\pi,\tau)$. After performing the symmetric
reversal of $x$ in $\pi$, let $y$ be a vertex in the connected component
$C_{i}$, and $x^{\prime}$ is in the connected component $C_{j}$, $i\neq j$.
Let $\pi^{\prime\prime}$ be the resulting chromosome after performing the
symmetric reversal of $x^{\prime}$ in $\pi$, then the color of $y$ is the same
in $IG(\pi^{\prime},\tau)$ and $IG(\pi^{\prime\prime},\tau)$.

_Proof._ We conduct the proof by considering the following two cases: (1)
$y\in N(x)$, (2) $y\notin N(x)$ in $IG(\pi,\tau)$. In case (1),
$(y,x^{\prime})\in E[\pi]$, then the color of $y$ would be changed by
performing the symmetric reversal on either $x$ or $x^{\prime}$ in $\pi$. In
case (2), $(y,x^{\prime})\notin E[\pi]$, then the color of $y$ would not be
changed by performing the symmetric reversal on either $x$ or $x^{\prime}$ in
$\pi$. $\sqcap$$\sqcup$

###### Lemma 3.5

Let $x^{\prime}$ be a black vertex, $\omega(x)=\omega(x^{\prime})=1$, and
$x^{\prime}\in N(x)$ in $IG(\pi,\tau)$. After performing the symmetric
reversal of $x$ in $\pi$, let $y,z$ be two vertices in the connected component
$C_{i}$, and $x^{\prime}$ is in the connected component $C_{j}$, $i\neq j$.
Let $\pi^{\prime\prime}$ be the resulting chromosome after performing the
symmetric reversal of $x^{\prime}$ in $\pi$. If $(y,z)\in E[\pi^{\prime}]$,
then $(y,z)\in E[\pi^{\prime\prime}]$.

_Proof._ We conduct the proof by considering the following three cases: (1)
both $y,z\in N(x)$, (2) only one, say $y$, is in $N(x)$, and (3) neither of
them belongs to $N(x)$ in $IG(\pi,\tau)$. We illustrate the three cases in
Figure 4.

(1) both $y,z\in N(x)$. Then $(y,z)\notin E[\pi]$, since $y$ and $x^{\prime}$
are in distinct connected component, $(y,x^{\prime})\in E[\pi]$ and
$(z,x^{\prime})\in E[\pi]$, thus, $(y,z)\in E[\pi^{\prime\prime}]$.

(2) $y\in N(x)$, $z\notin N(x)$. Then $(y,z)\in E[\pi]$, since $y$ and
$x^{\prime}$ are in distinct connected component, $(y,x^{\prime})\in E[\pi]$
and $(z,x^{\prime})\notin E[\pi]$, thus, $(y,z)\in E[\pi^{\prime\prime}]$.

(3) $y\notin N(x)$, $z\notin N(x)$. Then $(y,z)\in E_{\pi}$, since $y$ and
$x^{\prime}$ are in distinct connected component, $(y,x^{\prime})\notin
E[\pi]$ and $(z,x^{\prime})\notin E[\pi]$, thus, $(y,z)\in
E[\pi^{\prime\prime}]$. $\sqcap$$\sqcup$

Figure 4: Three cases in the proof of Lemma 3.5.

###### Theorem 3.2

If a connected component of $IG(\pi,\tau)$ contains at least one black vertex,
then there exists a symmetric reversal, after performing it, any newly created
connected component containing a white vertex of weight 1 also contains a
black vertex.

_Proof._ It is apparent that performing a symmetric reversal of a black vertex
$x$ of weight 2 will not introduce any new connected component, and the vertex
$x$ is still black. Assume that there is no black vertex of weight 2 in the
connected component. For each black vertex $x$, let $\Delta(x)$ be the number
of white vertices in the connected components, which contains white vertices
of weight 1 but not any black vertex, introduced by performing the symmetric
reversal of $x$. Next, we show that, there must be some vertex $x$, such that
$\Delta(x)=0$.

On the contrary, let $x$ be the black vertex with minimum $\Delta(x)>0$. Let
$C_{1},C_{2},\dots,C_{m}$ be the introduced connected components after
performing the symmetric reversal of $x$. There could not be a connected
component which is composed of white vertices of weight 2, since otherwise,
following Lemma 3.3, the neighbor of $x$ in this connected component is black
prior to performing the symmetric reversal of $x$, which is in contradiction
with our assumption. W.l.o.g, assume that each of $C_{1},C_{2},\dots,C_{i}$
($1\leq i\leq m$) contains a white vertex of weight 1 but no black vertex, and
each of $C_{i+1},C_{i+2},\dots,C_{m}$ contains at least one black vertex.

Let $x^{\prime}$ be the neighbor of $x$ in $C_{1}$. Then, $x^{\prime}$ is a
black vertex of weight 1 prior to performing the symmetric reversal of $x$. It
is sufficient to show that $\Delta(x^{\prime})<\Delta(x)$, and hence
contradicting with that $\Delta(x)$ is minimum. $\Delta(x)$ only counts the
vertices in $C_{1},C_{2},\dots,C_{i}$. From Lemma 3.4 and Lemma 3.5, the color
of all the vertices in $C_{i+1},C_{i+2},\dots,C_{m}$ are preserved, and all
the edges in $C_{i+1},C_{i+2},\dots,C_{m}$ are preserved after performing the
symmetric reversal of $x^{\prime}$. Therefore, $\Delta(x^{\prime})$ will also
not count any vertex in $C_{i+1},C_{i+2},\dots,C_{m}$, which implies,
$\Delta(x^{\prime})\leq\Delta(x)$.

From Lemma 3.2, $x^{\prime}$ must have a neighbor in $C_{1}$. Let
$x^{\prime\prime}$ be a neighbor of $x^{\prime}$ in $C_{1}$. In
$IG(\pi,\tau)$, if $(x,x^{\prime\prime})\in E_{\pi}$, then
$(x^{\prime},x^{\prime\prime})\notin E_{\pi}$, and $x^{\prime\prime}$ is a
black vertex prior to and after performing the symmetric reversal of
$x^{\prime}$. If $(x,x^{\prime\prime})\notin E_{\pi}$, then
$(x^{\prime},x^{\prime\prime})\in E_{\pi}$, and $x^{\prime\prime}$ is a white
vertex prior to and after performing the symmetric reversal of $x$, but become
a black vertex after performing the symmetric reversal of $x^{\prime}$. In
either case, $\Delta(x^{\prime})$ will not count $x^{\prime\prime}$, thus,
$\Delta(x^{\prime})<\Delta(x)$. We illustrate the proof in Figure 5.
$\sqcap$$\sqcup$

Figure 5: Whether $(x,x^{\prime\prime})\in E_{\pi}$ or not, $x^{\prime\prime}$
will always be black after performing the symmetric reversal of $x^{\prime}$,
thus $\Delta(x^{\prime})<\Delta(x)$.

The main contribution of this section is the following theorem.

###### Theorem 3.3

A chromosome $\pi$ can be transformed into the other chromosome $\tau$ if and
only if (I) $\mathcal{A}[\pi]=\mathcal{A}[\tau]$, and (II) each white vertex
of weight 1 belongs to a connected component of $IG(\pi,\tau)$ containing a
black vertex.

_Proof._ $(\Rightarrow)$ If there exists an connected component of
$IG(\pi,\tau)$, say $C$, which is composed of white vertices including a white
vertex $x$ of wight 1, and all the vertex in $C$ do not admit any symmetric
reversal. Moreover, $x$ is odd in $\pi$. Thus, it is impossible to find a
series of symmetric reversals to make $x$ black, and then make $x$ even.
According to Theorem 3.1, $\pi$ can not be transformed into $\tau$.

$(\Leftarrow)$ As each odd repeat in $\pi$ corresponds to a vertex of weight
1, and each even repeat in $\pi$ corresponds to a vertex of weight 2. Theorem
3.2 guarantees that, each vertex of weight 1 will be reversed once, and each
vertex of weight 2 will either not be reversed or be reversed twice. Finally,
all the repeats will become even, from Theorem 3.1, $\pi$ has been transformed
into $\tau$. $\sqcap$$\sqcup$

The above theorem implies that a breadth-first search of $IG[\pi,\tau]$ will
determine whether $\pi$ can be transformed into $\tau$, which takes $O(n^{2})$
time, because $IG(\pi,\tau)$ contains at most $n$ vertices and $n^{2}$ edges.
We will show the details of the algorithm in Section 5, since it also serves
as a decision algorithm for the general case.

In the next section, we show that the optimization version is also
surprisingly polynomially solvable when the input genomes have some
constraints.

##  4 An Algorithm for the 2-Balanced Case of SMSR

In this section, we consider a special case of SMSR, which we call 2-Balanced,
where the duplication numbers of the two simple related chromosomes $\pi$ and
$\tau$ are both 2, and $\tau$ contains both $+r$ and $-r$ for each repeat
$r\in\Sigma_{2}$. The algorithm presented here will give a shortest sequence
of symmetric reversals that transform $\pi$ into $\tau$.

As $\mathcal{A}[\pi]=\mathcal{A}[\tau]$ for two related chromosomes $\pi$ and
$\tau$, there is a bijection between identical adjacencies of
$\mathcal{A}[\pi]$ and $\mathcal{}{A}[\tau]$. For each pair of identical
adjacencies $\langle r(x_{i}),l(x_{i+1})\rangle\in\textit{A}[\pi]$ and
$\langle r(y_{j}),l(y_{j+1})\rangle\in\textit{A}[\tau]$, define the sign of
$\langle r(x_{i}),l(x_{i+1})\rangle$ to be _positive_ if
$r(x_{i})=r(y_{j})\neq l(x_{i+1})=l(y_{j+1})$, and _negative_ if
$r(x_{i})=l(y_{j+1})\neq l(x_{i+1})=r(y_{j})$. We can always assume that
$\langle r(x_{0}),l(x_{1})\rangle$ and $\langle r(x_{n}),l(x_{n+1})\rangle$
are positive, since otherwise we can reverse $\pi$ in a whole. Note that if
$r(x_{i})=l(x_{i+1})=r(y_{j})=l(y_{j+1})$, $\langle
r(x_{i}),l(x_{i+1})\rangle$ can be either positive or negative, we call it an
entangled adjacency.

A segment $I$ of $\pi$ is referred to as _positive_ (resp. _negative_) if all
the adjacencies in it have positive (resp. _negative_) directions, and $I$ is
_maximal_ , if it is not a subsegment of any other positive (resp. negative)
segment in $\pi$ than $I$. A maximal positive (resp. negative) segment is
abbreviated as an _MPS_ (resp. _MNS_). (See Figure 6 for an example.)

Figure 6: An example of _MPS_ and _MNS_. Positive adjacencies and _MPS_ are
marked with straight lines, while negative adjacencies and _MNS_ are marked
with curved lines, the boundaries are circled, and the entangled adjacency
$\langle r_{4},-r_{4}\rangle$ is colored green.

Now we assign proper directions to the entangled adjacencies such that the
number of _MNS_ of $\pi$ is minimized. Let $\langle
r(x_{i}),l(x_{i+1})\rangle$ be an entangled adjacency, then
$r(x_{i})=l(x_{i+1})=r(y_{j})=l(y_{j+1})$, accordingly
$l(x_{i})=r(x_{i+1})=l(y_{j})=r(y_{j+1})$. Since $\pi$ is simple,
$r(x_{i-1})\neq l(x_{i+2})$; hence, if $r(x_{i-1})=r(y_{j-1})$ and
$l(x_{i+2})=l(y_{j+2})$, then both $\langle r(x_{i-1}),l(x_{i})\rangle$ and
$\langle r(x_{i+1}),l(x_{i+2})\rangle$ are positive; if
$r(x_{i-1})=l(y_{j+2})$ and $l(x_{i+2})=r(y_{j-1})$, then both $\langle
r(x_{i-1}),l(x_{i})\rangle$ and $\langle r(x_{i+1}),l(x_{i+2})\rangle$ are
negative. Thus, we have:

###### Proposition 4.1

The two neighbors of any entangled adjacency always have the same direction.
The number of _MNS_ is minimized provided that the direction of each entangled
adjacency is the same as its neighbors.

The two neighbors of any entangled adjacency always have the same direction.
Therefore, the number of _MNS_ is minimized provided that the direction of
each entangled adjacency is the same as its neighbors.

Once the directions of all the adjacencies of $\pi$ are fixed, the positive
segments and negative segments appear alternatively on $\pi$, in particular,
both the leftmost and rightmost segments are positive. Let
$N_{\emph{MPS}}[\pi]$ and $N_{\emph{MNS}}[\pi]$ be the number of _MPS_ and
_MNS_ respectively on $\pi$, then $N_{\emph{MPS}}[\pi]-N_{\emph{MNS}}[\pi]=1$.
Accordingly,

###### Theorem 4.1

$\pi=\tau$ if and only if $N_{\emph{MNS}}[\pi]=0$.

_Proof._ The sufficient part is surely true.

We prove the efficient part inductively. Our inductive hypothesis is that
$x_{i}=y_{i}$ for $0\leq i\leq n+1$. Initially, we have $x_{0}=y_{0}=+0$. For
the inductive step, let $y_{j}$ be the other occurrence of $|y_{i}|$, since
$y_{i}$ and $y_{j}$ have distinct signs in $\tau$, $r(y_{i})=l(y_{j})$,
together with the inductive hypothesis that $x_{i}=y_{i}$, we have,
$r(x_{i})=r(y_{i})=l(y_{j})$. As the adjacency $\langle
r(x_{i}),l(x_{i+1})\rangle$ is positive, there must be some $y_{k}$ of $\tau$,
such that $r(y_{k})=r(x_{i})$ and $l(y_{k+1})=l(x_{i+1})$. Since $y_{i}$ is
the unique occurrence satisfying $r(y_{i})=r(x_{i})$, then $k=i$, and
consequently, $l(y_{i+1})=l(x_{i+1})$ and $x_{i+1}=y_{i+1}$. This completes
the induction. $\sqcap$$\sqcup$

An occurrence of $x_{i}$ ($1\leq i\leq n$), is called a boundary if the
directions of its left adjacency $\langle r(x_{i-1}),l(x_{i})\rangle$ and
right adjacency $\langle r(x_{i}),l(x_{i+1})\rangle$ are distinct. Thus, any
boundary is shared by an _MPS_ and an _MNS_. (See Figure 6 for an example.)
Let $x_{i}$ and $x_{j}$ ($i<j$) be a pair of occurrences of $|x_{i}|$ in $\pi$
with distinct signs, performing a symmetric reversal $\rho(i,j)$ on $|x_{i}|$
yields $\pi^{\prime}$. We have,

###### Lemma 4.1

$N_{\emph{MNS}}[\pi]-N_{\emph{MNS}}[\pi^{\prime}]\leq 1$.

_Proof._ The proof is conducted by enumerating all possible cases that $x_{i}$
and $x_{j}$ may be boundaries, in the interior of a _MPS_ or a _MNS_. For a
revenue of 1, the unique case is that both $x_{i}$ and $x_{j}$ are boundaries
and the substring $[x_{i},\dots,x_{j}]$ starts and ends with both _MNS_ or
both _MPS_. $\sqcap$$\sqcup$

Lemma 4.1 implies that a scenario will be optimal, provided that each
symmetric reversal subtracts the number of _MNS_ by one. Luckily, we can
always find such symmetric reversals till $\pi$ has been transformed into
$\tau$.

###### Lemma 4.2

Let $x_{i}$ and $x_{j}$ ($i<j$) be the two occurrences of the repeat $x$ in
$\pi$, (I) either they are both boundaries or none of them is a boundary. (II)
If $x_{i}$ and $x_{j}$ are both boundaries, the adjacencies $\langle
r(x_{i}),l(x_{i+1})\rangle$ and $\langle r(x_{j-1}),l(x_{j})\rangle$ have the
same direction, and the adjacencies $\langle r(x_{i-1}),l(x_{i})\rangle$ and
$\langle r(x_{j}),l(x_{j+1})\rangle$ have the same direction. (III) Moreover,
if $x_{i}=x_{j}$, then $\langle r(x_{i}),l(x_{i+1})\rangle$ and $\langle
r(x_{j-1}),l(x_{j})\rangle$ are matched to two consecutive adjacencies in
$\tau$, and $\langle r(x_{i-1}),l(x_{i})\rangle$ and $\langle
r(x_{j}),l(x_{j+1})\rangle$ are matched to two consecutive adjacencies in
$\tau$.

_Proof._ (I) Without loses of generality, assume that $x_{i}$ is a boundary.
Let $y_{k}$ and $y_{l}$ be the occurrences of $|x_{i}|$ in $\tau$ with
distinct signs, thus $l(y_{k})=r(y_{l})\neq r(y_{k})=l(y_{l})$. We partition
the adjacencies associated with $y_{k}$ and $y_{l}$ into two groups: $\langle
r(y_{k-1}),l(y_{k})\rangle$ and $\langle r(y_{l-1}),l(y_{l})\rangle$ form
Group-(I) and $\langle r(y_{k}),l(y_{k+1})\rangle$ and $\langle
r(y_{l}),l(y_{l+1})\rangle$ form Group-(II). The group partition guarantees
that $l(y_{k})$ and $r(y_{l})$ are in different groups, and $r(y_{k})$ and
$l(y_{l})$ are also in different groups. Since the two adjacencies $\langle
r(x_{i-1}),l(x_{i})\rangle$ and $\langle r(x_{i}),l(x_{i+1})\rangle$ have
distinct directions, so they are either matched to Group-(I) or Group-(II),
accordingly, the two adjacencies $\langle r(x_{j-1}),l(x_{j})\rangle$ and
$\langle r(x_{j}),l(x_{j+1})\rangle$ have to be matched to the other group. In
either case, $\langle r(x_{j-1}),l(x_{j})\rangle$ and $\langle
r(x_{j}),l(x_{j+1})\rangle$ have distinct directions. Thus, $x_{j}$ is a
boundary.

(II) If $\langle r(x_{i-1}),l(x_{i})\rangle$ and $\langle
r(x_{i}),l(x_{i+1})\rangle$ are matched to group-(I), then $\langle
r(x_{i}),l(x_{i+1})\rangle$ is negative, $l(x_{j})$ must be matched to either
$r(y_{k})$ or $r(y_{l})$, which implies that $\langle
r(x_{j-1}),l(x_{j})\rangle$ is also negative. If $\langle
r(x_{i-1}),l(x_{i})\rangle$ and $\langle r(x_{i}),l(x_{i+1})\rangle$ are
matched to group-(II), then $\langle r(x_{i}),l(x_{i+1})\rangle$ is positive,
$l(x_{j})$ must be matched to either $l(y_{k})$ or $l(y_{l})$, which implies
that $\langle r(x_{j-1}),l(x_{j})\rangle$ is also positive. Since the
direction of $\langle r(x_{i-1}),l(x_{i})\rangle$ is different from $\langle
r(x_{i}),l(x_{i+1})\rangle$, and the direction of $\langle
r(x_{j}),l(x_{j+1})\rangle$ is different from $\langle
r(x_{j-1}),l(x_{j})\rangle$, $\langle r(x_{i-1}),l(x_{i})\rangle$ and $\langle
r(x_{j}),l(x_{j+1})\rangle$ have the same direction.

(III) When $x_{i}=x_{j}$, the positive pair of adjacencies must be matched to
the two adjacencies associated with the occurrence with sign “+”, and the
negative pair of adjacencies must be matched to the two adjacencies associated
the occurrence with sign “-”, so they are consecutive in $\tau$.
$\sqcap$$\sqcup$

Figure 7: An illustration of Lemma 4.2. Assume that $x_{i}=y_{k}=-y_{l}$,
$\langle r(x_{j-1}),l(x_{j})\rangle$ and $\langle r(x_{j}),l(x_{j+1})\rangle$
are matched to Group-(I). In case ($a$), the signs of $x_{i}$ and $x_{j}$ are
distinct; and in case ($b$), the signs of $x_{i}$ and $x_{j}$ are identical.

###### Lemma 4.3

Every _MPS_ in $\pi$ has an identical segment in $\tau$, and every _MNS_ in
$\pi$ has a reversed and negated segment in $\tau$.

_Proof._ Let $I=[x_{i},x_{i+1},\dots,x_{i+k}]$ be a _MPS_ in $\pi$. There must
be an adjacency $\langle r(y_{j}),l(y_{j+1})\rangle$ such that
$r(x_{i})=r(y_{j})$ and $l(x_{i+1})=l(y_{j+1})$, We conduct an inductive
proof. Our inductive hypothesis is that $x_{i+t}=y_{j+t}$, for all $0\leq
t\leq k$. Initially, we have $x_{i}=y_{j}$. For the inductive step, let
$y_{j^{\prime}}$ be the other occurrence of $|y_{j+t}|$ in $\tau$. Since
$y_{j^{\prime}}$ and $y_{j+t}$ have distinct signs,
$r(y_{j+t})=l(y_{j^{\prime}})$, together with the inductive hypothesis, we
have $r(x_{i+t})=r(y_{j+t})=l(y_{j^{\prime}})$, which implies that $\langle
r(x_{i+t}),l(x_{i+t+1})\rangle$ must be matched to $\langle
r(x_{j+t}),l(y_{i+t+1})\rangle$. Consequently $l(x_{i+t+1})=l(y_{i+t+1})$ and
$x_{i+t+1}=y_{i+t+1}$. This completes the induction.

The proof for an _MNS_ in $\pi$ is similar hence omitted. $\sqcap$$\sqcup$

###### Theorem 4.2

If there exists an MNS in $\pi$, then there exists a pair of boundaries, which
are occurrences of the same repeat with different orientations.

_Proof._ Assume to the contrary that each pair of boundaries, which are
duplications of the same repeat, have the same sign. From Lemma 4.2 and 4.3,
each pair of boundaries that have equal absolute values locate on two distinct
_MPS_ s, whose corresponding segments are adjacent in $\tau$. As each _MPS_ is
associated with two boundaries, there is a path along all the _MPS_ s and
boundaries in $\pi$, the corresponding segments of all the _MPS_ s forms a
substring of $\tau$. Note that $\langle r(x_{0}),l(x_{1})\rangle$ and $\langle
r(x_{n}),l(x_{n+1})\rangle$ are both positive, so the substring contains both
$y_{0}$ and $y_{n+1}$, and it becomes the whole of $\tau$. That is a
contradiction, since $\tau$ also contains the corresponding segments of the
_MNS_ s. $\sqcap$$\sqcup$

Now, we formally present the algorithm as Algorithm 1 for computing the least
number of symmetric reversals to transform $\pi$ into $\tau$.

Algorithm 1 An algorithm for the 2-Balanced Case of SMSR

Input:: Two chromosomes $\pi$ and $\tau$, with
$\mathcal{A}[\pi]=\mathcal{A}[\tau]$ and $dp[\pi]=dp[\tau]=2$, and the
occurrences of each repeat has different orientation on $\tau$.
Output:: a sequence of minimum number of symmetric reversals that transforms
$\pi$ into $\tau$.

1:Delete the redundant repeats from $\pi$ and $\tau$ when $dp[\pi]=2$.(Lemma
3.1)

2:Build the bijection between $\mathcal{A}[\pi]$ and $\mathcal{A}[\tau]$.

3:Determine the direction of each adjacency (except entangled) of $\pi$
according to the bijection.

4:Assign the direction of each entangled adjacency the same as its two
neighbors. (See Proposition 4.1, where the two neighbors always have the same
direction.)

5:Identify all the _MPS_ , _MNS_ and boundaries in $\pi$.

6:while there exists an _MNS_ do

7: Find a pair of boundaries of the same repeat with different orientations.

8: Perform a symmetric reversal on this pair of inverted repeats.

9:end while

10:return all the symmetric reversals.

###### Theorem 4.3

Algorithm 1 gives a sequence of minimum number of symmetric reversals that
transforms $\pi$ into $\tau$, and runs in $O(n^{2})$ time.

_Proof._ Theorem 4.2 guarantees the existence of two boundaries with
$x_{i}=-x_{j}$, whenever there is an _MNS_. From Lemma 4.2-(II), performing
the symmetric reversal on $|x_{i}|$ will decrease the number of _MNS_ by one.
Thus, the number of symmetric reversals performed by the algorithm _Balanced-2
SMSR_ is equal to the number of _MNS_ in $\pi$, which is optimum according to
Theorem 4.1.

As for the time complexity, it takes $O(n^{2})$ time to build the bijection
between $\mathcal{A}[\pi]$ and $\mathcal{A}[\tau]$. Obviously, steps 2-4 take
linear time. The while-loop runs at most $n/2$ rounds, and in each round, it
takes linear time to find a pair of proper boundaries. Totally, the time
complexity is $O(n^{2})$. $\sqcap$$\sqcup$

We comment that the result in this section is perhaps the best that we can
hope, since we will show in section 6 that, when the duplication number is 2
but $\tau$ is not required to contain both $+|x|$ and $-|x|$ for each repeat
$|x|\in\Sigma_{2}$, the _SMSR_ problem becomes NP-hard. More generally, when
the duplication number of $\pi$ and $\tau$ is unlimited, the scenario is quite
different. Nevertheless, in the next section, we proceed to handle this
general case.

##  5 An $O(n^{2})$ Decision Algorithm for the General Case

For the general case, i.e., when the duplication number for the two related
input genomes is arbitrary, the extension of the algorithm in Section 3 is
non-trivial as it is impossible to make the genomes simple. Our overall idea
is to fix any bijection $f$ between the (identical) adjacencies of the input
genomes, and build the corresponding alternative-cycle graph. This
alternative-cycle graph is changing according to the corresponding symmetric
reversals; and we show that, when the graph contains only 1-cycles, then the
target $\tau$ is reached. Due to the changing nature of the alternative-cycle
graph, we construct a blue edge intersection graph to capture these changes.
However, this is not enough as the blue intersection graph built from the
alternative-cycle graph could be disconnected and we need to make it connected
by adding additional vertices such that the resulting sequence of symmetric
reversals are consistent with the original input genomes, and can be found in
the new intersection graph (called IG, which is based on the input genomes
$\pi$ and $\tau$ as well as $f$). We depict the details in the following.

Suppose that we are given two related chromosomes
$\pi=[x_{0},x_{1},\dots,x_{n+1}]$ and $\tau=[y_{0},y_{1},\dots,y_{n+1}]$, such
that $x_{0}=y_{0}=+r_{0}$ and $x_{n+1}=y_{n+1}=-r_{0}$. Theorem 2.1 shows that
$\mathcal{A}[\pi]=\mathcal{A}[\tau]$ is a necessary condition, thus there is a
bijection $f$ between identical adjacencies in $\mathcal{A}[\pi]$ and
$\mathcal{A}[\tau]$, as shown in Figure 8. Based on the bijection $f$ , we
construct the alternative-cycle graph $ACG(\pi,\tau,f)$ as follows. For each
$x_{i}$ in $\pi$, construct an ordered pair of nodes, denoted by $l(x_{i})$
and $r(x_{i})$, which are connected by a red edge. For each $y_{k}$ in $\tau$,
assume that $\langle r(y_{k-1}),l(y_{k})\rangle$ is matched to $\langle
r(x_{i-1}),l(x_{i})\rangle$, and $\langle r(y_{k}),l(y_{k+1})\rangle$ is
matched to $\langle r(x_{j-1}),l(x_{j})\rangle$, in the bijection $f$. There
are four cases:

  1. 1.

$l(y_{k})=l(x_{i})$ and $r(y_{k})=r(x_{j-1})$, then connect $l(x_{i})$ and
$r(x_{j-1})$ with a blue edge,

  2. 2.

$l(y_{k})=r(x_{i-1})$ and $r(y_{k})=r(x_{j-1})$, then connect $r(x_{i-1})$ and
$r(x_{j-1})$ with a blue edge,

  3. 3.

$l(y_{k})=l(x_{i})$ and $r(y_{k})=l(x_{j})$, then connect $l(x_{i})$ and
$l(x_{j})$ with a blue edge,

  4. 4.

$l(y_{k})=r(x_{i-1})$ and $r(y_{k})=l(x_{j})$, then connect $r(x_{i-1})$ and
$l(x_{j})$ with a blue edge.

Figure 8: The bijection between identical adjacencies in $\mathcal{A}[\pi]$
and $\mathcal{A}[\tau]$, and the corresponding alternative-cycle graph.

Actually, two nodes connected by a red edge implies they are from the same
occurrence of some repeat/gene in $\pi$, so each occurrence of some
repeat/gene in $\pi$ corresponds to a red edge; and similarly, two nodes
connected by a blue edge implies that they are from the same occurrence of
some repeat/gene in $\tau$, thus each occurrence of some repeat/gene in $\tau$
corresponds to a blue edge. Note that each node associates with one red edge
and one blue edge, so $ACG(\pi,\tau,f)$ is composed of edge disjoint cycles,
on which the red edges and blue edge appears alternatively. A cycle composed
of $c$ blue edges as well as $c$ red edges is called a $c$-cycle, it is called
a long cycle when $c\geq 2$.

###### Theorem 5.1

Given two chromosomes $\pi^{*}$ and $\tau$, $\pi^{*}=\tau$ if and only if
$\mathcal{A}[\pi^{*}]=\mathcal{A}[\tau]$, and there is a bijiection $f$
between the identical adjacencies in $\mathcal{A}[\pi^{*}]$ and
$\mathcal{A}[\tau]$, such that all the cycles in the resulting alternative-
cycle graph $ACG(\pi^{*},\tau,f)$ are 1-cycles.

_Proof._ Assume that $\pi^{*}=[z_{0},z_{1},\dots,z_{n},z_{n+1}]$ and
$\tau=[y_{0},y_{1},\dots,y_{n},y_{n+1}]$, where $z_{0}=y_{0}=+r_{0}$ and
$z_{n+1}=y_{n+1}=-r_{0}$.

The sufficiency part is surely true, since we have $z_{i}=z_{i}$ and bijection
$f$ is to match $\langle r(z_{i-1}),l(z_{i})\rangle$ with $\langle
r(y_{i-1}),l(y_{i})\rangle$.

Now we prove the necessity part inductively. Our inductive hypothesis is that
$z_{i}=y_{i}$ for $0\leq i\leq n+1$. Initially, we have
$l(z_{0})=l(y_{0})=r_{0}^{h}$ and $r(z_{0})=r(y_{0})=r_{0}^{t}$, as
$\mathcal{A}[\pi^{*}]=\mathcal{A}[\tau]$, we always assume that $z_{1}=y_{1}$,
since otherwise, we can reverse the whole chromosome $\tau$. For the inductive
step, as $l(z_{i})$ and $r(z_{i})$ form a 1-cycle, so then adjacency $\langle
r(z_{i}),l(z_{i+1})\rangle$ is matched to $\langle
r(y_{i}),l(y_{i+1})\rangle$, and from the inductive hypothesis that
$r(z_{i})=r(y_{i})$, we have, $l(z_{i+1})=l(y_{i+1})$, and thus,
$z_{i+1}=y_{i+1}$. $\sqcap$$\sqcup$

The above theorem gives us a terminating condition for our algorithm: let
$\pi$ and $\tau$ be the input chromosomes, and our algorithm keeps updating
the alternative-cycle graph until all cycles in it become 1-cycles.
unfortunately, in the following, we observe that some cycles can not be
performed on symmetric reversals directly, then we consider these cycles
intersecting with each other as a connected component. But this is still not
enough, since there could also be some connected components which do not admit
any symmetric reversal, we managed to handle this case by joining all the
cycles of the same repeat into a whole connected component.

###### Lemma 5.1

In an alternative-cycle graph, each cycle corresponds to a unique repeat and
every edge (both red and blue) in the cycle corresponds to an occurrence of
the unique repeat.

_Proof._ W.l.o.g, assume that $l(x_{i})$ are $l(x_{j})$ connected with a blue
edge, from the construction of the alternative-cycle graph, there must be an
occurrence in $\tau$, say $y_{k}$, such that
$\\{l(x_{i}),l(x_{j}\\}=\\{l(y_{k}),r(y_{k})\\}$, thus,
$|x_{i}|=|x_{j}|=|y_{k}|$, and the blue edge $(l(x_{i}),l(x_{j}))$ corresponds
the occurrence $y_{k}$ of the repeat $|y_{k}|$. $\sqcap$$\sqcup$

Since each gene appears once in $\pi$, Lemma 5.1 implies that each gene has a
1-cycle in $ACG(\pi,\tau,f)$, these 1-cycles will be untouched throughout our
algorithm.

###### Lemma 5.2

In an alternative-cycle graph, if we add a green edge connecting each pairs of
nodes $r(x_{i})$ and $l(x_{i+1})$ (for all $0\leq i\leq n$), then all the blue
edges and green edges together form a (blue and green alternative) path. (See
Figure 6.)

_Proof._ Actually, the green edge connecting $r(x_{i})$ and $l(x_{i+1})$
($0\leq i\leq n$) is the adjacency $\langle r(x_{i}),l(x_{i+1})\rangle$ of
$\mathcal{A}[\pi]$, which is identical to some adjacency $\langle
r(y_{j}),l(y_{j+1})\rangle$ of $\mathcal{A}[\tau]$ according to the bijection
between identical adjacencies of $\mathcal{A}[\pi]$ and $\mathcal{A}[\tau]$.
Therefore, $y_{j}$ and $y_{j+1}$ appears consecutively in $\tau$, and
following the construction of $ACG(\pi,\tau,f)$ and Lemma 5.1, they correspond
to the two blue edges, one of which is associated with $r(x_{i})$ and the
other is associated with $l(x_{i+1})$ in $ACG(\pi,\tau,f)$, thus, the two blue
edges are connected through the green edge $(r(x_{i}),l(x_{i+1}))$. The above
argument holds for every green edge, therefore, all the blue edges and green
edges constitute a path. We show an example in Figure 8. $\sqcap$$\sqcup$

Let $x\in\Sigma$ be a repeat. Let $x_{i}$ and $x_{j}$ be two occurrences of
$x$ in $\pi$, where $i\neq j$. A blue edge is _opposite_ if it connects
$l(x_{i})$ and $l(x_{j})$ or $r(x_{i})$ and $r(x_{j})$. A blue edge is _non-
opposite_ if it connects $l(x_{i})$ and $r(x_{j})$ or $r(x_{i})$ and
$l(x_{j})$.

Specially, the blue on any 1-cycle (with a blue edge and a red edge) is non-
opposite. A cycle is _opposite_ if it contains at least one opposite blue
edge.

###### Lemma 5.3

Let $x_{i}$ and $x_{j}$ be two occurrences of repeat $x$ in $\pi$. In the
alternative-cycle graph $ACG(\pi,\tau,f)$, if $l(x_{i})$ and $l(x_{j})$ ( or
$r(x_{i})$ and $r(x_{j})$) are connected with an opposite edge, $x_{i}$ and
$x_{j}$ has different orientations; and if $l(x_{i})$ and $r(x_{j})$ ( or
$r(x_{i})$ and $l(x_{j})$) are connected with a non-opposite edge, $x_{i}$ and
$x_{j}$ has the same orientations.

_Proof._ We conduct the proof according to the construction of the
alternative-cycle graph $ACG(\pi,\tau,f)$.

If $l(x_{i})$ and $l(x_{j})$ are connected with an opposite edge, there must
be an occurrence of $x$ in $\tau$, say $y_{k}$, such that
$\\{l(x_{i}),l(x_{j})\\}=\\{l(y_{k}),r(y_{k})\\}$. If $l(x_{i})=l(y_{k})$ and
$l(x_{j})=r(y_{k})$, then the orientations of $x_{i}$ and $y_{k}$ are the
same, and the orientations of $x_{j}$ and $y_{k}$ are different, thus $x_{i}$
and $x_{j}$ have different orientations. If $l(x_{i})=r(y_{k})$ and
$l(x_{j})=l(y_{k})$, then the orientations of $x_{i}$ and $y_{k}$ are
different, and the orientations of $x_{j}$ and $y_{k}$ are the same, also
$x_{i}$ and $x_{j}$ have different orientations. It will be similar when
$r(x_{i})$ and $r(x_{j})$ are connected with an opposite edge.

If $l(x_{i})$ and $r(x_{j})$ are connected with a non-opposite edge, there
must be an occurrence of $x$ in $\tau$, say $y_{k}$, such that
$\\{l(x_{i}),r(x_{j}\\}=\\{l(y_{k}),r(y_{k})\\}$. If $l(x_{i})=l(y_{k})$ and
$r(x_{j})=r(y_{k})$, then both $x_{i}$ and $x_{j}$ have the same orientations
as $y_{k}$, thus $x_{i}$ and $x_{j}$ have the same orientations. If
$l(x_{i})=r(y_{k})$ and $r(x_{j})=l(y_{k})$, then both $x_{i}$ and $x_{j}$
have different orientations with $y_{k}$, thus $x_{i}$ and $x_{j}$ have the
same orientations. It will be similar when $r(x_{i})$ and $l(x_{j})$ are
connected with an opposite edge. $\sqcap$$\sqcup$

###### Proposition 5.1

Given a $k$-cycle $C$ of $x$, performing a symmetric reversal on two
occurrences of $x$ that are connected by an opposite blue edge, will break $C$
into a $(k-1)$-cycle as well as a 1-cycle. Given a $k_{1}$-cycle $C_{1}$ and a
$k_{2}$-cycle $C_{2}$ of $x$, performing a symmetric reversal on the two
occurrences of $x_{i}\in C_{1}$ and $x_{j}\in C_{2}$, will join $C_{1}$ and
$C_{2}$ into a $(k_{1}+k_{2})$-cycle.

Now, we construct the _blue edge intersection graph_
$BG(\pi,\tau,f)=(BV_{\pi},BE_{\pi},f)$ according to $ACG(\pi,\tau,f)$, viewing
each blue edge as an interval of the two nodes it connects. For each interval,
construct an original vertex in $BV_{\pi}$, and set its weight to be 1, set
its color to be black if the blue edge is opposite, and white otherwise. An
edge in $BE_{\pi}$ connects two vertices if and only if their corresponding
intervals intersect but neither overlaps the other. An example of the blue
edge intersection graph is shown in Figure 9-($b$).

Note that each connected component of $BG(\pi,\tau,f)$ forms an interval on
$\pi$, for each connected component $P$ in $BG(\pi,\tau,f)$, we use
$\overline{P}$ to denote its corresponding interval on $\pi$.

###### Lemma 5.4

Let $P$ be some connected component of $BG(\pi,\tau,f)$, the leftmost endpoint
of $\overline{P}$ must be a left node of some $x_{i}$, i.e., $l(x_{i})$, and
the rightmost endpoint of $\overline{P}$ must be a right node of some $x_{j}$,
i.e., $r(x_{j})$, where $i<j$.

_Proof._ Since each blue edge connects two nodes of the interval
$\overline{P}$, the number of nodes in $\overline{P}$ must be even. Hence the
boundary nodes of an interval can neither be both left nodes nor be both right
nodes.

Assume to the contrary that the leftmost endpoint of $\overline{P}$ is
$r(x_{i})$ and the rightmost endpoint of $\overline{P}$ is $l(x_{j})$. There
are a total of $2(j-i)$ nodes appearing in $\overline{P}$. If we connect each
pairs of nodes $r(x_{k})$ and $l(x_{k+1})$ (for all $i\leq k\leq j$) with a
green edge, then there are $j-i$ green edges as well as $j-i$ blue edges
between the $2(j-i)$ nodes of $\overline{P}$. Since each node is associated
with one green edge and one blue edge, these green edges and blue edges form
cycles, which is a contradiction to Lemma 5.2. $\sqcap$$\sqcup$

###### Lemma 5.5

All the vertices in $BG(\pi,\tau,f)$ corresponding to the blue edges on the
same long cycle in $ACG(\pi,\tau,f)$ are in the same connected component of
$BG(\pi,\tau,f)$.

_Proof._ Assume to the contrary that there exist some connected components
each containing a part of blue edges of some cycle. Let $P$ be such a type of
connected component that $\overline{P}$ does not overlap any other interval of
such type of connected components. Let $e=(x_{i}^{t},x_{j}^{h})$ and
$e^{\prime}=(x_{i^{\prime}}^{t},x_{j^{\prime}}^{h})$ be two blue edges on a
cycle $C$, such that their corresponding vertices $v\in P$, but
$v^{\prime}\notin P$. From the way we choose $P$, the two nodes
$x_{i^{\prime}}^{t}$ and $x_{j^{\prime}}^{h}$ connected by $e^{\prime}$ in $C$
can not be both inside the interval of $P$. So they must be both outside the
interval of $P$. Also, the two nodes $x_{i}^{t}$ and $x_{j}^{h}$ connected by
$e$ in $C$ can not be both on the boundary of the interval of $P$, since
otherwise, $e$ will not intersect with any other blue edge corresponding to a
vertex of $P$. W.l.o.g, assume that $x_{i}^{t}$ appears inside the interval of
$P$. Since $e$ and $e^{\prime}$ are on the same cycle $C$, besides $e$, there
must be an alternative path from $x_{i}^{t}$ to $x_{j^{\prime}}^{h}$ on $C$.
From Lemma 5.4, it is impossible that the travel along an alternative path
outside the scope of an interval via a red edge, so the alternative path from
$x_{i}^{t}$ to $x_{j^{\prime}}^{h}$ must contain a blue edge which connects a
node inside $\overline{P}$ with a node outside $\overline{P}$, which contracts
that $P$ is a connected component. $\sqcap$$\sqcup$

As the two blue edges of a non-opposite 2-cycle do not intersect each other,
we have,

###### Corollary 5.1

A non-opposite 2-cycle can not form a connected component of $BG(\pi,\tau,f)$.

For each repeat $x$, assume that it constitutes $k$ cycles in
$ACG(\pi,\tau,f)$. Let $x_{i_{1}}$, $x_{i_{2}}$, $\dots$, $x_{i_{k}}$ be the
$k$ occurrences of $x$ that are in distinct cycles in $ACG(\pi,\tau,f)$, where
$1\leq i_{1}<i_{2}<\cdots<i_{k}\leq n$. We construct $k-1$ _additional
vertices_ corresponding to the intervals
$[r(x_{i_{j}})-\epsilon,l(x_{i_{j+1}})+\epsilon]$ to $BV_{\pi}$ ($1\leq j\leq
k-1$), for each such vertex, set its weight to be 1, and set its color to be
black if the signs of $x_{i_{j}}$ and $x_{i_{j+1}}$ are distinct, and white
otherwise. See the vertex marked with 10 in Figure 9-($c$) for an example.
Also, there is an edge between two vertices of $BV_{\pi}$ if and only if their
corresponding intervals intersect, but none overlaps the other. The resulting
graph is called the _intersection graph_ of $\pi$, denoted as
$IG(\pi,\tau,f)=(V[\pi],E[\pi])$. An example is shown in Figure 9-($c$). Let
$V_{\pi}^{w}\subseteq V[\pi]$ be the subset of vertices which corresponding to
non-opposite blue edges on long cycles in $ACG(\pi,\tau,f)$.

Figure 9: ($a$) The alternative-cycle graph $ACG(\pi,\tau,f)$, where each blue
edge is marked with a number. ($b$) The blue edge intersection graph
$BG(\pi,\tau,f)$. ($c$) The intersection graph $IG(\pi,\tau,f)$ with
additional vertices, where each number represents an interval.

From Lemma 5.4 and the construction of the intersection graph of $\pi$, all
the vertices corresponding to all the blue edges of the same repeat are in the
same connected component. Note that the intersection graph of $\pi$ may be
distinct, when the bijection between identical adjacencies of
$\mathcal{A}[\pi]$ and $\mathcal{A}[\tau]$ differs. Nevertheless, we have,

###### Lemma 5.6

Let $\pi$ and $\tau$ be two related chromosomes with
$\mathcal{A}[\pi]=\mathcal{A}[\tau]$. Let $x_{i}$ and $x_{j}$ ($i<j$) be two
occurrences of $x$ in $\pi$, and $x_{i^{\prime}}$ and $x_{j^{\prime}}$
($i^{\prime}<j^{\prime}$) be two occurrences of $x^{\prime}$ in $\pi$, if
either $i<i^{\prime}<j<j^{\prime}$ or $i^{\prime}<i<j^{\prime}<j$ is
satisfied, then, based on any bijection $f$ between
$\mathcal{A}[\pi]=\mathcal{A}[\tau]$, in the intersection graph
$IG(\pi,\tau,f)$, the vertices corresponding to all the intervals of $x$ and
$x^{\prime}$ are in the same connected component.

_Proof._ Assume that $i<i^{\prime}<j<j^{\prime}$, since the other case is
similar. From Lemma 5.4 and the construction of the intersection graph, in any
intersection graph of $\pi$, the vertices corresponding to the intervals
associated with $x_{i}$ and $x_{j}$ are in the same connected component $P$;
also, the vertices corresponding to the intervals associated with
$x_{i^{\prime}}$ and $x_{j^{\prime}}$ are in the same connected component
$P^{\prime}$. We show that $\overline{P}$ intersects $\overline{P^{\prime}}$,
and thus $P=P^{\prime}$.

It is impossible that $\overline{P}$ and $\overline{P^{\prime}}$ are disjoint,
because the interval $[l(x_{i}),\dots,r(x_{j})]$ is a part of $\overline{P}$,
and the interval $[l(x_{i^{\prime}}),\dots,r(x_{j^{\prime}})]$ is a part of
$\overline{P^{\prime}}$, but $[l(x_{i}),\dots,r(x_{j})]$ intersects with
$[l(x_{i^{\prime}}),\dots,r(x_{j^{\prime}})]$.

If $\overline{P}$ overlaps $\overline{P^{\prime}}$, in the intersection graph
$IG(\pi,\tau,f)$, there exists a path from some interval associated with
$x_{j}$ to some interval associated with $x_{i}$, among the intervals
corresponding to the vertices on this path, there must be one that intersects
with $\overline{P^{\prime}}$.

If $\overline{P^{\prime}}$ overlaps $\overline{P}$, in the intersection graph
$IG(\pi,\tau,f)$, there exists a path from some interval associated with
$x_{i^{\prime}}$ to some interval associated with $x_{j^{\prime}}$, among the
intervals corresponding to the vertices on this path, there must be one that
intersects with $\overline{P}$. $\sqcap$$\sqcup$

Actually, the connected components of the intersection graph partition the
repeats on $\pi$ into groups. From Lemma 5.4 and Lemma 5.6, the group
partition of the repeats is independent of the bijection between identical
adjacencies of $\mathcal{A}[\pi]$ and $\mathcal{A}[\tau]$. In other words, the
group partition will be fixed once $\pi$ and $\tau$ are given.

Similar to the intersection graph of chromosomes with a duplication number of
2, the intersection graph of chromosomes with unrestricted duplication number
also admit the rule-I, rule-II, and rule-III, as in Section 3, while
performing a symmetric reversal on $\pi$.

###### Theorem 5.2

If a connected component of $IG(\pi,\tau,f)$ contains a black vertex, then
there exists a symmetric reversal, after performing it, we obtain
$\pi^{\prime}$, any newly created connected component containing a white
vertex, which corresponds to a blue edge on a non-opposite long cycle in
$ACG(\pi^{\prime},\tau,f)$, also contains a black vertex.

_Proof._ Each vertex in $IG(\pi,\tau,f)=(V[\pi],E[\pi])$ corresponds to an
interval that are flanked by two occurrences of the same repeat. A vertex is
black when the two occurrences have different signs, thus admits a symmetric
reversal. For each black vertex $x$, let $C_{1},C_{2},\dots,C_{m}$ be the
newly created connected components after performing the symmetric reversal on
$x$, where each of $C_{1},C_{2},\dots,C_{i}$ contains a white vertex
corresponding to a blue edge on a non-opposite long cycle in
$ACG(\pi^{\prime},\tau,f)$, but does not contain a black vertex, each of
$C_{i+1},C_{i+2},\dots,C_{j}$ contains additional vertices and vertices
corresponding to blue edges on 1-cycles in $ACG(\pi^{\prime},\tau,f)$, but
does not black vertex, and each of $C_{j+1},C_{j+2},\dots,C_{m}$ contains a
black vertex, $0\leq i\leq j\leq m$. Let $\Delta(x)$ be the number of white
vertices in $C_{1},C_{2},\dots,C_{j}$.

We show next that if there exists a connected component, which contains a
white vertex corresponding to a blue edge on a non-opposite long cycle in
$ACG(\pi^{\prime},\tau,f)$ , but does not contain a black vertex, then there
would be a black vertex $x^{\prime}$ such that $\Delta(x^{\prime})<\Delta(x)$.

Assume to the contrary that $x$ is the black vertex with the minimum
$\Delta(x)>0$. Let $x^{\prime}$ be the neighbor of $x$ in $C_{1}$. Then,
$x^{\prime}$ is a black vertex prior to performing the symmetric reversal of
$x$. It is sufficient to show that $\Delta(x^{\prime})<\Delta(x)$, and hence
contradicting with that $\Delta(x)$ is minimum. From Lemma 3.4 and Lemma 3.5,
the color of all the vertices in $C_{j+1},C_{j+2},\dots,C_{m}$ are preserved,
and all the edges in $C_{j+1},C_{j+2},\dots,C_{m}$ are preserved after
performing the symmetric reversal of $x^{\prime}$. Therefore,
$\Delta(x^{\prime})$ will also not count any vertex in
$C_{j+1},C_{j+2},\dots,C_{m}$, consequently,
$\Delta(x^{\prime})\leq\Delta(x)$.

Since $C_{1}$ contains a white vertex corresponding to a blue edge on a non-
opposite long cycle, following Lemma 5.5 and Corollary 5.1, $C_{1}$ contains
at least 3 vertices. Let $N_{1}(x)$ be the neighbor set of $x$ in $C_{1}$, and
$x^{\prime}\in N_{1}(x)$. There must exist a neighbor of $x^{\prime}$ in
$C_{1}$, say $x^{\prime\prime}$. If $x^{\prime\prime}\in N_{1}(x)$, then
$(x^{\prime},x^{\prime\prime})\notin E[\pi]$, and $x^{\prime\prime}$ is black
prior to performing the symmetric reversal on $x$, thus, performing a
symmetric reversal on $x^{\prime}$ instead of $x$ will keep $x^{\prime\prime}$
be black, which implies $\Delta(x^{\prime})<\Delta(x)$. On the other side, if
$x^{\prime\prime}\notin N_{1}(x)$, then $(x^{\prime},x^{\prime\prime})\in
E[\pi]$, and $x^{\prime\prime}$ is white prior to performing the symmetric
reversal on $x$, Hence performing a symmetric reversal on $x^{\prime}$ instead
of $x$ will make $x^{\prime\prime}$ be black, which also implies
$\Delta(x^{\prime})<\Delta(x)$. Both contract the assumption that $\Delta(x)$
is the minimum. $\sqcap$$\sqcup$

###### Theorem 5.3

A chromosome $\pi$ can be transformed into the other chromosome $\tau$ by
symmetric reversals if and only if (I) $\mathcal{A}[\pi]=\mathcal{A}[\tau]$,
and (II) each white vertex in $V_{\pi}^{w}$ belongs to a connected component
of $IG(\pi,\tau,f)$ containing a black vertex.

_Proof._ $(\Rightarrow)$ If there exists a connected component of
$IG(\pi,\tau,f)$, say $C$, which contains a white vertex in $V_{\pi}^{w}$ but
does not contain a black vertex, then all the vertices of $C$ are white, and
they do not admit any symmetric reversal. Moreover, there must be a white
vertex, say $x$, which corresponds to a blue edge of a non-opposite long cycle
in $ACG(\pi,\tau,f)$. Thus, it is impossible to find a series of symmetric
reversals to transform this long cycle into 1-cycles. According to Theorem
5.1, $\pi$ can not be transformed into $\tau$.

$(\Leftarrow)$ Theorem 5.2 guarantees that, each original vertex either can be
performed with a symmetric reversal or its corresponding blue edge has been in
a 1-cycle. Finally, all the blue edges which correspond to the original
vertices are in 1-cycles; following Theorem 5.1, $\pi$ has been transformed
into $\tau$. $\sqcap$$\sqcup$

Now, we are ready to formally present the decision algorithm based on Theorem
5.3 for both the general case and the case, where the duplication number 2 in
Algorithm 2. We just directly test conditions (I) and (II) in Theorem 5.3.
Note that each connected component in $IG(\pi,\tau,f)$ may contain more than
one black vertex. By setting $Q=V_{\pi}^{b}$ in line 11, we can guarantee that
each connected component in $IG(\pi,\tau,f)$ is explored once during the
breadth first search so that $O(n^{2})$ running time can be kept.

Algorithm 2 The decision algorithm for SSR

Input: Two related chromosomes $\pi$ and $\tau$.
Output: $YES\backslash NO$

1:if $\mathcal{A}[\pi]\neq\mathcal{A}[\tau]$ then

2: return NO.

3:end if

4:Delete the redundant repeats from $\pi$ and $\tau$ when $dp[\pi]=2$.(Lemma
3.1)

5:Build a bijection $f$ between $\mathcal{A}[\pi]$ and $\mathcal{A}[\tau]$
when $dp[\pi]>2$ by mapping identical adjacencics together and adopting any
bijection among multiple occurences of the same adjacency.

6:Construct the alternative-cycle graph $ACG(\pi,\tau,f)$ based on $f$ when
$dp[\pi]>2$.

7:Construct the corresponding intersection graph
$IG(\pi,\tau,f)=(V_{\pi},E_{\pi})$ (based on $ACG(\pi,\tau,f)$ when
$dp[\pi]>2$ and directly from $\pi$ and $\tau$ if $dp[\pi]=2$).

8:if $dp[\pi]=2$ then

9: set $V_{\pi}^{w}$ to be the set of weight 1 white vertices

10:end if

11:if $dp[\pi]>2$ then

12: set $V_{\pi}^{w}$ to be the set of white vertices corresponding to non-
opposite blue edge on long cycle.

13:end if

14:Let $V_{\pi}^{b}$ be set of black vertices in $IG(\pi,\tau,f)$.

15:Set queue $Q=V_{\pi}^{b}$.

16:Do a breadth first search using $Q$ as the initial value to mark all
vertices in the same component of every $x\in V_{\pi}^{b}$.

17:if there exists an $u\in V_{\pi}^{w}$, which is not marked then return NO.

18:end if

19:return YES.

Running time of Algorithm 2: Let us analyze the time complexity of Algorithm
2. Verifying whether $\mathcal{A}[\pi]=\mathcal{A}[\tau]$ can be done in
$O(n^{2})$ time. It takes $O(n^{2})$ time to build an bijection between
$\mathcal{A}[\pi]$ and $\mathcal{A}[\tau]$, and construct the cycle graph
$ACG(\pi,\tau,f)$, as well as the corresponding intersection graph
$IG(\pi,\tau,f)$. It remains to analyze the size of $IG(\pi,\tau,f)$. For each
repeat, say $x$, there are $dp[x,\pi]$ original vertices and $c[x]-1$
additional vertices in $IG[\pi]$, where $c[x]$ is the number of cycles of $x$
in $ACG(\pi,\tau,f]$. Note that $c[x]\leq dp[x,\pi]$ and
$\sum_{x\in\sum}dp[x,\pi]=n$. Thus, the total number of vertices in
$IG(\pi,\tau,f)$ is bounded by $\sum_{x\in\sum}(dp[x,\pi]+c[x]-1)\leq
2\sum_{x\in\sum}dp[x,\pi]-1=2n-1$, then the number of edges in $IG[\pi]$ is at
most $4n^{2}$. The whole breadth-search process takes $O(n^{2})$ time, since
there are at most $2n-1$ vertices and at most $4n^{2}$ edges in
$IG(\pi,\tau,f)$. Therefore, Algorithm 2 runs in $O(n^{2})$ time.

##  6 Hardness Result for SMSR

In this section, we show that the optimization problem _SMSR_ is NP-hard. When
we initially investigated SMSR on the special case when the input genomes have
duplication number 2, we found that it is somehow related to searching a
Steiner set on the intersection graph, which is a type of circle graph with
its vertices colored and weighted. We review the definitions on circle graphs
as follows.

###### Definition 6.1

A graph is a _circle graph_ if it is the intersection graph of chords in a
circle.

###### Definition 6.2

A graph is an _overlap graph_ , if each vertex corresponds to an interval on
the real line, and there is an edge between two vertices if and only if their
corresponding intervals intersect but one does not contain the other.

The graph class of overlap graphs is equivalent to circle graphs if we join
the two endpoints of the real line into a circle. Circle graph can be
recognized in polynomial time [GHS89].

###### Definition 6.3

Minimum Steiner Tree Problem:

Instance: A connected graph $G$, a non-empty subset $X\subseteq V(G)$, called
terminal set.

Task: Find a minimum size subset $S\subseteq V(G)\backslash X$ such that the
induced subgraph $G[S\cup X]$ is connected.

More than thirty five years ago, Johnson stated that the _Minimum Steiner
Tree_ problem on _Circle Graphs_ was in $P$ [Joh85] and referred to a personal
communication as a reference. However, to date, there is no published
polynomial algorithm to solve the problem. Figueiredo et al. revisited
Johnson’s table recently, and although they still marked the problem as in
$P$, the reference remains “ongoing” [FMS22]. Here as a by-product, we clarify
that the _Minimum Steiner Tree_ problem on _Circle Graphs_ is NP-hard. The
reduction is from _MAX-(3,B2)-SAT_ , in which each clause is of size exactly 3
and each variable occurs exactly twice in its positive and twice in the
negative form.

###### Theorem 6.1

_MAX-(3,B2)-SAT_ is NP-hard _[BKS03]_.

Next, we conduct a reduction from _MAX-(3,B2)-SAT_ to the _Minimum Steiner
Tree_ problem on _Circle Graphs_.

###### Theorem 6.2

The _Minimum Steiner Tree_ problem on _Circle Graphs_ is NP-hard.

_Proof._ Given an instance of _MAX-(3,B2)-SAT_ with $n$ variables
$\\{x_{1},x_{2},...,x_{n}\\}$ and $m$ clauses $\\{c_{1},c_{2},...,c_{m}\\}$,
we construct a _circle graph_ denoted by $OLG(3,B2)$ as follows.

  * •

_Variable Intervals_. For each variable $x_{i}$, let $q_{i}=300(i-1)$.
Construct four group of ladder intervals, where
$B[i]_{a}^{b}=[q_{i}+50(a-1)+4(b-1)+1,q_{i}+50(a-1)+4(b-1)+7]$, for
$a=1,2,3,4$ and $b=1,2,3,4,5,6$. Let $b[i]=\\{B[i]_{a}^{b}|a=1,2,3,4$, and
$b=2,5\\}$, and $B[i]=\\{B[i]_{a}^{b}|a=1,2,3,4$, and $b=1,3,4,6\\}$. Then
construct four intervals: $P[i]_{1}=[q_{i}+12,q_{i}+125]$, which intersects
with both $B[i]_{1}^{3}$ and $B[i]_{3}^{6}$; $P[i]_{2}=[q_{i}+62,q_{i}+175]$,
which intersects with both $B[i]_{2}^{3}$ and $B[i]_{4}^{6}$;
$N[i]_{1}=[q_{i}+3,q_{i}+53]$, which intersects with both $B[i]_{1}^{1}$ and
$B[i]_{2}^{1}$; and $N[i]_{2}=[q_{i}+116,q_{i}+166]$, which intersects with
both $B[i]_{3}^{4}$ and $B[i]_{4}^{4}$. Let $P[i]=\\{P[i]_{1},P[i]_{2}\\}$,
and $N[i]=\\{N[i]_{1},N[i]_{2}\\}$.

  * •

_Clause Intervals_. For each clause $c_{a}$ ($1\leq a\leq m$), construct an
interval $c_{a}=[300n+3an,300n+3an+2n+1]$. We still use
$\mathbb{C}=\\{c_{1},c_{2},\dots,c_{m}\\}$ to denote the set of intervals
constructed by the clauses.

  * •

_Positive Literal Intervals_. If $x_{i}$ appears in $c_{j}$ and $c_{k}$($j<k$)
as positive literals, construct two intervals $f[i]^{j}=[q_{i}+200,q_{i}+210]$
and $f[i]^{k}=[q_{i}+220,q_{i}+230]$, which are independent with all the
previous intervals; and construct $G[i]^{j}=[q_{i}+209,300n+3jn+i]$, which
intersects with $f[i]^{j}$ and $c_{j}$; $G[i]^{k}=[q_{i}+229,300n+3kn+i]$,
which intersects with $f[i]^{k}$ and $c_{k}$. Construct
$D[i]^{j}=[q_{i}+25,q_{i}+201]$, which intersects with $f[i]^{j}$ and
$B[i]_{1}^{6}$, and $D[i]^{k}=[q_{i}+75,q_{i}+221]$, which intersects with
$f[i]^{k}$ and $B[i]_{2}^{6}$.

  * •

_Negative Literal Intervals_. If $x_{i}$ appears in $c_{j^{\prime}}$ and
$c_{k^{\prime}}$($j^{\prime}<k^{\prime}$) as negative literals, construct two
intervals $f[i]^{j^{\prime}}=[q_{i}+240,q_{i}+250]$ and
$f[i]^{k^{\prime}}=[q_{i}+260,q_{i}+270]$, which are independent with all the
previous intervals; and construct
$G[i]^{j^{\prime}}=[q_{i}+249,300n+3j^{\prime}n+i]$, which intersects with
$f[i]^{j^{\prime}}$ and $c_{j^{\prime}}$, and
$G[i]^{k^{\prime}}=[q_{i}+269,300n+3k^{\prime}n+i]$, which intersects with
$f[i]^{k^{\prime}}$ and $c_{k^{\prime}}$. Construct
$D[i]^{j^{\prime}}=[q_{i}+103,q_{i}+241]$, which intersects with
$f[i]^{j^{\prime}}$ and $B[i]_{1}^{6}$, and
$D[i]^{k^{\prime}}=[q_{i}+153,q_{i}+261]$, which intersects with
$f[i]^{k^{\prime}}$ and $B[i]_{2}^{6}$. Let
$f[i]=\\{f[i]^{j},f[i]^{k},f[i]^{j^{\prime}},f[i]^{k^{\prime}}\\}$ and let
$D[i]=\\{D[i]^{j},D[i]^{k},D[i]^{j^{\prime}},D[i]^{k^{\prime}}\\}$.

  * •

_Subtree Intervals_. For each variable $x_{i}$, construct four intervals
$t[i]=\\{t[i]_{1},t[i]_{2},t[i]_{3},t[i]_{4}\\}$, where
$t[i]_{a}=[-(4i+a)+4,q_{i}+50a-1]$ for $a=1,2,3,4$. Finally, construct two
intervals $r=\\{r_{1}=[-4n-1,301n],r_{2}=[-4n-2,0]\\}$.

Let $b=\cup_{1}^{n}b[i]$, $f=\cup_{1}^{n}f[i]$, $t=\cup_{1}^{n}t[i]$,
$\mathbb{B}=\cup_{1}^{n}B[i]$, $\mathbb{P}=\cup_{1}^{n}P[i]$,
$\mathbb{N}=\cup_{1}^{n}N[i]$, $\mathbb{D}=\cup_{1}^{n}D[i]$,
$\mathbb{G}=\cup_{1}^{n}G[i]$, $t\cup_{1}^{n}t[i]$. Let $OLG(3,B2)$ be the
corresponding circle graph of all the constructed intervals, define the input
terminal set of the _Steiner Tree Problem_ as the vertices corresponding to
intervals in $b\cup f\cup c\cup t\cup r$, and the vertices corresponding to
the intervals in
$\mathbb{B}\cup\mathbb{P}\cup\mathbb{N}\cup\mathbb{D}\cup\mathbb{G}$ are
candidate Steiner vertices.

It is not hard to observe that the vertices corresponding to the intervals in
$t\cup r$ have already formed a subtree, and all the candidate Steiner
vertices are connect to this subtree, thus it does not matter whether they are
connected themselves or not. The terminal vertices corresponding to the
intervals in $b\cup f\cup c$ are mutually independent, then they must connect
to the subtree through Steiner vertices.

We show that the _MAX-(3,B2)-SAT_ instance is satisfiable if and only if the
_minimum Steiner tree_ problem on $OLG(3,B2)$ has an optimum solution of $14n$
vertices.

For each variable $x_{i}$, assume that $c_{j}$ and $c_{k}$ are the two clauses
where $x_{i}$ appears as positive literals, and $c_{j^{\prime}}$ and
$c_{k^{\prime}}$ are the two clauses where $x_{i}$ appears as negative
literals.

($\Rightarrow$) Assume that there is a truth assignment to the
_MAX-(3,B2)-SAT_ instance, we can obtain a solution of $14n$ intervals for the
_Minimum Steiner Tree_ problem as follows.

If $x_{i}$ is assigned true, by selecting the 6 vertices corresponding to
intervals $\\{P[i]_{1}$, $P[i]_{2}$, $D[i]_{j^{\prime}}$, $D[i]_{k^{\prime}}$,
$G[i]_{j}$, $G[i]_{k}\\}$, and 8 vertices corresponding to the ladder
intervals $\\{B[i]_{1}^{3}$, $B[i]_{2}^{3}$, $B[i]_{3}^{6}$, $B[i]_{4}^{6}$,
$B[i]_{1}^{4}$, $B[i]_{2}^{4}$, $B[i]_{3}^{1}$, $B[i]_{4}^{1}\\}$, all the 12
terminals vertices corresponding interval in $b\cup f$, as well as the
terminals corresponding to $c_{j}$ and $c_{k}$ will connect to the subtree.

If $x_{i}$ is assigned false, by selecting the 6 vertices corresponding to
intervals $\\{N[i]_{1}$, $N[i]_{2}$, $D[i]_{j}$, $D[i]_{k}$,
$G[i]_{j^{\prime}}$, $G[i]_{k^{\prime}}\\}$, and 8 vertices corresponding to
the ladder intervals $\\{B[i]_{1}^{1}$, $B[i]_{2}^{1}$, $B[i]_{3}^{4}$,
$B[i]_{4}^{4}$, $B[i]_{1}^{6}$, $B[i]_{2}^{6}$, $B[i]_{3}^{3}$,
$B[i]_{4}^{3}\\}$, all the 12 terminals vertices corresponding interval in
$b\cup f$, as well as the terminals corresponding to $c_{j^{\prime}}$ and
$c_{k^{\prime}}$ will connect to the subtree. Therefore, we obtain a Steiner
set of size $14n$.

($\Leftarrow$) Assume that the _Minimum Steiner Tree_ problem on $OLG(3,B2)$
has a Steiner set of $14n$ vertices, we show that there is a truth assignment
to the _MAX-(3,B2)-SAT_ instance.

Firstly, for each variable $x_{i}$, we have, constraint (I): in order to
connect the 8 vertices corresponding to intervals in $b[i]$ to the subtree,
the Steiner set includes at least 8 vertices corresponding to intervals in
$B[i]$; and constraint (II): in order to connect the 4 vertices corresponding
to intervals in $f[i]$ to the subtree, the Steiner set must include at least 4
vertices corresponding to intervals in $D[i]\cup G[i]$. But any 12 vertices
satisfying the above constraints are not enough, because the four terminals
corresponding to the intervals in
$\\{B[i]_{1}^{2},B[i]_{2}^{2},B[i]_{3}^{5},B[i]_{4}^{5}\\}$ are still not
connected to the subtree. For each of them, say $B[i]_{1}^{2}$ for an example,
if it must be connected to the subtree through $B[i]_{1}^{3}$ and $P[i]_{1}$,
$B[i]_{1}^{1}$ and $N[i]_{1}$, or $B[i]_{1}^{3}$ and $B[i]_{1}^{4}$. If it
chooses $B[i]_{1}^{3}$ and $B[i]_{1}^{4}$, then the terminal corresponding to
$B[i]_{1}^{5}$ has to connect to the subtree through $B[i]_{1}^{6}$ and
$D[i]^{j}$, this implies both neighbors of the vertex corresponding to
$B[i]_{1}^{5}$ are selected in the Steiner set. Similar argument holds for
each of $\\{B[i]_{1}^{2},B[i]_{2}^{2},B[i]_{3}^{5},B[i]_{4}^{5}\\}$. Thus, to
connect the four terminals corresponding to the intervals in
$\\{B[i]_{1}^{2},B[i]_{2}^{2},B[i]_{3}^{5},B[i]_{4}^{5}\\}$ to the subtree,
besides a neighbor of each vertex, each of them also needs an additional
vertex, though two of them may share an additional vertex. Hence the Steiner
set must include at least another two vertices, which should either be
$P[i]_{1}$ and $P[i]_{2}$, or $N[i]_{1}$ and $N[i]_{2}$. Therefore, since the
Steiner set is of size $14n$, for each variable $x_{i}$($1\leq i\leq n$), it
includes exactly 14 vertices corresponding to intervals in $B[i]\cup P[i]\cup
N[i]\cup D[i]\cup G[i]$; moreover, either the vertices corresponds to
intervals of $P[i]$ or the vertices corresponds to intervals of $N[i]$ are
selected.

If the Steiner set includes $P[i]_{1}$ and $P[i]_{2}$, to connect the two
vertices corresponding to $B[i]_{3}^{2}$ and $B[i]_{4}^{2}$ to the subtree, it
also includes $D[i]^{j^{\prime}}$ and $D[i]^{k^{\prime}}$, then to connect the
two vertices corresponding to $f[i]^{j}$ and $f[i]^{k}$, the Steiner set could
contains one of $D[i]^{j}$ and $G[i]^{j}$, and one of $D[i]^{k}$ and
$G[i]^{k}$, we can revise the Steiner set such that it includes $G[i]^{j}$ and
$G[i]^{k}$; subsequently, the vertices corresponding to the intervals $c_{j}$
and $c_{k}$ are connected to the subtree. In this case, we assign $x_{i}$ true
to satisfy $c_{j}$ and $c_{k}$.

If the Steiner set contains $N[i]_{1}$ and $N[i]_{2}$, to connect the two
vertices corresponding to $B[i]_{1}^{5}$ and $B[i]_{2}^{5}$ to the subtree, it
also contains $D[i]^{j}$ and $D[i]^{k}$, then to connect the two vertices
corresponding to $f[i]^{j^{\prime}}$ and $f[i]^{k^{\prime}}$, the Steiner set
could contain one of $D[i]^{j^{\prime}}$ and $G[i]^{j^{\prime}}$, and one of
$D[i]^{k^{\prime}}$ and $G[i]^{k^{\prime}}$. Hence we can revise the Steiner
set such that it contains $G[i]^{j^{\prime}}$ and $G[i]^{k^{\prime}}$,
subsequently, the vertices corresponding to the intervals $c_{j^{\prime}}$ and
$c_{k^{\prime}}$ are connected to the subtree. In this case, we assign $x_{i}$
false to satisfy $c_{j^{\prime}}$ and $c_{k^{\prime}}$. $\sqcap$$\sqcup$

We take as instance of _MAX-(3,B2)-SAT_ as an example, where
$\\{x_{1},x_{2},x_{3}\\}$ is the set of the variables and
$\\{c_{1}=\\{x_{1},x_{2},x_{3}\\},c_{2}=\\{x_{1},\bar{x}_{2},\bar{x}_{3}\\},c_{3}=\\{\bar{x}_{1},\bar{x}_{2},x_{3}\\}$,
$c_{4}=\\{\bar{x}_{1},x_{2},\bar{x}_{3}\\}\\}$ is the set of clauses. The
constructed instance and the corresponding circle graph are in Fig. 10 and
Fig. 11 respectively.

Figure 10: The intervals base on $x_{1}$. Intervals corresponding to terminal
vertices are red, and intervals corresponding to Steiner vertices are colored
black. Figure 11: The corresponding circle graph according to the intervals in
Figure 10.

Finally, we conduct a reduction from the Minimum Steiner Tree problem on
circle graphs to the SMSR problem even if the duplication number of the
converted chromosomes is 2.

###### Lemma 6.1

Given two related simple chromosomes $\pi$ and $\tau$, both have a duplication
number 2, let $f$ be the unique bijection between $\mathcal{A}[\pi]$ and
$\mathcal{A}[\tau]$. $ACG(\pi,\tau,f)$ is composed of 1-cycles and 2-cycles,
and each appearance of an even repeat corresponds to a 1-cycle, and the two
appearances of every odd repeat corresponds to a 2-cycle.

_Proof._ Since the duplication number of $\pi$ and $\tau$ is 2, from Lemma
5.1, each cycle of $ACG(\pi,\tau,f)$ contains at most 2 red edges.

Let $x$ be an even repeat and $x_{i}$, $x_{j}$ be its two occurrences in
$\pi$. Since $x$ is neighbor-consistent, there must be two occurrences of $x$,
say $y_{k}$ and $y_{l}$ in $\tau$ such that $\langle
r(x_{i-1}),l(x_{i})\rangle$ and $\langle r(x_{i}),l(x_{i+1})\rangle$ are
matched to $\langle r(x_{k-1}),l(x_{k})\rangle$ and $\langle
r(x_{k}),l(x_{k+1})\rangle$, and $\langle r(x_{j-1}),l(x_{j})\rangle$ and
$\langle r(x_{j}),l(x_{j+1})\rangle$ are matched to $\langle
r(x_{l-1}),l(x_{l})\rangle$ and $\langle r(x_{l}),l(x_{l+1})\rangle$ in the
bijection $f$. From the construction of $ACG(\pi,\tau,f)$, $l(x_{i})$ and
$r(x_{i})$ are connected by a blue edge, and $l(x_{j})$ and $r(x_{j})$ are
connected by a blue edge, which implies that $x_{i}$ and $x_{j}$ correspond to
1-cycles respectively.

Let $x$ be an odd repeat and $x_{i}$, $x_{j}$ be its two appearances in $\pi$.
Since $x$ is neighbor-inconsistent, there must be two occurrences of $x$, say
$y_{k}$ and $y_{l}$ in $\tau$ such that $\langle r(x_{i-1}),l(x_{i})\rangle$
is matched to an adjacency involving $y_{k}$ while $\langle
r(x_{i}),l(x_{i+1})\rangle$ is matched to an adjacency involving $y_{l}$, thus
$l(x_{i})$ and $r(x_{i})$ are not connected by a blue edge, which implies that
$x_{i}$ and $x_{j}$ are in a 2-cycle. $\sqcap$$\sqcup$

###### Theorem 6.3

The SMSR problem is NP-hard even if the input genomes have duplication number
2.

_Proof._ Given a circle graph $G=(V,E)$, where $X\subseteq V$ is the set of
terminal vertices, for each vertex $v\in V$, let $[l(v),r(v)]$ be its
corresponding interval on the real line. Assume that $l(v_{min})$ is the
minimum and $r(v_{max})$ is the maximum.

We first construct two 1-cycles: $(l(v_{min})-1-\delta,l(v_{min})-1+\delta)$,
which corresponds to “+0”; and $(r(v_{max})+1-\delta,r(v_{max})+1+\delta)$,
which corresponds to “-0”.

For each terminal vertex $t\in X$, we construct two intersecting non-opposite
2-cycles: one is
$(l(t)-\delta,l(t)+\delta,r(t)-\delta,r(t)+\delta,l(t)-\delta)$, where
$(l(t)-\delta$, $l(t)+\delta)$ and $(r(t)-\delta$, $r(t)+\delta)$ are red
edges and $(l(t)-\delta$, $r(t)+\delta)$ and $(l(t)+\delta$, $r(t)-\delta)$
are blue edges. Let $t_{1}$ be the repeat corresponding to this cycle, the two
occurrences both have a “+”sign in $\pi$; the other is
$(r(t)-3\delta,r(t)-2\delta,r(t)+2\delta,r(t)+3\delta,r(t)-3\delta)$, where
$(r(t)-3\delta$, $r(t)-2\delta)$ and $(r(t)+2\delta$, $r(t)+3\delta)$ are red
edges and $(r(t)-3\delta$, $r(t)+3\delta)$ and $(r(t)-2\delta$,
$r(t)+2\delta)$ are blue edges. Let $t_{2}$ be the repeat corresponding to
this cycle, the two occurrences both have a “+”sign in $\pi$. Then, we denote
$l(t)-\delta$ and $r(t)-\delta$ by $t_{1}^{h}$, $l(t)+\delta$ and
$r(t)+\delta$ by $t_{1}^{t}$, $r(t)-3\delta$ and $r(t)+2\delta$ by
$t_{2}^{h}$, $r(t)-2\delta$ and $r(t)+3\delta$ by $t_{2}^{t}$.

Choose an arbitrary terminal vertex $x\in X$, we construct an opposite
2-cycle: $(r(x)-5\delta,r(x)-4\delta,r(x)+5\delta,r(x)+4\delta,r(x)-5\delta)$,
where $(r(x)-5\delta$, $r(x)-4\delta)$ and $(r(x)+4\delta$, $r(x)+5\delta)$
are red edges and $(r(x)-5\delta$, $r(x)+4\delta)$ and $(r(x)-4\delta$,
$r(x)+5\delta)$ are blue edges. Let $x_{3}$ be the repeat corresponding to
this cycle, the occurrence corresponding to the red edge
$(r(x)-5\delta,r(x)-4\delta)$ has a “+” sign, and the occurrence corresponding
to the red edge $(r(x)+4\delta,r(x)+5\delta)$ has a “-” sign in $\pi$. Then,
we denote $r(x)-5\delta$ and $r(x)+\delta$ by $x_{3}^{h}$, $r(x)-4\delta$ and
$r(x)+4\delta$ by $x_{3}^{t}$.

For each candidate Steiner vertex $s$, we construct two 1-cycles
$(l(s)-\delta,l(s)+\delta)$, $r(s)-\delta,r(s)+\delta)$. Let $s_{1}$ be the
repeat corresponding to this cycle, the two occurrences both have a “+” sign
in $\pi$. Then, we denote $l(s)-\delta$ and $r(s)-\delta$ by $s_{1}^{h}$,
$l(s)+\delta$ and $r(s)+\delta$ by $s_{1}^{t}$.

Let the graph constructed above be denoted by $ACG(G,X)$, Next, we show that
$ACG(G,X)$ is a well-defined alternative-cycle graph, i.e., there exist two
related simple chromosomes $\pi$ and $\tau$ with
$\mathcal{A}[\pi]=\mathcal{A}[\tau]$ (then there is a bijection $f$), such
that $ACG(\pi,\tau,f)=ACG(G,X)$.

In $ACG(G,X)$, each red edge corresponds to an occurrence of a repeat, thus
clearly the chromosome $\pi$ is a sequence of the occurrences. Then we can
view the blanks between red edges as adjacencies. From the above construction,
each blue edge connects in the cycles corresponding to $v_{i}$, then connects
node $v_{i}^{h}$ with node $v_{i}^{t}$, thus an blue edge will correspond to
an occurrence of $v_{i}$ in $\tau$. Therefore, from Lemma 5.2, it is
sufficient to show that all the blanks and blue edges form a path.

Sorting the vertices of $V$ in an increasing order of $l(v)$, then $ACG(G,X)$
is obtained by adding a 1-cycle, two intersecting non-opposite 2-cycles, and
an opposite 2-cycle iteratively. We prove that the blanks and blue edges from
a path inductively. Initially, the two blue edges of the cycles
$(0^{h},0^{t})$ and $(0^{t},0^{h})$ surely form a path. Assume that we have a
path $\mathbb{P}$ of blanks and blue edges,
$\mathbb{P}=(0^{h},n_{1},\dots,n_{k},0^{h})$.

(1) in case that a 1-cycle $(s_{1}^{h},s_{1}^{t})$ is added in between the
blank of $n_{i}$ and $n_{j}$, if $j=i+1$, then
$\mathbb{P}^{\prime}=(0^{h},\dots,n_{i},s_{1}^{h},s_{1}^{t},n_{j},\dots,n_{k})$
is a path; if $j=i-1$, then
$\mathbb{P}^{\prime}=(n_{0},\dots,n_{j},s_{1}^{t},s_{1}^{h},n_{i},\dots,n_{k},0^{h})$
is also a path.

(2) in case that two intersecting non-opposite 2-cycles
$(t_{1}^{h},t_{1}^{t},t_{1}^{h},t_{1}^{t},t_{1}^{h})$ and
$(t_{2}^{h},t_{2}^{t},t_{2}^{h},t_{2}^{t},t_{2}^{h})$ are added in between the
two blanks of $n_{i}$, $n_{j}$ and $n_{i^{\prime}}$, $n_{j^{\prime}}$. We just
show the case that $i+1=j<i^{\prime}=j^{\prime}-1$, since all other cases are
similar. $\mathbb{P}^{\prime}=(0^{h},\dots$, $n_{i}$, $t_{1}^{h}$,
$t_{1}^{t}$, $t_{2}^{h}$, $t_{2}^{t}$, $t_{1}^{h}$, $t_{1}^{t}$, $n_{j}$,
$\dots$, $n_{i^{\prime}}$, $t_{2}^{h}$, $t_{2}^{t}$, $n_{j^{\prime}}$,
$\dots$, $n_{k},0^{h})$ is also a path. Specially, if two intersecting non-
opposite 2-cycles are added in between one blank, the new path can be obtained
by deleting the segment $(n_{j}$, $\dots$, $n_{i^{\prime}})$ from
$\mathbb{P}^{\prime}$.

(3) in case that an opposite 2-cycle
$(x_{3}^{h},x_{3}^{t},x_{3}^{h},x_{3}^{t},x_{3}^{h})$ is added in between the
two blanks of $n_{i}$, $n_{j}$ and $n_{i^{\prime}}$, $n_{j^{\prime}}$. We just
show the case that $i+1=j<i^{\prime}=j^{\prime}-1$, since all other cases are
similar.
$\mathbb{P}^{\prime}=(0^{h},\dots,n_{i},x_{3}^{h},x_{3}^{t},n_{i^{\prime}},$
$\dots,n_{j},x_{3}^{t},x_{3}^{h},n_{j^{\prime}},\dots,n_{k},0^{h})$ is also a
path.

Therefore, in $ACG(G,X)$, all the blanks and blue edges form a path. We can
obtain $\tau$ along this path, if the path goes through a blue edge from
$v_{a}^{h}$ to $v_{a}^{t}$, then it has a “+”sign in $\tau$; and if the path
goes through a blue edge from $v_{a}^{t}$ to $v_{a}^{h}$, then it has a “-”
sign in $\tau$. Since the blanks represents adjacencies in both $\pi$ and
$\tau$, then $\mathcal{A}[\pi]=\mathcal{A}[\tau]$. To make $\pi$ and $\tau$,
we insert distinct genes between every adjacency.

Finally, we complete the proof by showing that $G$ has a Steiner set of size
$k$ if and only if $\pi$ can be transformed into $\tau$ by $2|X|+2k+1$
symmetric reversals.

($\Rightarrow$) Assume that $G$ has a Steiner set $S$ of size $k$, which
implies that the $G(X\cup S)$ forms a tree, thus, in the intersection graph
$IG(\pi,\tau)$, the repeats corresponds to $X\cup S$ are in a single connected
component, which contains a black vertex $x_{3}$. From our construction, there
are also two odd vertices corresponding to each vertex of $X$, and one even
vertex corresponding to each vertex of $S$, thus $\pi$ can be transformed into
$\tau$ by $2|X|+2k+1$ symmetric reversals.

($\Leftarrow$) Assume that $\pi$ can be transformed into $\tau$ by $2|X|+2k+1$
symmetric reversals. Since there are $2|X|+1$ odd vertices in the intersection
graph $IG(\pi,\tau)$, but only one black vertices, then the solution must
perform at least $2|X|+1$ symmetric reversals on these odd vertices, and at
most $2k$ symmetric reversals on $k$ even vertices. A symmetric reversal on a
vertex is applicable if and only if the vertex is in a connected component
that contains black vertices. Thus, the $2|X|+1$ odd vertices and $k$ even
vertices are in a connected component, which implies that $G$ has a Steiner
set of size $k$. $\sqcap$$\sqcup$

We give an example of the above reduction in Figure 12.

Figure 12: $(a)$. A circle graph $G$, where $X=\\{x,y,z\\}$ is the set of
terminals. $(b)$. The corresponding intervals of $G$. $(c)$. The constructed
alternative-cycle graph $ACG(G,X)$, and $\pi=[+0$,
$+x_{1},+y_{1},+u_{1},+x_{2},+x_{1},+x_{2},+w_{1}$,
$+y_{2},+y_{1},+y_{2},+v_{1},+u_{1},+z_{1},+v_{1},+w_{1},+z_{3},+z_{2},+z_{1},+z_{2},-z_{3},-0]$,
$\tau=[+0$,
$+x_{1},+x_{2},+x_{1},+y_{1},+y_{2},+y_{1},+u_{1},+x_{2},+w_{1},+y_{2},+v_{1},+u_{1},+z_{1},+z_{2},+z_{1},+v_{1},\\\
+w_{1},+z_{3},-z_{2},-z_{3},-0]$.

##  7 Concluding Remarks

This paper investigates a new model of genome rearrangements named sorting by
symmetric reversals. This model is based on recent new findings from genome
comparison. The decision problem, which asks whether a chromosome can be
transformed into another by symmetric reversals, is polynomial solvable. But
the optimization problem, which pursues the minimum number of symmetric
reversals during the transformation between two chromosomes, is NP-hard. It is
interesting to design some approximation algorithms for the optimization
problem. Perhaps, polynomial time algorithms to solve the optimization problem
for more realistic special cases are also interesting.

## Acknowledgments

This research is supported by NSF of China under grant 61872427 and 61732009.

## References

  * [APC03] L. Armengol, M.A. Pujana, J. Cheung, S.W. Scherer, and X. Estivill.  Enrichment of segmental duplications in regions of breaks of synteny between the human and mouse genomes suggest their involvement in evolutionary rearrangements.  _Human Molecular Genetics_ , 12(17):2201-2208, 2003.
  * [BBK04] J.A. Bailey, R. Baertsch, W.J. Kent, D. Haussler, and E.E. Eichler.  Hotspots of mammalian chromosomal evolution.  _Genome Biology_ , 5(4):R23, 2004.
  * [BHK02] P. Berman, S. Hannenhalli, and M. Karpinski.  1.375-approximation algorithm for sorting by reversals.  Proc. the 10th European Symposium on Algorithms (ESA’02), pp. 200–210, 2002.
  * [BK99] P. Berman and M. Karpinski.  On some tighter inapproximability results (extended abstract).  Proc. the 26th International Colloquium on Automata, Languages and Programming (ICALP’99), pp. 200–209, 1999.
  * [BKS03] P. Berman, M. Karpinski, and A.D. Scott.  Approximation Hardness of Short Symmetric Instances of MAX-3SAT.  _Electronic Colloquium on Computational Complexity_ , Report No. 49, 2003.
  * [BMD05] J.L. Bennetzen, J. Ma, and K.M. Devos.  Mechanisms of recent genome size variation in flowering plants.  _Annals of Botany_ , 95:127–32, 2005.
  * [Cap99] A. Caprara.  Sorting Permutations by Reversals and Eulerian Cycle Decompositions.  _SIAM J. Discrete Mathematics_ , 12(1):91–110, 1999.
  * [Chr98] D.A. Christie.  A 3/2-Approximation Algorithm for Sorting by Reversals.  Proc. the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’98), pp. 244–252, 1998.
  * [FLR09] G. Fertin, A. Labarre, I. Rusu, S. Vialette, and E. Tannier.  _Combinatorics of genome rearrangements_.  MIT press, 2009.
  * [FMS22] C.M.H. de Figueiredo, A.A. de Melo, D. Sasaki, and A. Silva.  Revising Johnson’s table for the 21st century.  _Discrete Applied Mathematics_ , 323:284-300, 2022.
  * [GHS89] C.P. Gabor, W.L. Hsu, and K.J. Supowit.  Recognizing circle graphs in polynomial time.  _J. ACM_ , 36:435–474, 1989.
  * [HP99] S. Hannenhalli and P. Pevzner.  Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals.  _J. ACM_ , 46(1):1–27, 1999.
  * [HP94] S.B. Hoot and J.D. Palmer.  Structural rearrangements, including parallel inversions within the choroplast genome of anemone and related genera.  _Journal of Molecular Evolution_ , 38: 274–281, 1994.
  * [Joh85] D.S. Johnson.  The NP-Completeness Column: an Ongoing Guide.  _Journal of Algorithms_ , 6:434–451, 1985.
  * [KST00] H. Kaplan, R. Shamir, and R.E. Tarjan.  A faster and simpler algorithm for sorting signed permutations by reversals.  _SIAM Journal on Computing_ , 29(3):880–892, 2000.
  * [KS95] J. Kececioglu and D. Sankoff.  Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement.  _Algorithmica_ , 13(1):180–210, 1995.
  * [LCG09] M.S. Longo, D.M. Carone, E.D. Green, M.L. O’Neill, and R.J. O’Neill.  Distinct retroelement classes define evolutionary breakpoints demarcating sites of evolutionary novelty.  _BMC Genomics_ , 10(1):334, 2009.
  * [OCM92] P. C. Orban, D. Chui, J.D. Marth.  Tissue– and site–specific recombination in transgenic mice.  _Proc. Nat. Acad. Sci. USA_ , 89(15): 6861–6865, 1992.
  * [PH86] J.D. Palmer and L.A. Herbon.  Tricicular mitochondrial genomes of brassica and raphanus:reversal of repeat configurations by inversion.  _Nucleic Acids Research_ , 14: 9755–9764, 1986.
  * [PT03] P. Pevzner and Glenn Tesler.  Human and mouse genomic sequences reveal extensive breakpoint reuse in mammalian evolution,  _Proc. Nat. Acad. Sci. USA_ , 100(13): 7672-7677, 2003.
  * [San09] D. Sankoff.  The where and wherefore of evolutionary breakpoints.  _J. Biology_ , 8:66, 2009.
  * [SLA92] D. Sankoff, G. Leduc, N. Antoine, B. Paquin, B. F. Lang, and R. Cedergran.  Gene order comparisons for phylogenetic interferce: Evolution of the mitochondrial genome.  _Proc. Nat. Acad. Sci. USA_ , 89: 6575–6579, 1992.
  * [Sau87] B. Sauer.  Functional expression of the Cre-Lox site-specific recombination system in the yeast Saccharomyces cerevisiae.  _Mol Cell Biol._ , 7(6): 2087–2096, 1987.
  * [SH88] B. Sauer and N. Henderson.  Site-specific DNA recombination in mammalian cells by the Cre recombinase of bacteriophage P1.  _Proc. Nat. Acad. Sci. USA_ , 85(14): 5166–5170, 1988.
  * [SIW97] K. Small, J. Iber, and S.T. Warren.  Emerin deletion reveals a common X-chromosome inversion mediated by inverted repeats.  _Nature Genetics_ , 16:96–99, 1997.
  * [TBS07] E. Tannier, A. Bergeron, and M-F. Sagot.  Advances on sorting by reversals.  _Discrete Applied Mathematics_ , 155(6-7):881–888, 2007.
  * [TVO11] A. Thomas, J-S. Varr, and A. Ouangraoua.  Genome dedoubling by DCJ and reversal.  _BMC Bioinformatics_ , 12(9):S20, 2011.
  * [WW18] D. Wang and L. Wang.  GRSR: a tool for deriving genome rearrangement scenarios from multiple unichromosomal genome sequences.  _BMC Bioinformatics_ , 19(9):11–19, 2018.
  * [WLG17] D. Wang, S. Li, F. Guo, and L. Wang.  Core genome scaffold comparison reveals the prevalence that inversion events are associated with pairs of inverted repeats.  _BMC Genomics_ , 18:268, 2017.
  * [WEH82] G.A. Watterson, W.J. Ewens, T.E. Hall, and A. Morgan.  The chromosome inversion problem.  _Journal of Theoretical Biology_ , 99(1):1–7, 1982.
  * [WPR19] A.M. Wenger, P. Peluso, W.J. Rowell, P.C. Chang, and M.W. Hunkapiller.  Accurate circular consensus long-read sequencing improves variant detection and assembly of a human genome.  _Nature Biotechnology_ , 37(11):1155-1162, 2019.