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

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

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

• Algorithms and Computation
• Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2119725 (Why is no real title available?)
• 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 algorithm for the two-sided scaffold filling problem
• The Approximability of the Exemplar Breakpoint Distance Problem
• The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated

Cited in

(10)

• On the solution bound of two-sided scaffold filling
• A new approximation algorithm for contig-based genomic scaffold filling
• A 1.5-approximation algorithm for two-sided scaffold filling
• Genomic scaffold filling: a progress report
• Notes on the \(\frac{6}{5}\)-approximation algorithm for one-sided scaffold filling
• A 1.4-approximation algorithm for two-sided scaffold filling
• The algorithm for the two-sided scaffold filling problem
• An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies
• A rearrangement distance for fully-labelled trees
• A 2.57-approximation algorithm for contig-based genomic 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)