The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated

DOI10.1007/978-3-642-00202-1_31zbMath1211.68509OpenAlexW1831121666MaRDI QIDQ3605511

Stéphane Vialette, Guillaume Blin, Guillaume Fertin, Florian Sikora

Publication date: 24 February 2009

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-00202-1_31

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Approximation algorithms (68W25) Computational methods for problems pertaining to biology (92-08)

Related Items (8)

Models and Algorithms for Genome Rearrangement with Positional Constraints ⋮ Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem ⋮ Genomic Scaffold Filling: A Progress Report ⋮ Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling ⋮ Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies ⋮ On the solution bound of two-sided scaffold filling ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics ⋮ A 1.5-approximation algorithm for two-sided scaffold filling

Cites Work

• On the Approximability of Comparing Genomes with Duplicates
• Color-coding
• The Approximability of the Exemplar Breakpoint Distance Problem
• On the Approximability of Comparing Genomes with Duplicates

This page was built for publication: The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated