Inapproximability of maximal strip recovery

DOI10.1016/J.TCS.2011.04.021MaRDI QIDQ551208zbMATH OpenOpenAlexFDO

Authors Minghui Jiang

Publication date 14 July 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.04.021

zbMATH Keywords

computational complexitybioinformaticssequence analysisgenome rearrangement

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Biochemistry, molecular biology (92C40) Genetics and epigenetics (92D10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Tractability and approximability of maximal strip recovery
• Tractability and approximability of maximal strip recovery
• On recovering syntenic blocks from comparative maps

Cites work

• scientific article; zbMATH DE number 3717365 (Why is no real title available?)
• Automata, Languages and Programming
• Complexity of approximating bounded variants of optimization problems
• Covering and packing in graphs IV: Linear arboricity
• Hardness of approximation for non-overlapping local alignments.
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• Non-approximability of weighted multiple sequence alignment for arbitrary metrics
• Non-approximability results for optimization problems on bounded degree instances
• On recovering syntenic blocks from comparative maps
• On the Tractability of Maximal Strip Recovery
• On the complexity of approximating \(k\)-set packing
• On the complexity of unsigned translocation distance
• On the hardness of approximating minimum vertex cover
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Optimization, approximation, and complexity classes
• Paired approximation problems and incompatible inapproximabilities
• Scheduling Split Intervals
• Some APX-completeness results for cubic graphs
• The linear arboricity of graphs
• Tractability and approximability of maximal strip recovery

Cited in

(13)

• A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem
• Tractability and approximability of maximal strip recovery
• An improved approximation algorithm for the complementary maximal strip recovery problem
• Tractability and approximability of maximal strip recovery
• On recovering syntenic blocks from comparative maps
• A 42k Kernel for the Complementary Maximal Strip Recovery Problem
• The complexity of finding common partitions of genomes with predefined block sizes
• An improved approximation algorithm for the complementary maximal strip recovery problem
• An improved linear kernel for complementary maximal strip recovery: simpler and smaller
• On Recovering Syntenic Blocks from Comparative Maps
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• Recognizing d-interval graphs and d-track interval graphs

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 Q551208)