D. Aguiar and S. Istrail, HapCompass: A Fast Cycle Basis Algorithm for Accurate Haplotype Assembly of Sequence Data, Journal of Computational Biology, vol.19, issue.6, pp.577-590, 2012.
DOI : 10.1089/cmb.2012.0084

D. Aguiar and S. Istrail, Haplotype assembly in polyploid genomes and identical by descent shared tracts, Bioinformatics, vol.29, issue.13, pp.352-360, 2013.
DOI : 10.1093/bioinformatics/btt213
URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3694639

M. Aldinucci, A. Bracciali, and T. Marschall, High-Performance Haplotype Assembly, Computational Intelligence Methods for Bioinformatics and Biostatistics -11th International Meeting, CIBB 2014, pp.245-258, 2014.
DOI : 10.1016/j.compbiolchem.2005.05.001
URL : https://hal.archives-ouvertes.fr/hal-01526652

G. Ausiello, P. Crescenzi, and G. Gambosi, Complexity and approximation: Combinatorial optimization problems and their approximability properties, 1999.
DOI : 10.1007/978-3-642-58412-1

V. Bansal and V. Bafna, HapCUT: an efficient and accurate algorithm for the haplotype assembly problem, Bioinformatics, vol.24, issue.16, pp.153-159, 2008.
DOI : 10.1093/bioinformatics/btn298
URL : http://bioinformatics.oxfordjournals.org/cgi/content/short/24/16/i153

E. Bao, T. Jiang, and T. Girke, BRANCH: boosting RNA-Seq assemblies with partial or related genomic sequences, Bioinformatics, vol.29, issue.10, pp.1250-1259, 2013.
DOI : 10.1093/bioinformatics/btt127
URL : http://bioinformatics.oxfordjournals.org/cgi/content/short/29/10/1250

N. Beerenwinkel, S. Beretta, and P. Bonizzoni, Covering pairs in directed acyclic graphs, Language and Automata Theory and Applications (LATA), pp.126-137, 2014.
DOI : 10.1007/978-3-319-04921-2_10
URL : http://arxiv.org/abs/1310.5037

N. Beerenwinkel, S. Beretta, and P. Bonizzoni, Covering Pairs in Directed Acyclic Graphs, The Computer Journal, vol.58, issue.7, pp.1673-1686, 2015.
DOI : 10.1093/comjnl/bxu116
URL : http://arxiv.org/abs/1310.5037

E. Berger, D. Yorukoglu, and J. Peng, HapTree: A Novel Bayesian Framework for Single Individual Polyplotyping Using NGS Data, PLoS Computational Biology, vol.26, issue.3, 2014.
DOI : 10.1371/journal.pcbi.1003502.t001
URL : http://doi.org/10.1371/journal.pcbi.1003502

P. Bonizzoni, D. Vedova, G. Dondi, and R. , The Haplotyping problem: An overview of computational models and solutions, Journal of Computer Science and Technology, vol.710, issue.5, pp.675-688, 2003.
DOI : 10.1007/BF02945456

P. Bonizzoni, R. Dondi, and G. W. Klau, On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction Problem, 26th Annual Symposium on Combinatorial Pattern Matching (CPM), pp.100-113, 2015.
DOI : 10.1007/978-3-319-19929-0_9
URL : https://hal.archives-ouvertes.fr/hal-01246260

B. Browning and S. Browning, Haplotypic analysis of Wellcome Trust Case Control Consortium data, Human Genetics, vol.316, issue.3, pp.273-280, 2008.
DOI : 10.1007/s00439-008-0472-1
URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2384233

Z. Z. Chen, F. Deng, W. , and L. , Exact algorithms for haplotype assembly from whole-genome sequence data, Bioinformatics, vol.29, issue.16, pp.1938-1983, 2013.
DOI : 10.1093/bioinformatics/btt349

