Approximating Weighted Duo-Preservation in Comparative
Genomics∗

arXiv:1708.09325v1 [cs.DS] 30 Aug 2017

Saeed Mehrabi
School of Computer Science
Carleton University, Ottawa, Canada
mehrabi235@gmail.com

Abstract
Motivated by comparative genomics, Chen et al. [9] introduced the Maximum Duo-preservation
String Mapping (MDSM) problem in which we are given two strings s1 and s2 from the same alphabet and the goal is to find a mapping π between them so as to maximize the number of
duos preserved. A duo is any two consecutive characters in a string and it is preserved in the
mapping if its two consecutive characters in s1 are mapped to same two consecutive characters
in s2 . The MDSM problem is known to be NP-hard and there are approximation algorithms for
this problem [3, 5, 13], but all of them consider only the “unweighted” version of the problem
in the sense that a duo from s1 is preserved by mapping to any same duo in s2 regardless of
their positions in the respective strings. However, it is well-desired in comparative genomics to
find mappings that consider preserving duos that are “closer” to each other under some distance
measure [19].
In this paper, we introduce a generalized version of the problem, called the Maximum-Weight
Duo-preservation String Mapping (MWDSM) problem that captures both duos-preservation and
duos-distance measures in the sense that mapping a duo from s1 to each preserved duo in s2
has a weight, indicating the “closeness” of the two duos. The objective of the MWDSM problem is
to find a mapping so as to maximize the total weight of preserved duos. In this paper, we give
a polynomial-time 6-approximation algorithm for this problem.

1

Introduction

Strings comparison is one of the central problems in the field of stringology with many applications
such as in Data Compression and Bioinformatics. One of the most common goals of strings comparison is to measure the similarity between them, and one of the many ways in doing so is to compute
the edit distance between them. The edit distance between two strings is defined as the minimum
number of edit operations to transform one string into the other. In biology, during the process of
DNA sequencing for instance, computing the edit distance between the DNA molecules of different
species can provide insight about the level of “synteny” between them; here, each edit operation is
considered as a single mutation.
∗

Appeared in proceedings of the 23rd International Computing and Combinatorics Conference (COCOON
2017) [18]. This work was done when the author was at the University of Waterloo.

1

s1 :

b

a

c

b

d

c

d

d

b

a

a

c

s2 :

a

c

d

b

b

c

a

d

d

a

c

b

Figure 1: An instance of the MDSM problem in which the mapping π preserves three duos.
In the simplest form, the only edit operation that is allowed in computing the edit distance is to
shift a block of characters; that is, to change the order of the characters in the string. Computing
the edit distance under this operation reduces to the Minimum Common String Partition (MCSP)
problem, which was introduced by Goldstein et al. [14] (see also [21]) and is defined as follows. For
a string s, let P (s) denote a partition of s. Given two strings s1 and s2 each of length n, where s2 is
a permutation of s1 , the objective of the MCSP problem is to find a partition P (s1 ) of s1 and P (s2 )
of s2 of minimum cardinality such that P (s2 ) is a permutation of P (s1 ). The problem is known to
be NP-hard and even APX-hard [14].
Recently, Chen et al. [9] introduced a maximization version of the MCSP problem, called the
Maximum Duo-preservation String Mapping (MDSM) problem. A duo in a string s is a pair of
consecutive characters in s. For two strings s1 and s2 , where s2 is a permutation of s1 under a
mapping π, we say that a duo is preserved in the mapping π, if its two consecutive characters are
mapped to same two consecutive characters in s2 . Notice that if partitions P (s1 ) and P (s2 ) are a
solution of size r for an instance of the MCSP problem, then this solution can be used to obtain
a mapping π from s1 to s2 that preserve n − r duos. As such, given two strings s1 and s2 , the
objective of the MDSM problem is to compute a mapping π from s1 to s2 that preserves a maximum
number of duos. See Figure 1 for an example.
Related Work. Since the MCSP problem is NP-hard [14], there has been many works on designing polynomial-time approximation algorithms for this problem [10, 11, 12, 14, 17]. The best
approximation results thus far are an O(log n log∗ n)-approximation algorithm for the general version of the problem [12], and an O(k)-approximation for the k-MCSP problem [12] (the k-MCSP
is a variant of the problem in which each character can appear at most k times in each string).
In terms of the parameterized complexity, the problem is known to be fixed-parameter tractable
with respect to k and the size of an optimal partition [6, 16], as well as the size of an optimal
solution only [7]. For the MDSM problem, we observe that since the MCSP problem is NP-hard [14],
the MDSM problem (i.e., its maximization version) is also NP-hard, and in fact even APX-hard [4].
Moreover, the problem is also shown to be fixed-parameter tractable with respect to the number
of duos preserved [2]. Boria et al. [4] gave a 4-approximation algorithm for the MDSM problem,
which was subsequently improved to algorithms with approximation factors of 7/2 [3], 3.25 [5] and
(recently) (2 + ) for any  > 0 [13].
Motivation and Problem Statement. Observe that in the MDSM problem mapping a duo from
s1 to a preserved duo in s2 does not consider the position of the two duos in s1 and s2 . In Figure 1,
for instance, the first ac in s1 is mapped to the second ac in s2 and the second ac in s1 is mapped
to the first ac in s2 . But, another (perhaps more realistic) mapping would be the one that maps
2

