P. N. Ariyaratne and W. K. Sung, PE-Assembler: de novo assembler using short paired-end reads, Bioinformatics, vol.27, issue.2, pp.167-182, 2011.
DOI : 10.1093/bioinformatics/btq626

S. Batzoglou, D. B. Jaffe, K. Stanley, J. Butler, S. Gnerre et al., ARACHNE: A Whole-Genome Shotgun Assembler, Genome Research, vol.12, issue.1
DOI : 10.1101/gr.208902

M. Boetzer, C. V. Henkel, H. J. Jansen, D. Butler, and W. Pirovano, Scaffolding pre-assembled contigs using SSPACE, Bioinformatics, vol.27, issue.4, pp.578-2011
DOI : 10.1093/bioinformatics/btq683

S. Boisvert, F. Laviolette, and J. Corbeil, Ray: Simultaneous Assembly of Reads from a Mix of High-Throughput Sequencing Technologies, Journal of Computational Biology, vol.17, issue.11, pp.1519-1533, 2010.
DOI : 10.1089/cmb.2009.0238

D. Bryant, W. K. Wong, and T. Mockler, QSRA ??? a quality-value guided de novo short read assembler, BMC Bioinformatics, vol.10, issue.1, pp.69-75, 2009.
DOI : 10.1186/1471-2105-10-69

C. Lander, D. B. Nusbaum, and . Jaffe, ALLPATHS: de novo assembly of wholegenome shotgun microreads, Genome Research, vol.18, issue.82, pp.810-820, 2008.

M. J. Chaisson, D. Brinza, and P. A. Pevzner, De novo fragment assembly with short mate-paired reads: Does the read length matter?, Genome Research, vol.19, issue.2, pp.336-346, 2009.
DOI : 10.1101/gr.079053.108

J. A. Chapman, I. Ho, S. Sunkara, S. Luo, G. P. Schroth et al., Meraculous: De Novo Genome Assembly with Short Paired-End Reads, PLoS ONE, vol.21, issue.8, pp.23501-23516, 2011.
DOI : 10.1371/journal.pone.0023501.s003

R. Chikhi, G. Chapuis, and D. Lavenier, Parallel and memory-efficient reads indexing for genome assembly, PBC, vol.64, pp.58-112, 2011.
URL : https://hal.archives-ouvertes.fr/inria-00637536

R. Chikhi and D. Lavenier, Paired-end read length lower bounds for genome re-sequencing, BMC Bioinformatics, vol.10, issue.Suppl 13, pp.2-111, 2009.
DOI : 10.1186/1471-2105-10-S13-O2

URL : https://hal.archives-ouvertes.fr/inria-00426856

R. Chikhi and D. Lavenier, Localized Genome Assembly from Reads to Scaffolds: Practical Traversal of the Paired String Graph, Algorithms in Bioinformatics, vol.18, issue.5, pp.39-48, 2011.
DOI : 10.1101/gr.074492.107

URL : https://hal.archives-ouvertes.fr/inria-00637535

T. C. Conway and A. J. Bromage, Succinct data structures for assembling large genomes, Bioinformatics, vol.27, issue.4, pp.479-57, 2011.
DOI : 10.1093/bioinformatics/btq697

URL : http://arxiv.org/abs/1008.2555

E. D. Demaine and M. L. Demaine, Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity. Graphs and Combinatorics, pp.195-208, 2007.
DOI : 10.1007/s00373-007-0713-4

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.3689

N. Donmez and M. Brudno, Hapsembler: An Assembler for Highly Polymorphic Genomes, Research in Computational Molecular Biology, pp.38-52
DOI : 10.1007/978-3-642-20036-6_5

D. A. Earl, K. Bradnam, J. S. John, A. Darling, D. Lin et al., Assemblathon 1: A competitive assessment of de novo short read assembly methods, Genome Research, vol.21, issue.12, pp.88-96, 2011.
DOI : 10.1101/gr.126599.111

URL : https://hal.archives-ouvertes.fr/inria-00637571

J. Edmonds and E. L. Johnson, Matching, Euler tours and the Chinese postman, Mathematical Programming, vol.1, issue.Suppl. 1, pp.88-124, 1973.
DOI : 10.1007/BF01580113

P. Ferragina and G. Manzini, Indexing compressed text, Journal of the ACM, vol.52, issue.4, pp.552-581, 2005.
DOI : 10.1145/1082036.1082039

