Approximation and nonapproximability for the one-sided scaffold filling problem

DOI10.1007/978-3-319-21398-9_20zbMATH Open1465.92070OpenAlexW1158677828MaRDI QIDQ3196388FDOQ3196388

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

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

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)

Cites Work

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

Cited In (9)

• Title not available (Why is that?)
• 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
• An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies

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)