the first ac in s1 to the first ac in s2 and the second one in s1 to the second one in s2 . The
latter mapping would become more desirable when solving the problem on strings of extremely long
length. In fact, considering the applications of the MDSM problem in comparative genomics, it is
much more desirable to find mappings that take into account the position of the preserved features
in the two sequences [19, 15]. One reason behind this is the fact that focusing on giving priority
to preserving features that are “closer” to each other (distance-wise under some distance measure)
provides better information about the “synteny” of the corresponding species [19, 15].
In this paper, we introduce a more general variant of the MDSM problem, called the MaximumWeight Duo-preservation String Mapping (MWDSM) problem. In this problem, in addition to s1 and
s2 , we are also given a weight function defined on pairs of duos that considers the position of the
duos in s1 and s2 , and so better captures the concept of “synteny” in comparative genomics. Now,
the objective becomes maximizing the total weight of the preserved duo (instead of maximizing the
number of them). Let us define the problem more formally. For a string s, we denote by D(s) the set
of all duos in s ordered from left to right. For example, if s = acbbda, then D(s) = {ac, cb, bb, bd, da}.
Definition 1.1 (The MWDSM Problem). Let s1 and s2 be two strings of length n. Moreover, let
w : D(s1 ) × D(s2 ) → R+ denote a weight function. Then, the MWDSM problem asks for a mapping π
from s1 to s2 that preserve a set S of duos such that
X
w(d, π(d))
d∈S

is maximized over all such sets S, where π(d) denotes the duo in s2 to which d ∈ s1 is mapped.
We note that the weight function is very flexible in the sense that it can capture any combination
of duos-preservation and duos-distance measures. To our knowledge, this is the first formal study
of a “weighted version” of the MDSM problem.
Our Result. Notice that the MWDSM problem is NP-hard as its unweighted variant (i.e., the
MDSM problem) is known to be NP-hard [14]. We note that the previous approximation algorithms
for the MDSM problem do not apply to the MWDSM problem. In particular, both 7/2-approximation
algorithm of Boria et al. [3] and (2 + )-approximation algorithm of Dudek et al. [13] are based
on the local search technique, which is known to fail for weighted problems [20, 8]. Moreover, the
3.25-approximation algorithm of Brubach [5] relies on a triplet matching approach, which involves
finding a weighted matching (with specialized weights) on a particular graph, but it is not clear
if the approach could handle the MWDSM problem with any arbitrary weight function w. Finally,
while the linear programming algorithm of Chen et al. [9] might apply to the MWDSM problem, the
approximation factor will likely stay the same, which is k 2 , where k is the maximum number of
times each character appears in s1 and s2 .
In this paper, we give a polynomial-time 6-approximation algorithm for the MWDSM problem for
any arbitrary weight function w. To this end, we construct a vertex-weighted graph corresponding
to the MWDSM problem and show that the problem reduces to the Maximum-Weight Independent
Set (MWIS) problem on this graph. Then, we apply the local ratio technique to approximate the
MWIS problem on this graph. The local ratio technique was introduced by Bar-Yehuda and Even [1],
and is used for designing approximation algorithms for mainly weighted optimization problems (see
Section 2 for a formal description of this technique). While the approximation factor of our algorithm
3

