A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals.
We give a quadratic time algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation by Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.
Introduction
. In this paper we study the problem of sorting signed permutations
by reversals. A signed permutation is a permutation on the
integers each number is also assigned a sign of plus or minus. A
reversal, (i; j), on  transforms  to
The minimum number of reversals needed to transform one permutation to another
is called the reversal distance between them. The problem of sorting signed permutations
by reversals is to nd, for a given signed permutation , a sequence of reversals
of minimum length that transforms  to the identity permutation (+1;
The motivation to studying the problem arises in molecular biology: Concurrent
with the fast progress of the Human Genome Project, genetic and DNA data on many
model organisms is accumulating rapidly, and consequently the ability to compare
genomes of dierent species has grown dramatically. One of the best ways of checking
similarity between genomes on a large scale is to compare the order of appearance
of identical genes in the two species. In the Thirties, Dobzhansky and Sturtevant [7]
had already studied the notion of inversions in chromosomes of drosophila. In the
late Eighties, Jerey Palmer demonstrated that dierent species may have essentially
the same genes, but the gene orders may dier between species. Taking an abstract
perspective, the genes along a chromosome can be thought of as points along a line.
Numbers identify the particular genes; and, as genes have directionality, signs correspond
to their direction. Palmer and others have shown that the dierence in order
may be explained by a small number of reversals [17, 18, 19, 20, 12]. These reversals
correspond to evolutionary changes during the history of the two genomes, so the numA
preliminary version of this paper was presented at the Eighth ACM-SIAM Symposium on
Discrete Algorithms [13].
y AT&T-labs research, 180 Park Ave, Florham Park, NJ 07932 USA. hkl@research.att.com
z Department of Computer Science, Sackler Faculty of Exact Sciences, Tel Aviv University,
Research supported in part by a grant from the Ministry of Science
and the Arts, Israel, and by US Department of Energy, grant No. DE-FG03-94ER61913/A000.
shamir@math.tau.ac.il
x Department of Computer Science, Princeton University, Princeton, NJ 08544 USA and InterTrust
Technologies Corporation, Sunnyvale, CA 94086 USA. Research at Princeton University partially
supported by the NSF, Grants CCR-8920505 and CCR-9626862, and the O-ce of Naval Research,
Contract No. N00014-91-J-1463. ret@cs.princeton.edu
ber of reversals re
ects the evolutionary distance between the species. Hence, given
two such permutations, their reversal distance measures their evolutionary distance.
Mathematical analysis of genome rearrangement problems was initiated by Sanko
[22, 21]. Kececioglu and Sanko [16] gave the rst constant-factor polynomial approximation
algorithm for the problem and conjectured that the problem is NP-hard.
Bafna and Pevzner [3], and more recently Christie [6] improved the approximation
factor, and additional studies have revealed the rich combinatorial structure of re-arrangement
problems [15, 14, 2, 9, 10]. Quite recently, Caprara [5] has established
that sorting unsigned permutations is NP-hard, using some of the combinatorial tools
developed by Bafna and Pevzner [3].
In 1995, Hannenhalli and Pevzner [11] showed that the problem of sorting a signed
permutation by reversals is polynomial. They proved a duality theorem that equates
the reversal distance with the sum of three combinatorial parameters (see Theorem 2.3
below). Based on this theorem, they proved that sorting signed permutations by
reversals can be done in O(n 4 ) time. More recently, Berman and Hannenhalli [4]
described a faster implementation that nds a minimum sequence of reversals in
O(n 2 (n)) time, where  is the inverse of Ackerman's function [1] (see also [23]).
In this study we give an O(n 2 ) algorithm for sorting a signed permutation of n
elements, thereby improving upon the previous best known bound [4]. In fact, if the
reversal distance is r, our algorithm requires O(r  n In addition to
giving a better time bound, our work considerably simplies both the algorithm and
combinatorial structure needed for the analysis, as follows:
The basic object we work with is an implicit representation of the overlap graph,
to be dened later, in contrast with the interleaving graph in [11] and [4]. The
overlap graph is combinatorially simpler than the interleaving graph. As a result,
it is easier to produce a representation for the overlap graph from the input, and
to maintain it while searching for reversals.
As a consequence of our ability to work with the overlap graph we need not perform
any \padding transformations", nor do we have to work with \simple permutations"
as in [11] and [4].
We deal with the unoriented and oriented parts of the permutation separately,
which makes the algorithm much simpler.
The notion of a hurdle, one of the combinatorial entities dened by [11] for the
duality theorem, is simplied and is handled in a more symmetric manner.
The search for the next reversal is much simpler, and requires no special data
structures. Our algorithm computes connected components only once, and any
simple implementation of it su-ces to obtain the quadratic time bound. In con-
trast, in [4] a logarithmic number of connected component computations may be
performed per reversal, using the union-nd data structure.
The paper is organized as follows: Section 2 gives the necessary preliminaries. Section
3 gives an overview of our algorithm. Sections 4 and 5 give the details of our algorithm.
We summarize our results and suggest some further research in Section 6.
2. Preliminaries. This section gives the basic background, primarily the theory
of Hannenhalli and Pevzner, on which we base our algorithm. The reader may nd
it helpful to refer to Figure 2.1, in which the main denitions are illustrated. We
start with some denitions for unsigned permutations. Let
permutation of ng. Augment  to a permutation on n vertices by adding
it. A pair is called a gap. Gaps
are classied into two types. breakpoint of  if and only if
otherwise, it is an adjacency of . We denote by b() the number of
breakpoints in .
A reversal, (i; j), on a permutation  transforms  to
We say that a reversal (i; j) acts on the gaps (
a
c
4,5
2,3
Fig. 2.1. a) The breakpoint graph, B(), of the permutation
edges are solid; gray edges are dashed; oriented edges are bold. b) B() decomposes into two disjoint
alternating cycles. c) The overlap graph, OV (). Black vertices correspond to oriented edges.
2.1. The breakpoint graph. The breakpoint graph B() of a permutation
is an edge-colored graph on n
1g. We join vertices  i and  j by a black edge if
in  and by a gray edge if (i; j) is a breakpoint in  1 .
We dene a one-to-one mapping u from the set of signed permutations of order
n into the set of unsigned permutations of order 2n as follows. Let  be a signed
permutation. To obtain u(), replace each positive element x in  by 2x
and each negative element x by 2x; 2x 1. For any signed permutation , let
Note that in B() every vertex is either isolated or incident to
exactly one black edge and one gray edge. Therefore, there is a unique decomposition
of B() into cycles. The edges of each cycle alternate between gray and black. Call a
reversal (i; j) such that i is odd and j even an even reversal. The reversal (2i+1; 2j)
on u() mimics the reversal (i+1; j) on . Thus, sorting  by reversals is equivalent to
sorting the unsigned permutation u() by even reversals. Henceforth we will consider
the latter problem, and by a reversal we will always mean an even reversal. Let
c() be the number of cycles in B().

