The Approximability of the Exemplar Breakpoint Distance Problem

DOI10.1007/11775096_27MaRDI QIDQ5434407zbMATH OpenOpenAlexFDO

Authors Zhi-Xiang Chen, Bin Fu, Binhai Zhu

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

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

Recommendations

• The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated
• Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems
• On the inapproximability of the exemplar conserved interval distance problem of genomes
• On the approximability of the exemplar adjacency number problem for genomes with gene repetitions
• Lower Bounds on the Approximation of the Exemplar Conserved Interval Distance Problem of Genomes

Cited in

(24)

• On the solution bound of two-sided scaffold filling
• A new approximation algorithm for contig-based genomic scaffold filling
• On the inapproximability of the exemplar conserved interval distance problem of genomes
• A 1.5-approximation algorithm for two-sided scaffold filling
• Can a breakpoint graph be decomposed into none other than 2-cycles?
• A fast and exact algorithm for the exemplar breakpoint distance
• Erratum: ``The approximability of the exemplar breakpoint distance problem
• Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies
• Approximation and nonapproximability for the one-sided scaffold filling problem
• Non-breaking Similarity of Genomes with Gene Repetitions
• Breakpoint Distance and PQ-Trees
• Lower Bounds on the Approximation of the Exemplar Conserved Interval Distance Problem of Genomes
• The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated
• On the Approximability of Comparing Genomes with Duplicates
• Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems
• Revisiting the minimum breakpoint linearization problem
• On the approximability of the exemplar adjacency number problem for genomes with gene repetitions
• 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?
• A retrospective on genomic preprocessing for comparative genomics
• On the Approximability of Comparing Genomes with Duplicates
• The complexity of calculating exemplar distances
• Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance

This page was built for publication: The Approximability of the Exemplar Breakpoint Distance Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5434407)