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.