is slightly large in compare to that of algorithms for the unweighted version of the problem [3, 5],
as we now have weights, our algorithm is much simpler as it benefits from the simplicity of the
local ratio technique. To our knowledge, this is the first application of the local ratio technique to
problems in stringology.
Organization. The paper is organized as follows. We first give some definitions and preliminary
results in Section 2. Then, we present our 6-approximation algorithm in Section 3, and will conclude
the paper with a discussion on future work in Section 4.

2

Preliminaries

In this section, we give some definitions and preliminaries. For a graph G, we denote the set of
vertices and edges of G by V (G) and E(G), respectively. For a vertex u ∈ V (G), we denote the set
of neighbours of u by N [u]; note that u ∈ N [u].
Let w ∈ Rn be a weight vector, and let F be a set of feasibility constraints on vectors x ∈
Rn . A vector x ∈ Rn is a feasible solution to a given problem (F, p) if it satisfies all of the
constraints in F . The value of a feasible solution x is the inner product w · x. A feasible solution is
optimal for a maximization (resp., minimization) problem if its value is maximal (resp., minimal)
among all feasible solutions. A feasible solution x is an α-approximation solution, or simply an
α-approximation, for a maximization problem if w · x ≥ α · w · x∗ , where x∗ is an optimal solution.
An algorithm is said to have an approximation factor of α (or, it is called an α-approximation
algorithm), if it always computes α-approximation solutions.
Local Ratio. Our approximation algorithm uses the local ratio technique. This technique was
first developed by Bar-Yehuda and Even [1]. Let us formally state the local ratio theorem.
Theorem 2.1. [1] Let F be a set of constraints, and let w, w1 and w2 be weight vectors where
w = w1 + w2 . If x is an α-approximation solution with respect to (F, w1 ) and with respect to
(F, w2 ), then x is an α-approximation solution with respect to (F, w).
We now describe how the local ratio technique is usually used for solving a problem. First, the
solution set is empty. The idea is to find a decomposition of the weight vector w into w1 and w2
such that w1 is an “easy” weight function in some sense (we will discuss this in more details later).
The local ratio algorithm continues recursively on the instance (F, w2 ). We assume inductively that
the solution returned recursively for the instance (F, w2 ) is a good approximation and need to prove
that it is also a good approximation for (F, w). This requires proving that the solution returned
recursively for the instance (F, w2 ) is also a good approximation for the instance (F, w1 ). This step
is usually the main part of the proof of the approximation factor.
Graph GI . Given an instance of the MWDSM problem, we first construct a bipartite graph GI =
(A ∪ B, E) as follows. The vertices in the left-side set A are the duos in D(s1 ) in order from top to
bottom and the vertices in the right-side set B are the duos in D(s2 ) in order from top to bottom.
There exists an edge between two vertices if and only if they represent the same duo. See Figure 2
for an example. Boria et al [4] showed that the MDSM problem on s1 and s2 reduces to the Maximum
Constrained Matching (MCM) problem on GI , which is defined as follows. Let A = a1 , . . . , an and
B = b1 , . . . , bn . Then, we are interested in computing a maximum-cardinality matching M such
4

ab

e2

ac

ba e1

cd

ac

dd

cd
dd

e3

db
e4

dd

ba
ad

