A new approximation algorithm for contig-based genomic scaffold filling

DOI10.1016/J.TCS.2020.05.017MaRDI QIDQ2220846zbMATH OpenOpenAlexFDO

Authors Guanlan Tan, Qilong Feng, Xiangzhong Meng, Jianxin Wang

Publication date 25 January 2021

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

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

zbMATH Keywords

approximation algorithmgenomic scaffold fillingmaximum matching

Mathematics Subject Classification ID

Approximation algorithms (68W25) Genetics and epigenetics (92D10)

Recommendations

• A 1.5-approximation algorithm for two-sided scaffold filling
• Approximation and nonapproximability for the one-sided scaffold filling problem
• An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies
• A 1.4-approximation algorithm for two-sided scaffold filling
• Genomic scaffold filling revisited

Cites work

• A 1.4-approximation algorithm for two-sided scaffold filling
• A 1.5-approximation algorithm for two-sided scaffold filling
• A polynomial time solution for permutation scaffold filling
• Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies
• Fixed-parameter algorithms for scaffold filling
• Genomic scaffold filling revisited
• Genomic scaffold filling: a progress report
• scientific article; zbMATH DE number 7203332 (Why is no real title available?)
• Non-breaking Similarity of Genomes with Gene Repetitions
• Notes on the $$\frac{6}{5}$$ -Approximation Algorithm for One-Sided Scaffold Filling
• The Approximability of the Exemplar Breakpoint Distance Problem

Cited in

(4)

• New results about the linearization of scaffolds sharing repeated contigs
• Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies
• Notes on the \(\frac{6}{5}\)-approximation algorithm for one-sided scaffold filling
• A 2.57-approximation algorithm for contig-based genomic scaffold filling

This page was built for publication: A new approximation algorithm for contig-based genomic scaffold filling

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