A 1.5-approximation algorithm for two-sided scaffold filling

DOI10.1007/s00453-014-9938-9zbMath1336.68298OpenAlexW1968943918MaRDI QIDQ261348

Binhai Zhu, Haitao Jiang, Daming Zhu, Nan Liu

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

complexityalgorithmperformance ratiogenomescaffold

Mathematics Subject Classification ID

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

Related Items (4)

A new approximation algorithm for contig-based genomic scaffold filling ⋮ Genomic Scaffold Filling: A Progress Report ⋮ A 1.4-Approximation Algorithm for Two-Sided Scaffold Filling ⋮ On the solution bound of two-sided scaffold filling

Cites Work

• Unnamed Item
• On the inapproximability of the exemplar conserved interval distance problem of genomes
• Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies
• The greedy path-merging algorithm for contig scaffolding
• The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated
• On the Approximability of Comparing Genomes with Duplicates
• The Algorithm for the Two-Sided Scaffold Filling Problem
• An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies
• The Approximability of the Exemplar Breakpoint Distance Problem
• Algorithms and Computation

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