Inapproximability of Maximal Strip Recovery: II

Maximal Strip Recovery (MSR) is an optimization problem proposed by Zheng, Zhu, and Sankoff for reliably recovering syntenic blocks from genomic maps in the midst of noise and ambiguities. Given d genomic maps as sequences of gene markers, the objective of MSR-

d

is to find d subsequences, one subsequence of each genomic map, such that the total length of syntenic blocks in these subsequences is maximized. In our recent paper entitled “Inapproximability of Maximal Strip Recovery” in ISAAC 2009, we proved that MSR-

d

is APX-hard for any constant

d

 ≥ 2, and presented the first explicit lower bounds for approximating MSR-2, MSR-3, andMSR-4, even for the most basic version of the problem in which all markers are distinct and appear in positive orientation in each genomic map. In this paper, we present several further inapproximability results for MSR-

d

and its variants CMSR-

d

,

δ

-gap-MSR-

d

, and

δ

-gap-CMSR-

d

. One of our main results is that MSR-d is NP-hard to approximate within Ω(

d

/ log

d

) even if all markers appear in positive orientation in each genomic map. From the other direction, we show that there is a polynomial-time 2

d

-approximation algorithm for MSR-

d

even if d is not a constant but is part of the input.