On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction Problem

Abstract : Haplotype assembly is the computational problem of reconstructing the two parental copies, called haplotypes, of each chromosome starting from sequencing reads, called fragments, possibly affected by sequencing errors. Minimum Error Correction (MEC) is a prominent computational problem for haplotype assembly and, given a set of fragments , aims at reconstructing the two haplotypes by applying the minimum number of base corrections. By using novel combinatorial properties of MEC instances, we are able to provide new results on the fixed-parameter tractability and approx-imability of MEC. In particular, we show that MEC is in FPT when para-meterized by the number of corrections, and, on " gapless " instances, it is in FPT also when parameterized by the length of the fragments, whereas the result known in literature forces the reconstruction of complementary haplotypes. Then, we show that MEC cannot be approximated within any constant factor while it is approximable within factor O(log nm) where nm is the size of the input. Finally, we provide a practical 2-approximation algorithm for the Binary MEC, a variant of MEC that has been applied in the framework of clustering binary data.
Type de document :
Communication dans un congrès
26th Annual Symposium on Combinatorial Pattern Matching (CPM), Jun 2015, Ischia, Italy. 〈10.1007/978-3-319-19929-0〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01246260
Contributeur : Marie-France Sagot <>
Soumis le : mercredi 24 mai 2017 - 11:08:34
Dernière modification le : mercredi 11 avril 2018 - 01:52:42
Document(s) archivé(s) le : lundi 28 août 2017 - 17:20:48

Fichier

Auth-CPM15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Paola Bonizzoni, Riccardo Dondi, Gunnar W Klau, Yuri Pirola, Nadia Pisanti, et al.. On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction Problem. 26th Annual Symposium on Combinatorial Pattern Matching (CPM), Jun 2015, Ischia, Italy. 〈10.1007/978-3-319-19929-0〉. 〈hal-01246260〉

Partager

Métriques

Consultations de la notice

206

Téléchargements de fichiers

38