A 1.5-approximation algorithm for two-sided scaffold filling

DOI10.1007/S00453-014-9938-9MaRDI QIDQ261348zbMATH OpenOpenAlexFDO

Authors Nan Liu, Daming Zhu, Haitao Jiang, Binhai Zhu

Publication date 23 March 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-014-9938-9

zbMATH Keywords

algorithmcomplexitygenomeperformance ratioscaffold

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32) Genetics and epigenetics (92D10)

Recommendations

• 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
• On the solution bound of two-sided scaffold filling
• Approximation and nonapproximability for the one-sided scaffold filling problem

Cites work

• Algorithms and Computation
• An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies
• Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies
• scientific article; zbMATH DE number 2119725 (Why is no real title available?)
• 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
• The greedy path-merging algorithm for contig scaffolding

Cited in

(9)

• On the solution bound of two-sided scaffold filling
• A new approximation algorithm for contig-based genomic scaffold filling
• Approximation and nonapproximability for the one-sided scaffold filling problem
• 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 2.57-approximation algorithm for contig-based genomic scaffold filling

This page was built for publication: A 1.5-approximation algorithm for two-sided scaffold filling

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