Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling

DOI10.1007/978-3-319-39817-4_15zbMath1475.68469OpenAlexW2476177376MaRDI QIDQ4632180

Jingjing Ma, Haitao Jiang

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-39817-4_15

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Genetics and epigenetics (92D10) Approximation algorithms (68W25) Computational methods for problems pertaining to biology (92-08) Algorithms on strings (68W32)

Related Items

A new approximation algorithm for contig-based genomic scaffold filling ⋮ 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 complexity of unsigned translocation distance
• On the inapproximability of the exemplar conserved interval distance problem of genomes
• Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies
• Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem
• 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