Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds

DOI10.1007/s00453-021-00819-6OpenAlexW3158374272MaRDI QIDQ2037107

Mathias Weller, Tom Davot, Rodolphe Giroudeau, Dorine Tabary, Annie Chateau

Publication date: 30 June 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-03218029v1/file/main_llncs.pdf

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Uses Software

• SOPRA
• SCARPA
• GRASS
• Velvet
• BESST
• ScaffMatch
• Bambus 2

Cites Work

• Unnamed Item
• On the hardness of approximating minimum vertex cover
• Optimization, approximation, and complexity classes
• Which problems have strongly exponential complexity?
• On the linearization of scaffolds sharing repeated contigs
• New results about the linearization of scaffolds sharing repeated contigs
• A complexity and approximation framework for the maximization scaffolding problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?