Tom Davot, Annie Chateau, Rodolphe Giroudeau and Mathias Weller. On the hardness of approximating 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 graph 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 the APX-completeness in this case.

return to ‘Accepted Papers’

Leave a Reply

Your email address will not be published. Required fields are marked *