Skip to Main content Skip to Navigation
Conference papers

New results about the linearization of scaffolds sharing repeated contigs

Abstract : Solutions to genome scaffolding problems can be represented as paths and cycles in a "solution graph". However, when working with repetitions, such solution graphs may contain branchings and, thus, they may not be uniquely convertible into sequences. Having introduced various ways of extracting the unique parts of such solutions, we extend previously known NP-hardness results to the case that the solution graph is planar, bipartite, and subcubic, and show that there is no PTAS in this case.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Tom Davot <>
Submitted on : Monday, October 22, 2018 - 9:20:56 AM
Last modification on : Tuesday, June 8, 2021 - 11:04:02 AM
Long-term archiving on: : Wednesday, January 23, 2019 - 12:46:45 PM


Files produced by the author(s)


  • HAL Id : lirmm-01900389, version 1


Dorine Tabary, Tom Davot, Mathias Weller, Annie Chateau, Rodolphe Giroudeau. New results about the linearization of scaffolds sharing repeated contigs. COCOA: Conference on Combinatorial Optimization and Applications, Dec 2018, Atlanta, United States. ⟨lirmm-01900389v1⟩



Record views


Files downloads