Maximal Strip Recovery (MSR) and its complementary version (CMSR) are classical optimization problems arising in comparative genomics: given two genomic maps on the same set of markers, the goal is to delete as few markers as possible (CMSR) so that the remaining markers can be partitioned into a set of common strips. Existing work has established NP-hardness and APX-hardness, and for the unweighted CMSR problem a 7/3-approximation is known via a prioritized sequence of local operations plus a local amortized analysis. In practical genomic settings, however, markers differ in reliability, biological importance, or confidence level, so the cost of deleting a marker is rarely uniform. In this paper we introduce the Weighted Complementary Maximal Strip Recovery (W-CMSR) problem, in which each marker has a positive weight and the objective is to minimize the total weight of deleted markers. We show that the local-operation framework can be extended to this weighted setting. We define weight-aware priorities, prove that every operation improves a suitable potential function, and give a charging scheme that bounds the algorithm’s total deletion weight by a constant factor of the optimal deletion weight. Concretely, we obtain a constant-factor approximation (with factor ≤ 3 in the basic version); we also discuss how tighter weight-normalized charges can reduce the factor toward the unweighted 7/3 bound. Our results broaden the applicability of CMSR-style algorithms to more realistic comparative-genomics instances where certain markers must be preserved whenever possible.
Maximal Strip Recovery (MSR) and its complementary version (CMSR) are classical optimization problems arising in comparative genomics: given two genomic maps on the same set of markers, the goal is to delete as few markers as possible (CMSR) so that the remaining markers can be partitioned into a set of common strips. Existing work has established NP-hardness and APX-hardness, and for the unweighted CMSR problem a 7/3-approximation is known via a prioritized sequence of local operations plus a local amortized analysis. In practical genomic settings, however, markers differ in reliability, biological importance, or confidence level, so the cost of deleting a marker is rarely uniform. In this paper we introduce the Weighted Complementary Maximal Strip Recovery (W-CMSR) problem, in which each marker has a positive weight and the objective is to minimize the total weight of deleted markers. We show that the local-operation framework can be extended to this weighted setting. We define weight-aware priorities, prove that every operation improves a suitable potential function, and give a charging scheme that bounds the algorithm’s total deletion weight by a constant factor of the optimal deletion weight. Concretely, we obtain a constant-factor approximation (with factor ≤ 3 in the basic version); we also discuss how tighter weight-normalized charges can reduce the factor toward the unweighted 7/3 bound. Our results broaden the applicability of CMSR-style algorithms to more realistic comparative-genomics instances where certain markers must be preserved whenever possible.