Figure 2: The graph GI corresponding to s1 = abacddd and s2 = acddbad.
that if (ai , bj ) ∈ M , then ai+1 can be only matched to bj+1 and bj+1 can be only matched to ai+1 . In
the following, we first assign weights to the edges of GI and will then show that a similar reduction
holds between the MWDSM problem on s1 and s2 , and a weighted version of the MCM problem on GI .
To weigh the edges of GI , we simply assign w(al , br ) as the weight of e, for all e ∈ E(GI ), where
al ∈ A and br ∈ B are the endpoints of e and w(al , br ) is given by Definition 1.1. Now, we define the
Maximum-Weight Constrained Matching (MWCM) problem as the problem of computing a maximumweight matching M in GI such that if (ai , bj ) ∈ M , then ai+1 can be only matched to bj+1 and bj+1
can be only matched to ai+1 . To see the equivalence between the MWDSM problem on s1 and s2 and
the MWCM problem on GI , let S be a feasible solution to the MWDSM problem with total weight w(S)
determined by a mapping π. Then, we can obtain a feasible solution S 0 for the MWCM problem on GI
by selecting the edges in GI that correspond to the preserved duos in S determined by π such that
w(S 0 ) = w(S). Moreover, it is not too hard to see that any feasible solution for the MWCM problem on
GI gives a feasible solution for the MWDSM problem with the same weight. This gives us the following
lemma.
Lemma 2.1. The MWDSM problem on s1 and s2 reduces to the MWCM problem on GI .
By Lemma 2.1, any feasible solution M with total weight w(M ) for the MWCM problem on GI gives
a mapping π between the strings s1 and s2 that preserves a set of duos with total weight w(M ). As
such, for the rest of this paper, we focus on the MWCM problem on GI and give a polynomial-time 6approximation algorithm for this problem on GI , which by Lemma 2.1, results in an approximation
algorithm with the same approximation factor for the MWDSM problem on s1 and s2 .

3

Approximation Algorithm

In this section, we give a 6-approximation algorithm for the MWCM problem. We were unable to apply
the local ratio directly to the MWCM problem on GI due to the constraint involved in the definition of
5

the problem. Instead, we construct a vertex-weighted graph GC , called the conflict graph, and show
that the MWCM problem on GI reduces to the Maximum-Weight Independent Set (MWIS) problem on
GC . We then apply the local ratio to approximate the MWIS problem on GC , which results in an
approximation algorithm for the MWCM problem on GI . Consequently, this gives us an approximation
algorithm for the MWDSM problem on s1 and s2 by Lemma 2.1.
Graph GC . We now describe the concept of conflict. We say that two edges in E(GI ) are conflicting if they both cannot be in a feasible solution for the MWCM problem at the same time, either
because they share an endpoint or their endpoints are consecutive on one side of the graph, but not
on the other side. The following observation is immediate.
Observation 3.1. Let e1 = (ai , bj ) and e2 = (ak , bl ) be two conflicting edges in E(GI ). Then,
either k ∈ {i − 1, i, i + 1} or l ∈ {j − 1, j, j + 1}.

We define the conflict graph GC as follows. Let V (GC ) be
2
1
E(GI ); that is, V (GC ) is the set of all edges in GI . For a vertex i ∈ V (GC ), we denote the edge in E(GI ) corresponding to i by
ei . Two vertices i and j are adjacent in GC if and only if ei and ej
are conflicting in GI . The conflict graph GC corresponding to the
3
4
graph GI in Figure 2 is shown on the right.
To assign weights to the vertices of GC , let i be a vertex of GC . Notice that i corresponds to
the edge ei = (al , br ) in E(GI ), where al ∈ A and br ∈ B are preserved duos. Then, the weight of
vertex i is defined as w(i) := w(al , br ) in which recall that w(al , br ) is the weight assigned to these
preserved duos by Definition 1.1. Although not precisely defined, we again note that the weight
function is very flexible and it can capture any combination of duos-preservation and duos-distance
measures.
Lemma 3.1. The MWCM problem on GI reduces to the MWIS problem on GC .
Proof. Suppose that S is a feasible solution to the MWCM problem on GI with total weight w(S). For
each edge ei ∈ S, add the vertex i ∈ V (GC ) to S 0 . Clearly, S 0 is an independent set because two
vertices i and j in S 0 being adjacent would imply that ei and ej are conflicting in GI , contradicting
the feasibility of S. To see w(S 0 ), notice that
X
X
X
w(S 0 ) =
w(i) =
w(al , br ) =
w(ei ) = w(S).
i∈S 0

ei =(al ,br )∈S

ei ∈S

S0

Now, suppose that is an independent set in GC with total weight w(S 0 ). For each u ∈ S 0 , add
eu ∈ E(GI ) to S. First, S is a feasible solution for the MWCM problem on GI because the vertices
of GC corresponding to any two conflicting edges in S would be adjacent in GC , contradicting the
fact that S 0 is an independent set. Moreover,
X
X
X
w(S) =
w(ei ) =
w(al , br ) =
w(i) = w(S 0 ).
ei ∈S

