On the inapproximability of the exemplar conserved interval distance problem of genomes
From MaRDI portal
Publication:2427442
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
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