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