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

DOI10.1007/s10878-007-9077-1zbMath1136.92028MaRDI 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 algorithm; weak approximation; genome rearrangement

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

92C40: Biochemistry, molecular biology

92D10: Genetics and epigenetics

65Y20: Complexity and performance of numerical algorithms

92-08: Computational methods for problems pertaining to biology

Related Items

Genomic Scaffold Filling: A Progress Report, Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling, A Retrospective on Genomic Preprocessing for Comparative Genomics, A 1.5-approximation algorithm for two-sided scaffold filling, 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, On the solution bound of two-sided scaffold filling, A NOTE ON COMPLEXITY OF GENETIC MUTATIONS, Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies, Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem

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