On the solution bound of two-sided scaffold filling

DOI10.1016/J.TCS.2021.04.024zbMATH Open1504.68296OpenAlexW3158152626MaRDI QIDQ2034400FDOQ2034400

Authors: Jingjing Ma, Daming Zhu, Haitao Jiang, Binhai Zhu 

Publication date: 22 June 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.04.024

Recommendations

• A 1.4-approximation algorithm for two-sided scaffold filling
• A 1.5-approximation algorithm for two-sided scaffold filling
• The algorithm for the two-sided scaffold filling problem
• Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling
• Approximation and nonapproximability for the one-sided scaffold filling problem

zbMATH Keywords

computational complexitygenomeperformance ratioscaffold filling

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Algorithms on strings (68W32)

Cites Work

• On the inapproximability of the exemplar conserved interval distance problem of genomes
• A 1.5-approximation algorithm for two-sided scaffold filling
• 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 Approximability of the Exemplar Breakpoint Distance Problem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Title not available (Why is that?)
• Fixed-parameter algorithms for scaffold filling
• The complexity of calculating exemplar distances
• Title not available (Why is that?)
• Local optimality and its application on independent sets for \(k\)-claw free graphs
• A polynomial time solution for permutation scaffold filling
• Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling
• A 1.4-Approximation Algorithm for Two-Sided Scaffold Filling
• Genomic scaffold filling revisited

Cited In (1)

• A 1.5-approximation algorithm for two-sided scaffold filling

This page was built for publication: On the solution bound of two-sided scaffold filling

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