The greedy path-merging algorithm for contig scaffolding

DOI10.1145/585265.585267MaRDI QIDQ3455543zbMATH OpenOpenAlexFDO

Authors Knut Reinert, Eugene W. Myers, D. Huson

Publication date 7 December 2015

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/585265.585267

zbMATH Keywords

genome assembly

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Genetics and epigenetics (92D10)

Recommendations

• Global optimization for scaffolding and completing genome assemblies
• Instance guaranteed ratio on greedy heuristic for genome scaffolding
• Better approximation algorithms for scaffolding problems
• On the linearization of scaffolds sharing repeated contigs
• Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds

Cited in

(7)

• Global optimization for scaffolding and completing genome assemblies
• On the solution bound of two-sided scaffold filling
• A complexity and approximation framework for the maximization scaffolding problem
• A 1.5-approximation algorithm for two-sided scaffold filling
• Instance guaranteed ratio on greedy heuristic for genome scaffolding
• Notes on the \(\frac{6}{5}\)-approximation algorithm for one-sided scaffold filling
• A 1.4-approximation algorithm for two-sided scaffold filling

This page was built for publication: The greedy path-merging algorithm for contig scaffolding

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