Tractability and approximability of maximal strip recovery

DOI10.1016/j.tcs.2012.04.034zbMath1252.68349OpenAlexW2104689036MaRDI QIDQ441877

Laurent Bulteau, Guillaume Fertin, Irena Rusu, Ming-Hui Jiang

Publication date: 8 August 2012

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

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

zbMATH Keywords

bioinformaticsapproximation algorithmsparameterized complexitycomparative genomicssynteny blocks

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10) Approximation algorithms (68W25)

Related Items

The complexity of finding common partitions of genomes with predefined block sizes ⋮ A linear kernel for the complementary maximal strip recovery problem ⋮ A 42k Kernel for the Complementary Maximal Strip Recovery Problem ⋮ A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem ⋮ An improved linear kernel for complementary maximal strip recovery: simpler and smaller ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics

Cites Work

• Unnamed Item
• Exact and approximation algorithms for the complementary maximal strip recovery problem
• An improved approximation algorithm for the complementary maximal strip recovery problem
• 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
• Efficient Exact and Approximate Algorithms for the Complement of Maximal Strip Recovery
• Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms

This page was built for publication: Tractability and approximability of maximal strip recovery