Inapproximability of maximal strip recovery

DOI10.1007/978-3-642-14553-7_8zbMATH Open1288.68301arXiv0912.4935OpenAlexW3123386506MaRDI QIDQ3587336FDOQ3587336

Authors: Minghui Jiang 

Publication date: 7 September 2010

Published in: Algorithms and Computation, Frontiers in Algorithmics (Search for Journal in Brave)

Abstract: 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 $dge2$, a polynomial-time 2d-approximation for msr{d} was previously known. In this paper, we show that for any $dge2$, 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 $dge2$. In particular, we show that msr{d} is NP-hard to approximate within $Omega(d/logd)$. 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}.

Full work available at URL: https://arxiv.org/abs/0912.4935

Recommendations

• Inapproximability of maximal strip recovery
• Inapproximability of maximal strip recovery
• Tractability and approximability of maximal strip recovery
• On recovering syntenic blocks from comparative maps
• On Recovering Syntenic Blocks from Comparative Maps

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Cited In (15)

• A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem
• Tractability and approximability of maximal strip recovery
• Exact and approximation algorithms for the complementary maximal strip recovery problem
• Inapproximability of maximal strip recovery
• An improved approximation algorithm for the complementary maximal strip recovery problem
• Tractability and approximability of maximal strip recovery
• Inapproximability of maximal strip recovery
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• On recovering syntenic blocks from comparative maps
• An improved approximation algorithm for the complementary maximal strip recovery problem
• On Recovering Syntenic Blocks from Comparative Maps
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• A linear kernel for the complementary maximal strip recovery problem
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• On the Tractability of Maximal Strip Recovery

This page was built for publication: Inapproximability of maximal strip recovery

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587336)