R. Cilibrasi, L. Van-iersel, and S. Kelk, The Complexity of the Single Individual SNP Haplotyping Problem, Algorithmica, vol.49, issue.1, pp.13-36, 2007.
DOI : 10.1007/s00453-007-0029-z

S. Das and H. Vikalo, SDhaP: haplotype assembly for diploids and polyploids via semi-definite programming, BMC Genomics, vol.14, issue.9, 2015.
DOI : 10.1186/s12864-015-1408-5
URL : http://doi.org/10.1186/s12864-015-1408-5

R. Dondi, New results for the Longest Haplotype Reconstruction problem, Discrete Applied Mathematics, vol.160, issue.9, pp.1299-1310, 2012.
DOI : 10.1016/j.dam.2011.10.014
URL : http://dx.doi.org/10.1016/j.dam.2011.10.014

R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity. Texts in Computer Science, 2013.
DOI : 10.1007/978-1-4471-5559-1
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.456.2729

J. Duitama, Fosmid-based whole genome haplotyping of a HapMap trio child: evaluation of Single Individual Haplotyping techniques, Nucleic Acids Research, vol.40, issue.5, pp.2041-2053, 2012.
DOI : 10.1093/nar/gkr1042

N. Eriksson, L. Pachter, and Y. Mitsuya, Viral Population Estimation Using Pyrosequencing, PLoS Computational Biology, vol.25, issue.5, 2008.
DOI : 10.1371/journal.pcbi.1000074.s004
URL : http://doi.org/10.1371/journal.pcbi.1000074

P. Fouilhoux and A. Mahjoub, Solving VLSI design and DNA sequencing problems using bipartization of graphs, Computational Optimization and Applications, vol.291, issue.2, pp.749-781, 2012.
DOI : 10.1007/s10589-010-9355-1
URL : https://hal.archives-ouvertes.fr/hal-01185262

D. R. Fulkerson, Note on Dilworth's decomposition theorem for partially ordered sets, Proc. American Mathematical Society, vol.7, pp.701-702, 1956.
DOI : 10.2307/2033375
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.226.652

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

N. Garg, V. V. Vazirani, Y. , and M. , Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications, SIAM Journal on Computing, vol.25, issue.2, pp.235-251, 1996.
DOI : 10.1137/S0097539793243016
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.3217

F. Geraci, A comparison of several algorithms for the single individual SNP haplotyping reconstruction problem, Bioinformatics, vol.26, issue.18, pp.2217-2225, 2010.
DOI : 10.1093/bioinformatics/btq411

J. Guo, J. Gramm, and F. Hüffner, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Journal of Computer and System Sciences, vol.72, issue.8, pp.1386-1396, 2006.
DOI : 10.1016/j.jcss.2006.02.001
URL : http://doi.org/10.1016/j.jcss.2006.02.001

B. V. Halldórsson, D. Aguiar, and S. Istrail, HAPLOTYPE PHASING BY MULTI-ASSEMBLY OF SHARED HAPLOTYPES: PHASE-DEPENDENT INTERACTIONS BETWEEN RARE VARIANTS, PSB, pp.88-99, 2011.
DOI : 10.1142/9789814335058_0010

D. He, A. Choi, and K. Pipatsrisawat, Optimal algorithms for haplotype assembly from whole-genome sequence data, Bioinformatics, vol.26, issue.12, pp.183-190, 2010.
DOI : 10.1093/bioinformatics/btq215
URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2881399

Y. Jiao, J. Xu, and M. Li, On the k-Closest Substring and k-Consensus Pattern Problems, In CPM LNCS, vol.3109, pp.130-144, 2004.
DOI : 10.1007/978-3-540-27801-6_10
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.9205

S. Khot, On the power of unique 2-prover 1-round games, STOC, pp.767-775, 2002.

J. Kleinberg, C. Papadimitriou, and P. And-raghavan, Segmentation problems, STOC, pp.473-482, 1998.

G. Lancia, V. Bafna, and S. Istrail, SNPs Problems, Complexity, and Algorithms, ESA, pp.182-193, 2001.
DOI : 10.1007/3-540-44676-1_15

