The Approximability of the Exemplar Breakpoint Distance Problem

DOI10.1007/11775096_27zbMath1137.92336OpenAlexW2669318290MaRDI QIDQ5434407

Zhixiang Chen, Binhai Zhu, Bin Fu

Publication date: 4 January 2008

Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11775096_27

Mathematics Subject Classification ID

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

Related Items

Can a breakpoint graph be decomposed into none other than 2-cycles? ⋮ Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem ⋮ On the approximability of the exemplar adjacency number problem for genomes with gene repetitions ⋮ On the inapproximability of the exemplar conserved interval distance problem of genomes ⋮ Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials ⋮ A new approximation algorithm for contig-based genomic scaffold filling ⋮ Genomic Scaffold Filling: A Progress Report ⋮ Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling ⋮ Can a Breakpoint Graph be Decomposed into None Other Than 2-Cycles? ⋮ On the Approximability of Comparing Genomes with Duplicates ⋮ Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies ⋮ The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated ⋮ On the solution bound of two-sided scaffold filling ⋮ Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics ⋮ A 1.5-approximation algorithm for two-sided scaffold filling