S. Gao, N. Nagarajan, and W. K. Sung, Opera: reconstructing optimal genomic scaffolds with high-throughput paired-end sequences, Research in Computational Molecular Biology, pp.437-451
DOI : 10.1089/cmb.2011.0170

URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3216105

S. Gnerre, I. Maccallum, D. Przybylski, F. J. Ribeiro, J. N. Burton et al., High-quality draft assemblies of mammalian genomes from massively parallel sequence data, Proceedings of the National Academy of Sciences, vol.108, issue.4, pp.1513-2011
DOI : 10.1073/pnas.1017351108

M. Hossain, N. Azimi, and S. Skiena, Crystallizing short-read assemblies around seeds, BMC Bioinformatics, vol.10, issue.Suppl 1, pp.16-49, 2009.
DOI : 10.1186/1471-2105-10-S1-S16

URL : http://doi.org/10.1186/1471-2105-10-s1-s16

D. Huson, K. Reinert, and E. W. Myers, The greedy path-merging algorithm for contig scaffolding, Journal of the ACM, vol.49, issue.5, pp.603-615, 2002.
DOI : 10.1145/585265.585267

B. Jackson, P. Schnable, and S. Aluru, Parallel short sequence assembly of transcriptomes, BMC Bioinformatics, vol.10, issue.Suppl 1, pp.14-57, 2009.
DOI : 10.1186/1471-2105-10-S1-S14

D. S. Johnson and M. R. Garey, Computers and intractability: A guide to the theory of NP-completeness. Freeman&Co, p.32, 1979.

J. Karkkainen and P. Sanders, Simple Linear Work Suffix Array Construction
DOI : 10.1007/3-540-45061-0_73

D. R. Kelley, M. C. Schatz, and S. L. Salzberg, Quake: quality-aware detection and correction of sequencing errors, Genome Biology, vol.11, issue.11, pp.116-2010
DOI : 10.1101/gr.088013.108

S. R. Kosaraju and A. L. Delcher, Large-scale assembly of DNA strings and space-efficient construction of suffix trees, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pp.169-177, 1995.

V. Kundeti, S. Rajasekaran, H. Dinh, M. Vaughn, and V. Thapar, Efficient parallel and out of core algorithms for constructing large bi-directed de Bruijn graphs, BMC Bioinformatics, vol.11, issue.1, pp.560-2010
DOI : 10.1186/1471-2105-11-560

H. Li, B. Handsaker, A. Wysoker, T. Fennell, J. Ruan et al., The Sequence Alignment/Map format and SAMtools, Bioinformatics, vol.25, issue.16, pp.252078-83, 2009.
DOI : 10.1093/bioinformatics/btp352

R. Li, H. Zhu, J. Ruan, W. Qian, X. Fang et al., De novo assembly of human genomes with massively parallel short read sequencing, Genome Research, vol.20, issue.2, pp.265-313, 2010.
DOI : 10.1101/gr.097261.109

A. L. Mcguire, M. K. Cho, S. E. Mcguire, and T. Caulfield, The future of personal genomics, Science, issue.5845 8, p.3171687, 2007.

P. Medvedev, K. Georgiou, G. Myers, and M. Brudno, Computability of Models for Sequence Assembly, Algorithms in Bioinformatics, vol.34, pp.289-301, 2007.
DOI : 10.1007/978-3-540-74126-8_27

P. Medvedev, S. Pham, M. Chaisson, G. Tesler, and P. Pevzner, Paired de bruijn graphs: a novel approach for incorporating mate pair information into genome assemblers, Research in Computational Molecular Biology, pp.238-251

J. R. Miller, S. Koren, and G. Sutton, Assembly algorithms for next-generation sequencing data, Genomics, vol.95, issue.6, pp.315-327, 2010.
DOI : 10.1016/j.ygeno.2010.03.001

URL : http://doi.org/10.1016/j.ygeno.2010.03.001

M. Mitzenmacher and E. Upfal, Probability and computing: Randomized algorithms and probabilistic analysis, p.102, 2005.
DOI : 10.1017/CBO9780511813603

E. W. Myers, Toward Simplifying and Accurately Formulating Fragment Assembly, Journal of Computational Biology, vol.2, issue.2, pp.275-290, 1995.
DOI : 10.1089/cmb.1995.2.275

N. Nagarajan and M. Pop, Parametric Complexity of Sequence Assembly: Theory and Applications to Next Generation Sequencing, Journal of Computational Biology, vol.16, issue.7, pp.897-908, 2009.
DOI : 10.1089/cmb.2009.0005