ei =(al ,br )∈S

i∈S 0

This completes the proof of the lemma.
By Lemma 3.1, any approximation algorithm for the MWIS problem on GC results in an approximation algorithm with the same factor for the MWCM problem on GI . As such, for the rest of this
section, we focus on the MWIS problem on GC and show how to apply the local ratio technique to
compute a 6-approximation algorithm for this problem on GC .
6

Approximating the MWIS Problem on GC . We first formulate the MWIS problem on GC as a
linear program. We define a variable x(u) for each vertex u ∈ V (GC ); if x(u) = 1, then vertex u
belongs to the independent set. The integer program assigns the binary values to the vertices with
the constraint that for each clique Q, the sum of the values assigned to all vertices in Q is at most
1.
X
w(u) · x(u)
(3.1)
maximize
u∈V (GC )

subject to

X

x(v) ≤ 1

∀ cliques Q ∈ GC ,

x(u) ∈ {0, 1}

∀u ∈ V (GC )

v∈Q

Note that the number of constraints in (3.1) can be exponential in general, as the number
of cliques in GC could be exponential. However, for the MWIS problem on GC , we can consider
only a polynomial number of cliques in GC . To this end, let u = (ai , bj ) be a vertex in GC . By
Observation 3.1, if v = (ak , bl ) is in conflict with u = (ai , bj ), then either k ∈ {i − 1, i, i + 1} or
l ∈ {j − 1, j, j + 1}. Let Sui−1 denote the set of all neighbours v of u in GC such that v = (ai−1 , bs )
for some bs ∈ B (recall the bipartite graph GI = (A ∪ B, E)). Define Sui and Sui+1 analogously.
Similarly, let Suj−1 be the set of all neighbours v of u such that v = (as , bj−1 ) for some as ∈ A, and
define Suj and Suj+1 analogously. Let M := {i − 1, i, i + 1, j − 1, j, j + 1}. Then, by relaxing the
integer constraint of the above integer program, we can formulate the MWIS problem on GC as the
following linear program.
X
maximize
w(u) · x(u)
(3.2)
u∈V (GC )

subject to

X
v∈Sur

x(v) ≤ 1

∀u ∈ V (GC ), ∀r ∈ M,

x(u) ≥ 0

∀u ∈ V (GC )

Notice that the linear program (3.2) has a polynomial number of constraints. These constraints
suffice for the MWIS problem on GC because, by Observation 3.1, the vertices u = (ai , bj ) and v
of GC corresponding to the two conflicting edges eu and ev in GI belong to Sur , for some r ∈ M .
Moreover, we observe that any independent set in GC gives a feasible integral solution to the linear
program. Therefore, the value of an optimal (not necessarily integer) solution to the linear program
is an upper bound on the value of an optimal integral solution.
We are now ready to describe the algorithm. We first compute an optimal solution x for the
above linear program. Then, the rounding algorithm applies a local ratio decomposition of the
weight vector w with respect to x. See Algorithm 1. The key to our rounding algorithm is the
following lemma.
Lemma 3.2. Let x be a feasible solution to (3.2). Then, there exists a vertex u ∈ V (GC ) such that
X
x(v) ≤ 6.
v∈N [u]

Proof. Let u ∈ V (GC ). Notice that u corresponds to an edge in GI ; that is, u = (ai , bj ), where ai and
bj are a pair of preserved duos in the mapping π from s1 to s2 . Observe that v ∈ N [u] for some v =
7

Algorithm 1 ApproximateMWIS(GC )
Delete all vertices with non-positive weight. If no vertex remains, then return the empty set;
2: Let u ∈ V (GC ) be a vertex satisfying
X
x(v) ≤ 6.
1:

v∈N [u]

