Computer Science – Computational Complexity
Scientific paper
2009-12-25
Computer Science
Computational Complexity
A preliminary version of this paper appeared in two parts in the Proceedings of the 20th International Symposium on Algorithms
Scientific paper
In comparative genomic, the first step of sequence analysis is usually to decompose two or more genomes into syntenic blocks that are segments of homologous chromosomes. For the reliable recovery of syntenic blocks, noise and ambiguities in the genomic maps need to be removed first. 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. For any constant $d \ge 2$, a polynomial-time 2d-approximation for \msr{d} was previously known. In this paper, we show that for any $d \ge 2$, \msr{d} is APX-hard, even for the most basic version of the problem in which all gene markers are distinct and appear in positive orientation in each genomic map. Moreover, we provide the first explicit lower bounds on approximating \msr{d} for all $d \ge 2$. In particular, we show that \msr{d} is NP-hard to approximate within $\Omega(d/\log d)$. From the other direction, we show that the previous 2d-approximation for \msr{d} can be optimized into a polynomial-time algorithm even if $d$ is not a constant but is part of the input. We then extend our inapproximability results to several related problems including \cmsr{d}, \gapmsr{\delta}{d}, and \gapcmsr{\delta}{d}.
No associations
LandOfFree
Inapproximability of maximal strip recovery does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Inapproximability of maximal strip recovery, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inapproximability of maximal strip recovery will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-269535