Figure

2.1(a) shows the breakpoint graph of the permutation
It has eight breakpoints and decomposes into two alternating cycles, i.e.
2. The two cycles are shown in Figure 2.1(b). Figure 2.2(a) shows the break-point
graph of  which has seven breakpoints and decomposes
into two cycles.
For an arbitrary reversal  on a permutation , dene b(;
and c(; c(). When the reversal  and the permutation  are clear
from the context, we will abbreviate b(; ) by b and c(; ) by c. As Bafna
and Pevzner [3] observed, the following values are taken by b and c depending on
the types of the gaps (i; acts on:
1. Two adjacencies: 2.
2. A breakpoint and an adjacency:
3. Two breakpoints each belonging to a dierent cycle:
4. Two breakpoints of the same cycle C:
a. are gray edges: 2.
b. Exactly one of
c. Neither gray edge, and when breaking C at i and
in the same
d. Neither gray edge, and when breaking C at i and
dierent paths:
Call a reversal proper if b c = 1, i.e. it is either of type 4a, 4b, or 4d.
We say that a reversal  acts on a gray edge e if it acts on the breakpoints which
correspond to the black edges incident with e. A gray edge is oriented if a reversal
acting on it is proper, otherwise it is unoriented. Notice that a gray edge
oriented if and only if k + l is even. For example, the gray edge (0; 1) in the graph of

Figure

2.1(a) is unoriented, while the gray edge (7;
2.2. The overlap graph. Two intervals on the real line overlap if their intersection
is nonempty but neither properly contains the other. A graph G is an interval
overlap graph if one can assign an interval to each vertex such that two vertices are
adjacent if and only if the corresponding intervals overlap (see, e.g., [8]). For a permutation
, we associate with a gray edge the interval [i; j]. The overlap graph
of a permutation , denoted OV (), is the interval overlap graph of the gray edges
of B(). Namely, the vertex set of OV () is the set of gray edges in B(), and two
vertices are connected if the intervals associated with their gray edges overlap. We
shall identify a vertex in OV () with the edge it represents and with its interval in the
representation. Thus, the endpoints of a gray edge are actually the endpoints of the
interval representing the corresponding vertex in OV (). Note that all the endpoints
of intervals in this representation are distinct integers. A connected component of
OV () that contains an oriented edge is called an oriented component; otherwise, it
is called an unoriented component.

Figure

2.1(c) shows the interval overlap graph for It
has only one oriented component. Figure 2.2(b) shows the overlap graph of the permutation
which has two connected components, one oriented
and the other unoriented.
a
4,5
Fig. 2.2. a) The breakpoint graph of  was obtained from  of

Figure

2.1 by the reversal (7; 10); or, equivalently, by the reversal dened by the gray edge (2; 3).
b) The overlap graph of  0 .
2.3. The connected components of the overlap graph. Let X be a set of
gray edges in B(). Dene
Xg and Equivalently, one can look at the interval overlap
representation of OV () mentioned above and dene the span of a set of vertices
X as the minimum interval which contains all the intervals of vertices in X .
The major object our algorithm will work with is OV (), though for e-ciency
considerations we will avoid generating it explicitly. In contrast, Pevzner and Han-
nenhalli worked with the interleaving graph H  , whose vertices are the alternating
cycles of B(). Two cycles C 1 and C 2 are connected by an edge in H  i there exists
a gray edge e 1 2 C 1 and a gray edge e 2 2 C 2 that overlap.
The following lemma and its corollary imply that the partition imposed by the
connected components of OV () on the set of gray edges is identical to the one
imposed by the connected components of H  :
Lemma 2.1. If M is a set of gray edges in B() that corresponds to a connected
component in OV () then min(M) is even and max(M) is odd.
Proof. Assume min(M) is odd. Then  must both
be in span(M) (i.e. there exist l 1 span(M) such that  l 1
1). Thus  min(M) is neither the maximum nor the minimum element
in the set f i span(M)g. Hence, either the maximum element or the minimum
element in span(M) is  j for some min(M) < j < max(M ). By the denition of B()
there must be a gray edge contradicting the fact that
M is a connected component in OV (). The proof that max(M) is odd is similar.
As an illustration of Lemma 2.1, consider Figure 2.2(a). Let M
and
[10; 15].
Corollary 2.2. Every connected component of OV () corresponds to the set of
gray edges of a union of cycles.
Proof. Assume by contradiction that C is a cycle whose gray edges belong to
at least two connected components in OV (). Assume M 1 and M 2 are two of these
components such that there are two consecutive gray edges
along C. Since the spans of dierent connected components in OV () cannot overlap
there are two dierent cases to consider.
1.
e 1 and e 2 are in dierent components they cannot overlap. Thus, either the right
endpoint of e 2 is even and equals max(M 2 ) or the left endpoint of e 2 is odd and
In both cases we have a contradiction to Lemma 2.1.
2. are disjoint intervals. W.l.o.g. assume that max(M 1 ) <
The right endpoint of e 1 is even and equals max(M 1 ), which contradicts
Lemma 2.1.
Note that in particular Corollary 2.2 implies that an overlap graph cannot contain
isolated vertices.
2.4. Hurdles. Let  i 1
be the subsequence of 0;  consisting
of those elements incident with gray edges that occur in unoriented components
of OV (). Order  i 1
on a circle CR such that  i j
for
. Let M be an unoriented connected component in
g be the set of endpoints of the edges in M . An
unoriented component M is a hurdle if the elements of E(M) occur consecutively on
CR.
This denition of a hurdle is dierent from the one given by Hannenhalli and
Pevzner [11]. It is simpler in the sense that minimal hurdles and the maximal one do
not have to be treated in dierent ways. Using Corollary 2.2 above, one can prove that
the hurdles as we have dened them are identical to the ones dened by Hannenhalli
and Pevzner. Let h() denote the number of hurdles in a permutation .
A hurdle is simple if when one deletes it from OV () no other unoriented component
becomes a hurdle, and it is a super hurdle otherwise. A fortress is a permutation
with an odd number of hurdles all of which are super hurdles.
The following theorem was proved by Hannenhalli and Pevzner.
Theorem 2.3. [11] The minimum number of reversals required to sort a permutation
is b() c() + h(), unless  is a fortress, in which case exactly one
additional reversal is necessary and su-cient.
3. Overview of our algorithm. Denote by d() the reversal distance of , i.e.,
is a fortress and
Following the theory developed in [11], it turns out that given a permutation
with h() > 0 one can perform
permutation  0 such that h( 0 t. If OV () has unoriented
components then our algorithm rst nds t such reversals that transform  into a  0
which has only oriented components.
Our method of \clearing the hurdles" uses the theory developed by Hannenhalli
and Pevzner. In Section 5 we describe an e-cient implementation of this process
which uses the implicit representation of the overlap graph OV (). Our implementation
runs in O(n) time assuming OV () is already partitioned into its connected
components. Recently, Berman and Hannenhalli [4] gave an O(n(n)) algorithm for
computing the connected components of an interval overlap graph given implicitly by
its representation. Using their algorithm we can clear the hurdles from a permutation
in O(n(n)) time.
The overlap graph of  0 , OV ( 0 ), has only oriented components. In Section 4 we
prove that in the neighborhood of any oriented gray edge e there is an oriented gray
could be the same as e) such that a reversal acting on e 1 does not create
new hurdles. Call such a reversal a safe reversal. We develop an e-cient algorithm
to locate a safe reversal in a permutation with at least one oriented gray edge. Our
algorithm uses only an implicit representation of the overlap graph and runs in O(n)
time.
The second stage of our algorithm repeatedly nds a safe reversal and performs
it as long as OV () is not empty. Clearly the overall complexity is O(r  n
where r is the number of reversals required to sort  0 .
3.1. Representing the overlap graph. We assume that the input is given as
a sequence of n signed integers representing  0 . First the permutation
constructed as described in Section 2.1 and stored in an array. We also construct an
array representing  1 . It is straightforward to verify that with these two arrays we
can determine for each element in  whether it is a left or a right endpoint of a gray
edge in constant time. In case the element is an endpoint of a gray edge we can also
nd the other endpoint and check whether the edge is oriented in constant time.
Thus the arrays  and  1 comprise a representation of OV (). Our algorithm
will maintain these two arrays while carrying out the reversals that it nds. The time
to update the arrays is proportional to the length of the interval being reversed, which
is O(n). We shall give a high-level presentation of our algorithm and use primitives
like \Scan the oriented gray edges in increasing left endpoint order". It is easy to
see how to implement these primitives using the arrays  and  1 ; we shall omit the
details.
It is easy to produce a list of the intervals in the representation of OV () sorted
by either left or right endpoint from the arrays  and  1 . It is also possible to
maintain them without increasing the asymptotic time bound of the algorithm. In
practice it may be faster to maintain such lists instead of, or in addition to  and
4. Eliminating oriented components. First we introduce some notation. Recall
that the vertices of OV () are the gray edges of B(). In order to avoid confusion
we will usually refer to them as vertices of OV (). Hence a vertex of OV () is oriented
if the corresponding gray edge is oriented and it is unoriented otherwise. Let e be a
vertex in OV (). Denote by r(e) the reversal acting on the gray edge corresponding
to e. Denote by N(e) the set of neighbors of e in OV () including e itself. Denote by
ON(e) the subset of N(e) containing the oriented vertices and by UN(e) the subset
of N(e) containing the unoriented vertices.
In this section we prove that if an oriented vertex e exists in OV () then there
exists an oriented vertex f 2 ON(e) such that r(f) is proper and safe. We also
describe an algorithm that nds a proper safe reversal in a permutation that contains
at least one oriented edge.
We start with the following useful observation:
Observation 4.1. Let e be a vertex in OV () and let
be obtained from OV () by the following operations. 1) Complement the graph induced
by OV () on N(e) feg, and
ip the orientation of every vertex in N(e) feg. 2)
If e is oriented in OV () then remove it from OV (). 3) If there exists an oriented
edge e 0 in OV () with
Note that if e is an oriented vertex in a component M of OV (), M feg may
split into several components in OV ( 0 ). (Compare gures 2.1(c) and 2.2(b).) Denote
these components by M 0
k (e), where k  1. We will refer to M 0
simply
as
whenever e is clear from the context.
Let C be a clique of oriented vertices in OV (). We say that C is happy if for
every oriented vertex e 62 C and every vertex f 2 C such that (e; f) 2 E(OV ()) there
exists an oriented vertex g 62 C such that (g; e) 2 E(OV ()) and (g; f) 62 E(OV ()).
For example, in the overlap graph shown in Figure 2.1(c) f(2; 3); (10; 11)g and f(6; 7)g
are happy cliques, but f(2; 3); (10; 11); (8; 9)g is not. Our rst theorem claims that one
of vertices in any happy clique denes a safe proper reversal.
Theorem 4.1. Let C be a happy clique and let e be a vertex in C such that
for every e 0 2 C. Then the reversal r(e) is safe.
Proof. Let  assume by contradiction that M 0
i (e) is unoriented for
Assume there exists y 2 N(e) \ M 0
i such that y 62 C. Clearly y must be oriented
in OV () and since C is happy it must also have an oriented neighbor y 0 such that
not adjacent to e in OV () it stays oriented and
adjacent to y in OV ( 0 ), in contradiction with the assumption that M 0
i is unoriented.
Hence we may assume that N(e) \ M 0
i and let z 2 UN(e). Vertex z is oriented in OV ( 0 ) and if it is
adjacent to y in OV ( 0 ) we obtain a contradiction. Hence, z and y are not adjacent in
must be adjacent in OV (). Hence we obtain that UN(e)  UN(y)
in OV (). Corollary 2.2 implies that component M 0
cannot contain y alone. Thus y
must have a neighbor x in M 0
x is not adjacent to e
in OV (). Thus we obtain that (x; y) 2 OV (), (x; e) 62 OV (), and x is unoriented
in OV (). Since we have already proved that UN(e)  UN(y), this implies that
UN(e)  UN(y), in contradiction with the choice of e.
For example Theorem 4.1 implies that the reversal dened by the gray edge
(10; 11) is a safe proper reversal for the permutation of Figure 2.1 (a), since it
corresponds to the vertex with maximum unoriented degree in the happy clique
11)g. On the other hand, the reversal dened by (2; creates a new
unoriented component, as it yields the permutation shown in Figure 2.2.
The following theorem proves that a happy clique exists in the neighborhood of
any oriented edge.
Theorem 4.2. Let e be an oriented vertex in OV (). There exists an oriented
vertex f 2 ON(e) such that for  all the components in OV ( 0 ) are oriented

Proof. By Theorem 4.1 it su-ces to show that there exists a happy clique C in
ON(e).
there exists y 2 ON(x) such that y 62 ON(e)g.
That is, Ext(e) contains all oriented neighbors of e which have oriented neighbors
outside of ON(e).
Case 1:
Case 2: Ext(e)  ON(e) feg. Let D
not a clique let K j be a maximal clique in D j and dene D
be the nal clique and set
It is straightforward to verify that in each of the two cases C is indeed a happy clique.
In the next section we describe an algorithm that will nd an oriented edge e
such that r(e) is safe given the representation of OV () described in Section 3.1. The
algorithm rst nds a happy clique C and then searches for the vertex with maximum
unoriented degree in C. According to Theorem 4.1 this vertex denes a safe reversal.
Even though Theorem 4.2 guarantees the existence of a happy clique in the neighborhood
of any xed oriented vertex, our algorithm does not search in one particular
such neighborhood. We will prove that the algorithm is guaranteed to nd a happy
clique assuming that there exists at least one oriented edge. Therefore the algorithm
provides an alternative proof to a weaker version of Theorem 4.2 that only claims the
existence of a happy clique somewhere in the graph.
4.1. Finding a happy clique. In this section we give an algorithm that
locates a happy clique in OV (). Let e be the oriented vertices in OV () in
increasing left endpoint order. The algorithm traverses the oriented vertices in OV ()
according to this order. Let L(e) and R(e) be the left and right endpoints, respectively,
of vertex e in the realization of OV (). After traversing e the
algorithm maintains a happy clique C i in the subgraph of OV () induced by these
vertices. Assume jC
be the vertices in C i where
. The vertices of C i are maintained in a linked list ordered in
increasing left endpoint order. If there exists an interval that contains all the intervals
in C i then the algorithm maintains a minimal such interval t i . The clique C i and the
vertex t i (if exists) satisfy the following invariant.
Invariant 4.1.
Every vertex e l 62 C i , l  i, such that L(e i 1
must be adjacent to t i , i.e.,
) that is adjacent to a vertex in C i is either
adjacent to an interval e p such that R(e p ) < L(e
or adjacent to t i .
The fact that C i is happy in the subgraph induced by e
this invariant. We initialize the algorithm by setting C g. Initially, t 1 is not
dened. Let the current interval be e i+1 . If R(e i j
guaranteed
to be happy in OV () since all remaining oriented vertices are not adjacent to C i .
Hence the algorithm stops and returns C i as the answer. See Figure 4.1(a).
We now assume that L(e i+1
show how to obtain C i+1 and t i+1 .
We have to consider the following cases.
Case 1. The interval t i is dened and
Figure 4.1(b).
Case 2. The interval t i is not dened or R(e i+1
a)
obtained by adding e i+1 to C i and
Figure 4.1(c).
). The clique C i+1 consists of e i+1 alone and
Figure 4.1(d).
c)
). As in the previous case C g. In this case t i+1 is set
to e i j
, the last interval in C i . See Figure 4.1(e).
The following theorem proves that the algorithm above produces a happy clique.
Theorem 4.3. Let C l be the current clique when the algorithm stops. Then C l
is a happy clique in OV ().
Proof. A straightforward induction on the number of oriented vertices traversed
by the algorithm proves that C l and t l satisfy Invariant 4.1.
The algorithm stops either when R(e
when l is equal to the
number of oriented vertices. In either case since C l is happy in the subgraph induced
by e must be happy in OV ().
The running time of the algorithm is proportional to the number of oriented
vertices traversed since a constant amount of work is performed for each such vertex.
4.2. Searching the happy clique. After locating a happy clique C in OV ()
we need to search it for a vertex with a maximum number of unoriented neighbors.
In this section we give an algorithm that performs this task.
d
a
e
c
Fig. 4.1. The various cases of the algorithm for nding a happy clique. The topmost interval
is always t i . The three thick intervals comprise C i . The dotted interval corresponds to e i+1 .
be the intervals in C ordered in increasing left endpoint order.
Clearly, R(j). Thus the endpoints
of the j vertices in C partition the line into 2j
I
1). The algorithm consists of the
following three stages.
Stage 1: Let e be an unoriented vertex that has a non-empty intersection with the
interval [L(1); R(j)]. Mark each of e's endpoints with the index of the interval that
contains it.
Stage 2: Let o be an array of j counters, each corresponding to a vertex in C. The
intention is to assign values to o such that the sum P l
o[i] is the unoriented degree
of the vertex e l 2 C. The counters are initialized to zero. For each unoriented vertex
e that overlaps with the interval [L(1); R(j)] we change at most four of the counters
as follows. Let I l and I r be the intervals in which L(e) and R(e) occur, respectively.
We may assume l < r as otherwise e is not adjacent to any vertex in C and we can
ignore it. We continue according to one of the following cases.
Case 1: r  j. All the vertices from e l+1 to e r are adjacent to e: we increment o[l
and decrement o[r
Case 2: j  l. All the vertices from e l j+1 to e r j are adjacent to e: we increment
decrement
Case 3: l < j and j < r. Let all the vertices from
e 1 to e m are adjacent to e: we increment o[1] and decrement o[m
then the vertices from e l+1 to e j are adjacent to e: we
increment the counter o[l
Stage 3: Compute
jg. Return e f .
The following theorem summarizes the result of this section. We omit the proof,
which is straightforward.
Theorem 4.4. Given a clique C, the vertex e f 2 C computed by the algorithm
above has maximum unoriented degree among the vertices in C.
The complexity of the algorithm is proportional to the size of C plus the number
of unoriented vertices in OV (), and hence is O(n).
5. Clearing the hurdles. In case there are unoriented components in OV (),
there exists a sequence r of t reversals that transform  into  0 such that
t, where dh()=2e. In this section we summarize the characterization given
by Hannenhalli and Pevzner for these t reversals and outline how to nd them using
our implicit representation of OV ().
We will use the following denitions. A reversal merges hurdles H 1 and H 2 if it
acts on two breakpoints, one incident with a gray edge in H 1 and the other incident
with a gray edge in H 2 . Recall the circle CR dened in Section 2, in which the
endpoints of the edges in the unoriented components of OV () are ordered consistently
with their order in . Two hurdles H 1 and H 2 are consecutive if their sets of endpoints
occur consecutively on CR, i.e., there is no hurdle H such that
E(H) separates E(H 1 ) and E(H 2 ) on CR.
The following lemmas were essentially proved by Hannenhalli and Pevzner though
stated dierently in their paper.
Lemma 5.1 ([11]). Let  be a permutation with an even number, say 2k, of
hurdles. Any sequence of k 1 reversals each of which merges two non-consecutive
hurdles followed by a reversal merging the remaining two hurdles will transform  into
0 such that has only oriented components.
Lemma 5.2 ([11]). Let  be a permutation with an odd number, say 2k
hurdles. If at least one hurdle H is simple then a reversal acting on two breakpoints
incident with edges in H transforms  into  0 with 2k hurdles such that
d() 1. If  is a fortress then a sequence of k 1 reversals merging pairs of non-consecutive
hurdles followed by two additional merges of pairs of consecutive hurdles
(one merges two original hurdles and the next merges a hurdle created by the rst and
the last original hurdle) will transform  into  0 such that
0 has only oriented components.
We now outline how to turn these lemmas into an algorithm that nds a particular
sequence of reversals r with the properties described above. First OV () is
decomposed into connected components as described in [4]. One then has to identify
those unoriented components that are hurdles. This task can be done by traversing the
endpoints of the circle CR, counting the number of elements in each run of consecutive
endpoints belonging to the same component. If a run contains all endpoints of a
particular unoriented component M then M is an hurdle.
In a similar fashion one can check for each hurdle whether it is a simple hurdle
or a super hurdle. While traversing the cycle, a list of the hurdles in the order they
occur on CR is created. At the next stage this list is used to identify correct hurdles
to merge.
We assume that given an endpoint one can locate its connected component in
constant time. It is easy to verify that the data can be maintained so that this is
possible.
Theorem 5.3. Given OV () decomposed into its connected components, the
algorithm outlined above nds t reversals such that when we apply them to  we obtain
a  0 which is hurdle-free and has t. The algorithm can be implemented
to run in O(n) time.
Proof. Correctness follows from Lemma 5.1 and 5.2. The time bound is achieved
if we always merge hurdles that are separated by a single hurdle. If the ith merge
merged hurdles H 1 and H 2 that are separated by H , then H should be merged in the
1st merge. Carrying out the merges this way guarantees that the span of each
hurdle H overlaps at most two merging reversals, the second of which eliminates H .
6.

Summary

. Figure 6.1 gives a schematic description of the algorithm.
algorithm Signed Reversals();
/*  is a signed permutation */
1. Compute the connected components of OV ().
2. Clear the hurdles.
3. while  is not sorted do :
iteration */
begin
a. nd a happy clique C in OV ().
b. nd a vertex e f 2 C with maximum unoriented
degree, and perform a safe reversal on e f ;
c. update  and the representation of OV ().
4. output the sequence of reversals.
Fig. 6.1. An algorithm for sorting signed permutations
Theorem 6.1. Algorithm Signed Reversals nds the reversal distance r in
n) time, and in particular in O(n 2 ) time.
Proof. The correctness of the algorithm follows from Theorem 2.3, Theorem 4.1
and Lemmas 5.1 and 5.2.
by the algorithm of Berman and Hannenhalli [4].
takes O(n) time by Theorem 5.3. Step 3 takes O(n) time per reversal, by the
discussion in Section 4.
It is an intriguing open question whether a faster algorithm for sorting signed
permutations by reversals exists. It certainly might be the case that one can nd an
optimal sequence of reversals faster. To date, no nontrivial lower bound is known for
this problem.

Acknowledgments

. We thank Donald Knuth, Sridhar Hannenhalli, Pavel Pevzner,
and Itsik Pe'er for their comments on a preliminary version of this paper.



--R

Zum hilbertshen aufbau der reelen zahlen
Sorting permutations by transpositions
SIAM Journal on Computing
Fast
Sorting by reversals is di-cult

Inversions in the chromosomes of drosophila pseu- doobscura
Algorithmic Graph Theory and Perfect Graphs
Polynomial algorithm for computing translocation distance between genomes
Transforming men into mice (polynomial algorithm for genomic distance problems
Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals)
including parallel inversions
Faster and simpler algorithm for sorting signed permutations by reversals
Physical mapping of chromosomes using unique probes


Tricircular mitochondrial genomes of Brassica and Raphanus: reversal of repeat con


Evolutionalry signi
Edit distance for genome comparison based on non-local operations
Genomic divergence through gene rearrangement.

--TR

--CTR
Tannier , Anne Bergeron , Marie-France Sagot, Advances on sorting by reversals, Discrete Applied Mathematics, v.155 n.6-7, p.881-888, April, 2007
Anne Bergeron, A very elementary presentation of the Hannenhalli-Pevzner theory, Discrete Applied Mathematics, v.146 n.2, p.134-145, 1 March 2005
Glenn Tesler, Efficient algorithms for multichromosomal genome rearrangements, Journal of Computer and System Sciences, v.65 n.3, p.587-609, November 2002
Adam C. Siepel, An algorithm to enumerate all sorting reversals, Proceedings of the sixth annual international conference on Computational biology, p.281-290, April 18-21, 2002, Washington, DC, USA
Max A. Alekseyev , Pavel A. Pevzner, Colored de Bruijn Graphs and the Genome Halving Problem, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.1, p.98-107, January 2007
Haim Kaplan , Elad Verbin, Sorting signed permutations by reversals, revisited, Journal of Computer and System Sciences, v.70 n.3, p.321-341, May 2005
Isaac Elias , Tzvika Hartman, A 1.375-Approximation Algorithm for Sorting by Transpositions, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.3 n.4, p.369-379, October 2006
Severine Berard , Anne Bergeron , Cedric Chauve , Christophe Paul, Perfect Sorting by Reversals Is Not Always Difficult, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.1, p.4-16, January 2007
reversal distance;computational molecular biology;sorting permutations