On the hardness of approximating Linearization of Scaffolds sharing Repeated Contigs
Résumé
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 they may not be uniquely convertible into sequences. Having introduced, in a previous work, 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. We also provide some practical tests.
Domaines
Bio-informatique [q-bio.QM]
Fichier principal
recomb-cg_2018_on_the_hardness_of_approximating_linearization_of_scaffolds_sharing_repeated_contigs.pdf (542.91 Ko)
Télécharger le fichier
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...