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

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

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

• scientific article; zbMATH DE number 2119725 (Why is no real title available?)
• 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
• 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
• The greedy path-merging algorithm for contig scaffolding

Cited in

(8)

• On the solution bound of two-sided scaffold filling
• Genomic Scaffold Filling: A Progress Report
• The algorithm for the two-sided scaffold filling problem
• Approximation and nonapproximability for the one-sided scaffold filling problem
• A new approximation algorithm for contig-based genomic scaffold filling
• A 1.4-Approximation Algorithm for Two-Sided Scaffold Filling
• A 2.57-approximation algorithm for contig-based genomic scaffold filling
• An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies

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)