Instance Guaranteed Ratio on Greedy Heuristic for Genome Scaffolding

DOI10.1007/978-3-319-48749-6_22zbMath1484.92065OpenAlexW2540368177MaRDI QIDQ2958322

Annie Chateau, Rodolphe Giroudeau, Mathias Weller, Clément Dallard

Publication date: 1 February 2017

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-48749-6_22

zbMATH Keywords

approximation ratiogreedy heuristicgenome scaffolding

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Genetics and epigenetics (92D10)

Uses Software

• SOPRA
• SCARPA
• GRASS
• Samtools
• BESST
• Bambus 2
• BWA

Cites Work

• Unnamed Item
• Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
• A complexity and approximation framework for the maximization scaffolding problem
• The greedy path-merging algorithm for contig scaffolding
• On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs

This page was built for publication: Instance Guaranteed Ratio on Greedy Heuristic for Genome Scaffolding