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 approximability of MEC. In particular, we show that MEC is in FPT when parameterized 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(lognm) 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.

Bonizzoni, P., Dondi, R., Klau, G., Pirola, Y., Pisanti, N., Zaccaria, S. (2015). On the fixed parameter tractability and approximability of the minimum error correction problem. In Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 - July 1, 2015, Proceedings (pp.100-113). Springer Verlag [10.1007/978-3-319-19929-0_9].

On the fixed parameter tractability and approximability of the minimum error correction problem

BONIZZONI, PAOLA;PIROLA, YURI;ZACCARIA, SIMONE
2015

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 approximability of MEC. In particular, we show that MEC is in FPT when parameterized 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(lognm) 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.
slide + paper
algorithm; haplotype assembly; computational complexity; fixed-parameter tractability
English
Annual Symposium on Combinatorial Pattern Matching, CPM 2015 29 June - 1 July
2015
Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 - July 1, 2015, Proceedings
9783319199283
2015
9133
100
113
reserved
Bonizzoni, P., Dondi, R., Klau, G., Pirola, Y., Pisanti, N., Zaccaria, S. (2015). On the fixed parameter tractability and approximability of the minimum error correction problem. In Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 - July 1, 2015, Proceedings (pp.100-113). Springer Verlag [10.1007/978-3-319-19929-0_9].
File in questo prodotto:
File Dimensione Formato  
conf-paper-15-cpm.pdf

Solo gestori archivio

Descrizione: Articolo principale
Dimensione 283.17 kB
Formato Adobe PDF
283.17 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/84752
Citazioni
  • Scopus 9
  • ???jsp.display-item.citation.isi??? ND
Social impact