Approximation and nonapproximability for the one-sided scaffold filling problem

DOI10.1007/978-3-319-21398-9_20MaRDI QIDQ3196388zbMATH OpenOpenAlexFDO

Authors Haitao Jiang, Jingjing Ma, Junfeng Luan, Daming Zhu

Publication date 29 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-21398-9_20

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies
• The algorithm for the two-sided scaffold filling problem
• A 1.4-approximation algorithm for two-sided scaffold filling
• A 1.5-approximation algorithm for two-sided scaffold filling
• Genomic scaffold filling revisited

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2119725 (Why is no real title available?)
• Algorithms and Computation
• Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Non-breaking Similarity of Genomes with Gene Repetitions
• On Syntactic versus Computational Views of Approximability
• On the Approximability of Comparing Genomes with Duplicates
• On the inapproximability of the exemplar conserved interval distance problem of genomes
• The Approximability of the Exemplar Breakpoint Distance Problem
• The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated
• The algorithm for the two-sided scaffold filling problem

Cited in

(9)

• An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies
• scientific article; zbMATH DE number 7559196 (Why is no real title available?)
• A 1.5-approximation algorithm for two-sided scaffold filling
• A new approximation algorithm for contig-based genomic scaffold filling
• The algorithm for the two-sided scaffold filling problem
• On the solution bound of two-sided scaffold filling
• Genomic Scaffold Filling: A Progress Report
• A 2.57-approximation algorithm for contig-based genomic scaffold filling
• Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling

This page was built for publication: Approximation and nonapproximability for the one-sided scaffold filling problem

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