The complexity of finding common partitions of genomes with predefined block sizes
From MaRDI portal
Publication:2163952
DOI10.1007/978-3-031-06220-9_7zbMath1493.92036OpenAlexW4285305246MaRDI QIDQ2163952
Peng Zou, Manuel Lafond, Binhai Zhu, Adiesha Liyanage
Publication date: 11 August 2022
Full work available at URL: https://doi.org/10.1007/978-3-031-06220-9_7
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10) Computational methods for problems pertaining to biology (92-08)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimum common string partition revisited
- Exact and approximation algorithms for the complementary maximal strip recovery problem
- An improved approximation algorithm for the complementary maximal strip recovery problem
- Tractability and approximability of maximal strip recovery
- Inapproximability of maximal strip recovery
- On recovering syntenic blocks from comparative maps
- Permutation-constrained common string partitions with applications
- An improved linear kernel for complementary maximal strip recovery: simpler and smaller
- Maximal strip recovery problem with gaps: hardness and approximation algorithms
- A linear kernel for the complementary maximal strip recovery problem
- Minimum common string partition problem: hardness and approximations
- The greedy algorithm for the minimum common string partition problem
- An Improved Kernel for the Complementary Maximal Strip Recovery Problem
- A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem
- Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
- A Bound for a Solution of a Linear Diophantine Problem
- Hard tiling problems with simple tiles
This page was built for publication: The complexity of finding common partitions of genomes with predefined block sizes