R. Lippert, R. Schwartz, and G. Lancia, Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem, Briefings in Bioinformatics, vol.3, issue.1, pp.23-31, 2002.
DOI : 10.1093/bib/3.1.23
URL : http://bib.oxfordjournals.org/cgi/content/short/3/1/23

J. Meidanis, O. Porto, and G. P. Telles, On the consecutive ones property, Discrete Applied Mathematics, vol.88, issue.1-3, pp.325-354, 1998.
DOI : 10.1016/S0166-218X(98)00078-X
URL : http://doi.org/10.1016/s0166-218x(98)00078-x

R. Ostrovsky and Y. Rabani, Polynomial-time approximation schemes for geometric min-sum median clustering, Journal of the ACM, vol.49, issue.2, pp.139-156, 2002.
DOI : 10.1145/506147.506149

M. Patterson, T. Marschall, and N. Pisanti, WhatsHap: Haplotype Assembly for Future-Generation Sequencing Reads, RECOMB, pp.237-249, 2014.
DOI : 10.1007/978-3-319-05269-4_19
URL : https://hal.archives-ouvertes.fr/hal-01225988

M. Patterson, T. Marschall, and N. Pisanti, : Weighted Haplotype Assembly for Future-Generation Sequencing Reads, Journal of Computational Biology, vol.22, issue.6, pp.498-509, 2015.
DOI : 10.1089/cmb.2014.0157

Y. Pirola, P. Bonizzoni, and T. Jiang, An Efficient Algorithm for Haplotype Inference on Pedigrees with Recombinations and Mutations, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.9, issue.1, pp.12-25, 2012.
DOI : 10.1109/TCBB.2011.51

Y. Pirola, D. Vedova, G. Bonizzoni, and P. , Haplotype-based prediction of gene alleles using pedigrees and SNP genotypes, Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics, BCB'13, pp.33-41, 2013.
DOI : 10.1145/2506583.2506592

Y. Pirola, S. Zaccaria, and R. Dondi, HapCol: accurate and memory-efficient haplotype assembly from long reads, Bioinformatics, vol.32, issue.11, 2015.
DOI : 10.1093/bioinformatics/btv495
URL : https://hal.archives-ouvertes.fr/hal-01225984

B. Reed, K. Smith, and A. Vetta, Finding odd cycle transversals, Operations Research Letters, vol.32, issue.4, pp.299-301, 2004.
DOI : 10.1016/j.orl.2003.10.009
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.6357

R. Rizzi, A. Tomescu, and V. Mäkinen, On the complexity of Minimum Path Cover with Subpath Constraints for multi-assembly, BMC Bioinformatics, vol.15, issue.Suppl 9, p.5, 2014.
DOI : 10.1145/115234.115366

L. Song and L. Florea, CLASS: constrained transcript assembly of RNA-seq reads, BMC Bioinformatics, vol.14, issue.Suppl 5, pp.1-8, 2013.
DOI : 10.1093/bioinformatics/btp120
URL : http://doi.org/10.1186/1471-2105-14-s5-s14

C. Trapnell, B. A. Williams, and G. Pertea, Transcript assembly and quantification by RNA-Seq reveals unannotated transcripts and isoform switching during cell differentiation, Nature Biotechnology, vol.25, issue.5, pp.516-520, 2010.
DOI : 10.1038/nbt.1621
URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3146043

R. S. Wang, L. Y. Wu, and Z. P. Li, Haplotype reconstruction from SNP fragments by minimum error correction, Bioinformatics, vol.21, issue.10, pp.2456-2462, 2005.
DOI : 10.1093/bioinformatics/bti352
URL : http://bioinformatics.oxfordjournals.org/cgi/content/short/21/10/2456

M. Yannakakis, Node-and edge-deletion NP-complete problems, Proceedings of the tenth annual ACM symposium on Theory of computing , STOC '78, pp.253-264, 1978.
DOI : 10.1145/800133.804355