Approximating Weighted Duo-Preservation in Comparative Genomics

摘要

Motivated by comparative genomics, Chen et al. [9] introduced the Maximum Duo-preservation String Mapping (MDSM) problem in which we are given two strings s_1 and s_2 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 s_1 are mapped to same two consecutive characters in s_2. The MDSM problem is known to be NP-hard and there are approximation algorithms for this problem [3,5], all of which consider only the "unweighted" version of the problem in the sense that a duo from s_1 is preserved by mapping to any same duo in s_2 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 [18]. In this paper, we introduce a generalized version of the problem, called the Maximum-Weight Duo-preservation String Mapping (MWDSM) problem, capturing both duos-preservation and duos-distance measures in the sense that mapping a duo from s_1 to each preserved duo in s_2 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. We give a polynomial-time 6-approximation algorithm for this problem.