D. Okanohara and K. Sadakane, Practical entropy-compressed rank/select dictionary . Arxiv preprint cs/0610001, p.57, 2006.
DOI : 10.1137/1.9781611972870.6

URL : http://arxiv.org/abs/cs/0610001

Y. Peng, H. Leung, S. Yiu, and F. Chin, IDBA ??? A Practical Iterative de Bruijn Graph De Novo Assembler, Research in Computational Molecular Biology, pp.426-440
DOI : 10.1007/978-3-642-12683-3_28

P. Peterlongo and R. Chikhi, Mapsembler, targeted and micro assembly of large NGS datasets on a desktop computer, BMC Bioinformatics, vol.13, issue.1, pp.48-76, 2012.
DOI : 10.1186/gb-2011-12-1-r6

URL : https://hal.archives-ouvertes.fr/hal-00784408

M. Pop, D. S. Kosack, and S. L. Salzberg, Hierarchical Scaffolding With Bambus, Genome Research, vol.14, issue.1
DOI : 10.1101/gr.1536204

URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC314292

M. Pop, S. L. Salzberg, and M. Shumway, Genome sequence assembly: algorithms and issues, Computer, vol.35, issue.7, pp.47-54, 2002.
DOI : 10.1109/MC.2002.1016901

R. Raman, V. Raman, and S. R. Satti, -ary trees, prefix sums and multisets, ACM Transactions on Algorithms, vol.3, issue.4, pp.43-57, 2007.
DOI : 10.1145/1290672.1290680

URL : https://hal.archives-ouvertes.fr/hal-01087676

S. L. Salzberg, A. M. Phillippy, A. Zimin, D. Puiu, T. Magoc et al., GAGE: A critical evaluation of genome assemblies and assembly algorithms, Genome Research, vol.22, issue.3, pp.2011-109
DOI : 10.1101/gr.131383.111

F. Sanger, S. Nicklen, and A. Coulson, DNA sequencing with chain-terminating inhibitors, Proceedings of the National Academy of Sciences, vol.74, issue.12, pp.5463-5470, 1977.
DOI : 10.1073/pnas.74.12.5463

URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC431765

B. Schmidt, R. Sinha, B. Beresford-smith, and S. J. Puglisi, A fast hybrid short read fragment assembly algorithm, Bioinformatics, vol.25, issue.17, pp.2279-75, 2009.
DOI : 10.1093/bioinformatics/btp374

T. Shea, L. Williams, S. Young, C. Nusbaum, D. Jaffe et al., ALLPATHS 2: small genomes assembled accurately and with high continuity from short paired reads, Genome Biology, vol.10, issue.87, pp.103-63, 2009.

J. Shendure and H. Ji, Next-generation DNA sequencing, Nature Biotechnology, vol.105, issue.10, pp.1135-1145, 2008.
DOI : 10.1038/nbt1486

J. T. Simpson and R. Durbin, Efficient construction of an assembly string graph using the FM-index, Bioinformatics, vol.26, issue.12, pp.367-416, 2010.
DOI : 10.1093/bioinformatics/btq217

J. T. Simpson, K. Wong, S. D. Jackman, J. E. Schein, S. J. Jones et al., ABySS: A parallel assembler for short read sequence data, Genome Research, vol.19, issue.6, pp.1117-1123, 2009.
DOI : 10.1101/gr.089532.108

G. Sutton, J. R. Miller, A. L. Delcher, S. Koren, E. Venter et al., Aggressive assembly of pyrosequencing reads with mates, Bioinformatics, issue.24, pp.242818-2824, 2008.

R. L. Warren, G. G. Sutton, S. J. Jones, and R. A. Holt, Assembling millions of short DNA sequences using SSAKE, Bioinformatics, vol.23, issue.4, pp.500-501, 2007.
DOI : 10.1093/bioinformatics/btl629

J. Wetzel, C. Kingsford, and M. Pop, Assessing the benefits of using mate-pairs to resolve repeats in de novo short-read prokaryotic assemblies, BMC Bioinformatics, vol.12, issue.1, pp.95-2011
DOI : 10.4056/sigs.761490

N. Whiteford, String Matching in DNA Sequences: Implications for Short Read Sequencing and Repeat Visualisation, p.29, 2007.

M. Roach, C. Bradley, and . Neylon, An analysis of the feasibility of short read