Then, decompose w into w := w1 + w2 as follows:
(
w(u)
if v ∈ N [u],
w1 (v) :=
0
otherwise.
Solve the problem recursively using w2 as the weight vector. Let S 0 be the independent set
returned;
4: If u is not adjacent with some vertex in S 0 , then return S := S 0 ∪ {u}; otherwise, return S := S 0 .
3:

(ak , bl ) ∈ V (GC ) if and only if (ak , bl ) conflicts with (i, j) in GI . Let M := {i−1, i, i+1, j −1, j, j +1}
and define the set Sur as above, for all r ∈ M . Note that the vertices in Sur form a clique in GC , for
all r ∈ M , because the set of edges corresponding to the vertices of Sur in GI all share one endpoint
(in particular, this endpoint is in A if r ∈ {i − 1, i, i + 1} or it is in B if r ∈ {j − 1, j, j + 1}). See
Figure 3 for an illustration. This means by the first constraint of the linear program (3.2) that
X
x(v) ≤ 1,
v∈Sur

for all r ∈ M . Therefore, we have
X
v∈N [u]

x(v) ≤

X X
r∈M v∈Sur

x(v) = |M | = 6.

This completes the proof of the lemma.
We now analyze the algorithm. First, the set S returned by the algorithm is clearly an independent set. The following lemma establishes the approximation factor of the algorithm.
Lemma 3.3. Let x be a feasible solution to (3.2). Then, w(S) ≥ 61 (w · x).
Proof. We prove the lemma by induction on the number of recursive calls. In the base case, the set
returned by the algorithm satisfies the lemma because no vertices have remained. Moreover, the
first step that removes all vertices with non-positive weight cannot decrease the right-hand side of
the above inequality.
We now prove the induction step. Suppose that z and z0 correspond to the indicator vectors for
S and S 0 , respectively. By induction, w2 ·z0 ≥ 16 (w2 ·x). Since w2 (u) = 0, we have w2 ·z ≥ 16 (w2 ·x).
From the last step of the algorithm, we know that at least one vertex from N [u] is in S and so we
have
X
w1 · z = w(u)
z(v) ≥ w(u).
v∈N [u]

8

ai−1

ai

bj−1

bj

ai+1

bj+1

Figure 3: Graph GI with edge u = (ai , bj ). The edge corresponding to any vertex v ∈ N [u] in GC
is incident to at least one of the six vertices in {i − 1, i, i + 1, j − 1, j, j + 1.
Moreover, by Lemma 3.2,
w1 · x = w(u)

X
v∈N [u]

x(v) ≤ 6w(u).

Hence, w1 · x ≤ 6w(u) ≤ 6(w1 · z), which gives w1 · z ≥ 16 (w1 · x). Therefore, we conclude that
(w1 + w2 ) · z ≥ 16 (w1 + w2 ) · x and so w(S) ≥ 61 w · x. This completes the proof of the lemma.
Since there exists at least one vertex u for which w2 (u) = 0 in each recursive step, Algorithm 1
terminates in polynomial time. Therefore, by Lemmas 2.1, 3.1 and 3.3, we have the main result of
this paper.
Theorem 3.1. There exists a polynomial-time 6-approximation algorithm for the MWDSM problem
on s1 and s2 .

4

Conclusion

In this paper, we studied a weighted version of the MDSM problem [9] that considers the position of
the preserved duos in the respective input strings (i.e., the MWDSM problem). This is a natural variant
of the problem, as considering the position of the preserved features in the strings provides solutions
with better quality in many applications, such as in comparative genomics in which more weight
could indicate more synteny between the corresponding preserved features. We gave a polynomialtime 6-approximation algorithm for the MWDSM problem using the local ratio technique. Although
the approximation factor of our algorithm is a bit large in compare to that of algorithms for the
unweighted version of the problem, our algorithm is much simpler as it benefits from the simplicity
of the local ratio technique. Giving approximation algorithms with better approximation factors
for the MWDSM problem remains open for future work.

References
[1] Reuven Bar-Yehuda and Shimon Even. A local-ratio theorem for approximating the weighted
vertex cover problem. In G. Ausiello and M. Lucertini, editors, Analysis and Design of Algorithms for Combinatorial Problems, volume 109, pages 27–45. North-Holland, 1985. 3, 4
[2] Stefano Beretta, Mauro Castelli, and Riccardo Dondi. Parameterized tractability of the
maximum-duo preservation string mapping problem. Theor. Comput. Sci., 646:16–25, 2016. 2
9

[3] Nicolas Boria, Gianpiero Cabodi, Paolo Camurati, Marco Palena, Paolo Pasini, and Stefano
Quer. A 7/2-approximation algorithm for the maximum duo-preservation string mapping problem. In proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching (CPM
2016), Tel Aviv, Israel, pages 11:1–11:8, 2016. 1, 2, 3, 4
[4] Nicolas Boria, Adam Kurpisz, Samuli Leppänen, and Monaldo Mastrolilli. Improved approximation for the maximum duo-preservation string mapping problem. In proceedings of the
14th International Workshop on Algorithms in Bioinformatics (WABI 2014), Wroclaw, Poland,
pages 14–25, 2014. 2, 4
[5] Brian Brubach. Further improvement in approximating the maximum duo-preservation string
mapping problem. In proceedings of the 16th International Workshop on Algorithms in Bioinformatics (WABI 2016), Aarhus, Denmark, pages 52–64, 2016. 1, 2, 3, 4
[6] Laurent Bulteau, Guillaume Fertin, Christian Komusiewicz, and Irena Rusu. A fixed-parameter
algorithm for minimum common string partition with few duplications. In proceedings of the
13th International Workshop on Algorithms in Bioinformatics (WABI 2013), Sophia Antipolis,
France, pages 244–258, 2013. 2
[7] Laurent Bulteau and Christian Komusiewicz. Minimum common string partition parameterized
by partition size is fixed-parameter tractable. In proceedings of the Twenty-Fifth Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2014), Portland, Oregon, USA, pages 102–
121, 2014. 2
[8] Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent
set of pseudo-disks. Discrete & Computational Geometry, 48(2):373–392, 2012. 3
[9] Wenbin Chen, Zhengzhang Chen, Nagiza F. Samatova, Lingxi Peng, Jianxiong Wang, and
Maobin Tang. Solving the maximum duo-preservation string mapping problem with linear
programming. Theor. Comput. Sci., 530:1–11, 2014. 1, 2, 3, 9
[10] Xin Chen, Jie Zheng, Zheng Fu, Peng Nan, Yang Zhong, Stefano Lonardi, and Tao Jiang.
Assignment of orthologous genes via genome rearrangement. IEEE/ACM Trans. Comput.
Biology Bioinform., 2(4):302–315, 2005. 2
[11] Marek Chrobak, Petr Kolman, and Jirí Sgall. The greedy algorithm for the minimum common
string partition problem. In proceedings of the 7th International Workshop on Approximation
Algorithms for Combinatorial Optimization Problems (APPROX 2004), Cambridge, MA, USA,
pages 84–95, 2004. 2
[12] Graham Cormode and S. Muthukrishnan. The string edit distance matching problem with
moves. ACM Trans. Algorithms, 3(1):2:1–2:19, 2007. 2
[13] Bartlomiej Dudek, Pawel Gawrychowski, and Piotr Ostropolski-Nalewaja. A family of approximation algorithms for the maximum duo-preservation string mapping problem. CoRR,
abs/1702.02405, 2017. 1, 2, 3
[14] Avraham Goldstein, Petr Kolman, and Jie Zheng. Minimum common string partition problem:
Hardness and approximations. Electr. J. Comb., 12, 2005. 2, 3

10

[15] Ross C. Hardison. Comparative genomics. PLoS Biol., 1(2):e58, 2003. 3
[16] Haitao Jiang, Binhai Zhu, Daming Zhu, and Hong Zhu. Minimum common string partition
revisited. J. Comb. Optim., 23(4):519–527, 2012. 2
[17] Petr Kolman and Tomasz Walen. Reversal distance for strings with duplicates: Linear time
approximation using hitting set. Electr. J. Comb., 14(1), 2007. 2
[18] Saeed Mehrabi. Approximating weighted duo-preservation in comparative genomics. In proceedings of the 23rd International Computing and Combinatorics Conference (COCOON 2017),
Hong Kong, China, pages 396–406, 2017. 1
[19] Arcady R. Mushegian. Foundations of Comparative Genomics. Academic Press (AP), 2007. 1,
3
[20] Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems.
Discrete & Computational Geometry, 44(4):883–895, 2010. 3
[21] Krister M. Swenson, Mark Marron, Joel V. Earnest-DeYoung, and Bernard M. E. Moret.
Approximating the true evolutionary distance between two genomes. ACM Journal of Experimental Algorithmics, 12:3.5:1–3.5:17, 2008. 2

11

