On the inapproximability of the exemplar conserved interval distance problem of genomes

DOI10.1007/s10878-007-9077-1zbMath1136.92028OpenAlexW2019300909MaRDI QIDQ2427442

Zhixiang Chen, Bin Fu, Binhai Zhu, Richard H. Fowler

Publication date: 13 May 2008

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-007-9077-1

zbMATH Keywords

approximation algorithmweak approximationgenome rearrangement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Biochemistry, molecular biology (92C40) Genetics and epigenetics (92D10) Complexity and performance of numerical algorithms (65Y20) Computational methods for problems pertaining to biology (92-08)

Related Items (10)

A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem ⋮ On the approximability of the exemplar adjacency number problem for genomes with gene repetitions ⋮ Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials ⋮ 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

• Unnamed Item
• Unnamed Item
• Genomic distances under deletions and insertions
• On the Similarity of Sets of Permutations and Its Applications to Genome Comparison
• Transforming cabbage into turnip
• Non-breaking Similarity of Genomes with Gene Repetitions
• Lower Bounds on the Approximation of the Exemplar Conserved Interval Distance Problem of Genomes
• The Approximability of the Exemplar Breakpoint Distance Problem
• Computing and Combinatorics
• Computing and Combinatorics

This page was built for publication: On the inapproximability of the exemplar conserved interval distance problem of genomes