I. Memory-usage, 10.5.2 Multiple contig borders between t and next(t) Correct node id for next(t), p.89

G. Kucherov, K. Salikhov, and D. Tsur, Approximate string matching using a bidirectional index, Theor. Comput. Sci, pp.145-158, 2016.
URL : https://hal.archives-ouvertes.fr/hal-00824706

K. Salikhov, G. Sacomoto, and G. Kucherov, Using cascading Bloom filters to improve the memory usage for de Brujin graphs, BMC Algorithms for Molecular Biology, vol.9191, issue.70, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00824697

K. Salikhov, Improved compression of DNA sequencing data with Cascading Bloom filters In: Special issue of the, IJFCS) for the international Student Conference on Mathematical Foundations in Bioinformatics (MatBio), 2017.

J. D. Watson and F. H. Crick, Molecular structure of nucleic acids; a structure for deoxyribose nucleic acid, In: Nature, vol.1714356, issue.12, pp.737-738, 1953.

Z. D. Stephens, Big Data: Astronomical or Genomical?, PLOS Biology, vol.28, issue.7, pp.1-11, 2015.
DOI : 10.1371/journal.pbio.1002195.s006
URL : https://doi.org/10.1371/journal.pbio.1002195

J. C. Venter, Environmental Genome Shotgun Sequencing of the Sargasso Sea, Science, vol.304, issue.5667, pp.66-74, 2004.
DOI : 10.1126/science.1093857

E. Karsenti, A Holistic Approach to Marine Eco-Systems Biology, PLoS Biology, vol.6, issue.10, 2011.
DOI : 10.1371/journal.pbio.1001177.g002
URL : https://hal.archives-ouvertes.fr/hal-00691580

J. Qin, A human gut microbial gene catalogue established by metagenomic sequencing, Nature, vol.13, issue.7285, pp.59-65, 2010.
DOI : 10.1101/gr.229202. Article published online before March 2002
URL : https://hal.archives-ouvertes.fr/cea-00908974

T. M. Vogel, TerraGenome: a consortium for the sequencing of a soil metagenome, Nature Reviews Microbiology, vol.5, issue.4, pp.252-252, 2009.
DOI : 10.1038/nrmicro2119
URL : https://hal.archives-ouvertes.fr/hal-00391653

J. Peterson, The NIH Human Microbiome Project, Genome Research, vol.1912, pp.2317-2323, 2009.

T. W. Lam, High Throughput Short Read Alignment via Bi-directional BWT, 2009 IEEE International Conference on Bioinformatics and Biomedicine, pp.31-36, 2009.
DOI : 10.1109/BIBM.2009.42

R. E. Franklin and R. G. Gosling, Molecular Configuration in Sodium Thymonucleate, Nature, vol.1714356, pp.740-741, 1953.

A. M. Maxam and W. Gilbert, A new method for sequencing DNA., Proceedings of the National Academy of Sciences, vol.74, issue.2, pp.560-564, 1977.
DOI : 10.1073/pnas.74.2.560

F. Sanger, S. Nicklen, and A. R. Coulson, DNA sequencing with chain-terminating inhibitors, Proceedings of the National Academy of Sciences of the United States of America, 1977.
DOI : 10.1073/pnas.74.12.5463
URL : http://www.pnas.org/content/74/12/5463.full.pdf

E. R. Mardis, Next-Generation DNA Sequencing Methods, Annual Review of Genomics and Human Genetics, vol.9, issue.1, pp.387-402, 2008.
DOI : 10.1146/annurev.genom.9.081307.164359

E. R. Mardis, A decade???s perspective on DNA sequencing technology, Nature, vol.364, issue.7333, 2011.
DOI : 10.1056/NEJMoa1012928

M. L. Metzker, Sequencing technologies ??? the next generation, Nature Reviews Genetics, vol.37, issue.1, pp.31-46, 2010.
DOI : 10.1016/j.tig.2007.12.006

J. Thompson and P. Milos, The properties and applications of single-molecule DNA sequencing, Genome Biology, vol.122, 2011.

M. Margulies, Genome sequencing in microfabricated high-density picolitre reactors, Nature, vol.2, issue.7057, p.14, 2005.
DOI : 10.1089/cmb.1995.2.275

H. Y. Lam, Performance comparison of whole-genome sequencing platforms, Nature Biotechnology, vol.30, issue.1, pp.78-82, 2011.
DOI : 10.1038/nbt.1975

M. Barba, H. Czosnek, and A. Hadidi, Historical Perspective, Development and Applications of Next-Generation Sequencing in Plant Virology, Viruses, vol.66, issue.1, 2014.
DOI : 10.3390/v3101849

L. T. França, E. Carrilho, and T. B. Kist, A review of DNA sequencing techniques, Quarterly Reviews of Biophysics, vol.35, issue.02, pp.169-200, 2002.
DOI : 10.1017/S0033583502003797

B. Liu, Accurate and fast estimation of taxonomic profiles from metagenomic shotgun sequences, S4, pp.14-76, 2011.

J. K. Kulski, Next-Generation Sequencing ??? An Overview of the History, Tools, and ???Omic??? Applications, p.61964
DOI : 10.5772/61964

S. Levy, The Diploid Genome Sequence of an Individual Human, PLoS Biology, vol.17, issue.10, 2007.
DOI : 10.1371/journal.pbio.0050254.sd001

D. A. Wheeler, The complete genome of an individual by massively parallel DNA sequencing, Nature, vol.2, issue.7189, 2008.
DOI : 10.1101/gr.8.3.175

L. M. Bragg, Shining a Light on Dark Sequencing: Characterising Errors in Ion Torrent PGM Data, PLoS Computational Biology, vol.6, issue.4, 2013.
DOI : 10.1371/journal.pcbi.1003031.s014

A. Gilles, Accuracy and quality assessment of 454 GS-FLX Titanium pyrosequencing, BMC Genomics, vol.23, issue.21, 2011.
DOI : 10.1093/bioinformatics/btm404

S. Huse, Accuracy and quality of massively parallel DNA pyrosequencing, Genome Biology, vol.87, 2007.

F. C. Botelho, Y. Kohayakawa, and N. Ziviani, A Practical Minimal Perfect Hashing Method, pp.488-500, 2005.
DOI : 10.1007/11427186_42

D. Belazzougui, Monotone Minimal Perfect Hashing: Searching a Sorted Table with <italic>O</italic>(1) Accesses, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.785-794, 2009.

A. Limasset, Fast and scalable minimal perfect hashing for massive key sets, p.16
URL : https://hal.archives-ouvertes.fr/hal-01566246

B. H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, vol.13, issue.7, pp.422-426, 1970.
DOI : 10.1145/362686.362692

A. Kirsch and M. Mitzenmacher, Less hashing, same performance: Building a better Bloom filter " . In: Random Struct, Algorithms, vol.33, issue.2, pp.187-218, 2008.
DOI : 10.1002/rsa.20208
URL : http://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf

P. Weiner, Linear Pattern Matching Algorithms SWAT '73, Proceedings of the 14th Annual Symposium on Switching and Automata Theory, 1973.
DOI : 10.1109/swat.1973.13
URL : http://airelles.i3s.unice.fr/files/Weiner.pdf

E. M. Mccreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM, vol.23, issue.2, pp.262-272, 1976.
DOI : 10.1145/321941.321946

E. Ukkonen, On-line construction of suffix trees, Algorithmica, vol.10, issue.3, pp.249-260, 1995.
DOI : 10.1145/321941.321946

M. Farach, Optimal suffix tree construction with large alphabets, Proceedings 38th Annual Symposium on Foundations of Computer Science, pp.137-143, 1997.
DOI : 10.1109/SFCS.1997.646102

C. Meek, J. M. Patel, and S. Kasetty, OASIS, Proceedings of the 29th international conference on Very large data bases, pp.910-921, 2003.
DOI : 10.1016/B978-012722442-8/50085-9

A. L. Delcher, Alignment of whole genomes, Nucleic Acids Research, vol.7, issue.4, pp.2369-2376, 1999.
DOI : 10.1101/gr.7.4.315

U. Manber and G. Myers, Suffix Arrays: A New Method for On-Line String Searches, Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '90, pp.319-327, 1990.
DOI : 10.1137/0222058

G. H. Gonnet, R. A. Baeza-yates, T. Snider, W. B. Frakes, and R. Baeza-yates, Information Retrieval, Chap. New Indices for Text: PAT Trees and PAT Arrays, pp.66-82, 1992.

J. Kärkkäinen and P. Sanders, Simple Linear Work Suffix Array Construction The Netherlands, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, pp.943-9553, 2003.

G. Nong, S. Zhang, and W. H. Chan, Linear Suffix Array Construction by Almost Pure Induced-Sorting, 2009 Data Compression Conference, pp.193-202, 2009.
DOI : 10.1109/DCC.2009.42

S. J. Puglisi, W. F. Smyth, and A. H. Turpin, A taxonomy of suffix array construction algorithms, ACM Computing Surveys, vol.39, issue.2, 2007.
DOI : 10.1145/1242471.1242472

M. I. Abouelhoda, S. Kurtz, and E. Ohlebusch, Replacing suffix trees with enhanced suffix arrays, Journal of Discrete Algorithms, vol.2, issue.1, pp.53-86, 2004.
DOI : 10.1016/S1570-8667(03)00065-0
URL : https://doi.org/10.1016/s1570-8667(03)00065-0

K. Malde, E. Coward, and I. Jonassen, Fast sequence clustering using a suffix array algorithm, Bioinformatics, vol.19, issue.10, 2003.
DOI : 10.1093/bioinformatics/btg138

M. I. Abouelhoda, S. Kurtz, and E. Ohlebusch, Replacing suffix trees with enhanced suffix arrays, Journal of Discrete Algorithms, vol.2, issue.1, pp.53-86, 2004.
DOI : 10.1016/S1570-8667(03)00065-0
URL : https://doi.org/10.1016/s1570-8667(03)00065-0

C. Otto, P. F. Stadler, and S. Hoffmann, Fast and sensitive mapping of bisulfitetreated sequencing data, Bioinformatics, vol.2813, issue.19, pp.1698-1704, 2012.

M. Burrows and D. J. Wheeler, A block-sorting lossless data compression algorithm, 1994.

P. Ferragina and G. Manzini, Opportunistic data structures with applications, Proceedings 41st Annual Symposium on Foundations of Computer Science, pp.390-398, 2000.
DOI : 10.1109/SFCS.2000.892127

M. Burrow and D. Wheeler, A block-sorting lossless data compression algorithm, California, vol.19, p.31, 1994.

R. Grossi, A. Gupta, and J. S. Vitter, High-order Entropy-compressed Text Indexes, Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '03, pp.841-850, 2003.
DOI : 10.1007/978-3-642-40273-9_14

B. Langmead, Ultrafast and memory-efficient alignment of short DNA sequences to the human genome, Genome Biology, vol.10, issue.3, pp.25-31, 2009.
DOI : 10.1186/gb-2009-10-3-r25

H. Li and R. Durbin, Fast and accurate short read alignment with Burrows-Wheeler transform, Bioinformatics, vol.9, issue.11, pp.1754-1760, 2009.
DOI : 10.1186/1471-2105-9-128
URL : https://academic.oup.com/bioinformatics/article-pdf/25/14/1754/605544/btp324.pdf

J. Simpson and R. Durbin, Efficient de novo assembly of large genomes using compressed data structures, Genome Research, vol.22, issue.3, pp.549-556, 2012.
DOI : 10.1101/gr.126953.111

L. Russo, Approximate String Matching with Compressed Indexes, Algorithms, vol.1, issue.3, pp.1105-1136, 2009.
DOI : 10.1145/135239.135244
URL : https://doi.org/10.3390/a2031105

T. Schnattinger, E. Ohlebusch, and S. Gog, Bidirectional search in a string with wavelet trees and bidirectional matching statistics, Information and Computation, vol.213, pp.13-22, 2012.
DOI : 10.1016/j.ic.2011.03.007

D. Belazzougui, Versatile Succinct Representations of the Bidirectional Burrows-Wheeler Transform, Proc. 21st European Symposium on Algorithms (ESA). 2013, pp.133-144
DOI : 10.1007/978-3-642-40450-4_12

K. B?inda, Novel computational techniques for mapping and classifying Next- Generation Sequencing data, p.94

H. Li and N. Homer, A survey of sequence alignment algorithms for next-generation sequencing, Briefings in Bioinformatics, vol.10, issue.9, pp.473-483, 2010.
DOI : 10.1186/gb-2009-10-9-r98

P. Ribeca, Short-Read Mapping Bioinformatics for High Throughput Sequencing, pp.107-125

S. Canzar and S. L. Salzberg, Short Read Mapping: An Algorithmic Tour, Proceedings of the IEEE, vol.105, issue.3, pp.1-23, 2015.
DOI : 10.1109/JPROC.2015.2455551
URL : http://europepmc.org/articles/pmc5425171?pdf=render

R. S. Boyer and J. S. Moore, A fast string searching algorithm, Communications of the ACM, vol.20, issue.10, pp.762-772, 1977.
DOI : 10.1145/359842.359859

D. E. Knuth, J. James, H. Morris, and V. R. Pratt, Fast Pattern Matching in Strings, SIAM Journal on Computing, vol.6, issue.2, 1977.
DOI : 10.1137/0206024

M. J. Fischer and M. S. Paterson, String-matching and other products, Symposium on Complexity of Computation: SIAM-AMS Proceedings, pp.113-125, 1974.

Z. Galil and R. Giancarlo, Improved string matching with k mismatches, ACM SIGACT News, vol.17, issue.4, pp.52-54, 1986.
DOI : 10.1145/8307.8309

A. Amir, M. Lewenstein, and E. Porat, Faster algorithms for string matching with k mismatches, Journal of Algorithms, vol.50, issue.2, pp.257-275, 2004.
DOI : 10.1016/S0196-6774(03)00097-X

G. M. Landau and U. Vishkin, Fast string matching with k differences, Journal of Computer and System Sciences, vol.37, issue.1, pp.63-78, 1988.
DOI : 10.1016/0022-0000(88)90045-1
URL : https://doi.org/10.1016/0022-0000(88)90045-1

Z. Galil, K. Park-ausiello, M. Dezani-ciancaglini, and S. R. Della-rocca, An improved algorithm for approximate string matching, Automata, Languages and Programming: 16th International Colloquium Stresa, Italy, pp.394-404, 1989.

S. Henikoff and J. G. Henikoff, Amino acid substitution matrices from protein blocks., Proceedings of the National Academy of Sciences, vol.89, issue.22, pp.10915-10919, 1992.
DOI : 10.1073/pnas.89.22.10915
URL : http://www.pnas.org/content/89/22/10915.full.pdf

S. B. Needleman and C. D. Wunsch, A general method applicable to the search for similarities in the amino acid sequence of two proteins, Journal of Molecular Biology, vol.483, pp.443-453, 1970.

T. F. Smith and M. S. Waterman, Identification of common molecular subsequences(81 ) 90087 -5. url: http : / / www . sciencedirect . com / science, Journal of molecular biology, vol.1471, pp.195-202, 1981.

G. Myers, A fast bit-vector algorithm for approximate string matching based on dynamic programming, Journal of the ACM, vol.463, pp.395-415, 1999.

W. R. Pearson and D. J. Lipman, Improved tools for biological sequence comparison., Proceedings of the National Academy of Sciences, vol.85, issue.8, p.55, 1988.
DOI : 10.1073/pnas.85.8.2444

R. Li, SOAP: short oligonucleotide alignment program, Bioinformatics, vol.5, issue.5, pp.713-714, 2008.
DOI : 10.1038/nrg1325
URL : https://academic.oup.com/bioinformatics/article-pdf/24/5/713/527122/btn025.pdf

R. Li, SOAP2: an improved ultrafast tool for short read alignment, Bioinformatics, vol.456, issue.7218, pp.1966-1967, 2009.
DOI : 10.1038/nature07484

W. Lee, MOSAIK: A Hash-Based Algorithm for Accurate Next-Generation Sequencing Short-Read Mapping, PLoS ONE, vol.8, issue.3, 2014.
DOI : 10.1371/journal.pone.0090581.s008

N. Homer, B. Merriman, and S. F. Nelson, BFAST: an alignment tool for large scale genome resequencing In: PloS one 4, 2009.

H. Li, J. Ruan, and R. Durbin, Mapping short DNA sequencing reads and calling variants using mapping quality scores, Genome Research, vol.18, issue.11, pp.1851-1858, 2008.
DOI : 10.1101/gr.078212.108
URL : http://genome.cshlp.org/content/18/11/1851.full.pdf

A. D. Smith, Updates to the RMAP short-read mapping software, Bioinformatics, vol.5251, issue.11, pp.2841-2842, 2009.
DOI : 10.1007/978-3-540-87361-7_4

H. Lin, ZOOM! Zillions of oligos mapped, Bioinformatics, vol.124, issue.1, p.29, 2008.
DOI : 10.1016/j.cell.2005.10.043

M. David, SHRiMP2: Sensitive yet Practical Short Read Mapping, Bioinformatics, vol.26, issue.7, 2011.
DOI : 10.1093/bioinformatics/btq057
URL : https://academic.oup.com/bioinformatics/article-pdf/27/7/1011/16902170/btr046.pdf

L. Noé and G. Kucherov, YASS: enhancing the sensitivity of DNA similarity search In: Nucleic acids research 33, Web Server issue, 2005.

B. Ma, J. Tromp, and M. Li, PatternHunter: faster and more sensitive homology search, Bioinformatics, vol.18, issue.3, pp.440-445, 2002.
DOI : 10.1093/bioinformatics/18.3.440
URL : https://academic.oup.com/bioinformatics/article-pdf/18/3/440/648219/180440.pdf

S. Burkhardt and J. Kärkkäinen, Better Filtering with Gapped q-Grams, Combinatorial Pattern Matching: 12th Annual Symposium, pp.73-85, 2001.
DOI : 10.1007/3-540-48194-X_6
URL : http://www.mpi-sb.mpg.de/~juha/publications/fundamenta-revised.ps.gz

H. Jiang and W. H. Wong, SeqMap: mapping massive amount of oligonucleotides to the genome, Bioinformatics, vol.14, issue.8, pp.2395-2396, 2008.
DOI : 10.1261/rna.1070208

G. Kucherov, L. Noé, M. Roytberg, . Unifying, . For et al., A, Journal of Bioinformatics and Computational Biology, vol.04, p.2, 2006.
URL : https://hal.archives-ouvertes.fr/hal-00824706

G. Navarro and V. Mäkinen, Compressed full-text indexes, ACM Computing Surveys, vol.39, issue.1, p.31, 2007.
DOI : 10.1145/1216370.1216372
URL : http://www.dcc.uchile.cl/TR/2006/TR_DCC-2006-006.pdf

B. Langmead, Ultrafast and memory-efficient alignment of short DNA sequences to the human genome, Genome Biology, vol.10, issue.3, p.75, 2009.
DOI : 10.1186/gb-2009-10-3-r25

H. Li, poster Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. 2013 (cit, p.31

T. W. Lam, Compressed indexing and local alignment of DNA, Bioinformatics, vol.14, issue.6, pp.791-797, 2008.
DOI : 10.1109/69.979973

H. Li and R. Durbin, Fast and accurate long-read alignment with Burrows???Wheeler transform, Bioinformatics, vol.7, issue.5, pp.589-595, 2010.
DOI : 10.1089/10665270050081478
URL : https://academic.oup.com/bioinformatics/article-pdf/26/5/589/16896917/btp698.pdf

H. Li and R. Durbin, Fast and accurate short read alignment with Burrows- Wheeler transform " . en, In: Bioinformatics, vol.2514, pp.31-75, 2009.
DOI : 10.1093/bioinformatics/btp324
URL : https://academic.oup.com/bioinformatics/article-pdf/25/14/1754/605544/btp324.pdf

L. H. Chen, Poisson Approximation for Dependent Trials, The Annals of Probability, vol.3, issue.3, pp.534-545, 1975.
DOI : 10.1214/aop/1176996359
URL : http://doi.org/10.1214/aop/1176996359

A. D. Barbour, L. Holst, and S. Janson, Poisson approximation, 1992.

S. Mihov and K. U. Schulz, Fast Approximate Search in Large Dictionaries, Computational Linguistics, vol.22, issue.1, pp.451-477, 2004.
DOI : 10.1002/spe.4380250307

J. Kärkkäinen and J. C. Na, Faster Filters for Approximate String Matching, Proc. 9th Workshop on Algorithm Engineering and Experiments (ALENEX), pp.84-90, 2007.
DOI : 10.1137/1.9781611972870.8

Z. Li, Comparison of the two major classes of assembly algorithms: overlap-layout-consensus and de-bruijn-graph, Briefings in Functional Genomics, vol.24, issue.24, 2012.
DOI : 10.1093/bioinformatics/btn548

W. Zhang, A Practical Comparison of De Novo Genome Assembly Software Tools for Next-Generation Sequencing Technologies, PLoS ONE, vol.215, issue.3, 2011.
DOI : 10.1371/journal.pone.0017915.s003

S. L. Salzberg, GAGE: A critical evaluation of genome assemblies and assembly algorithms, Genome Research, vol.22, issue.3, pp.557-567, 2011.
DOI : 10.1101/gr.131383.111

K. R. Bradnam, Assemblathon 2: evaluating de novo methods of genome assembly in three vertebrate species, GigaScience, vol.215, issue.3, pp.2047-217, 2013.
DOI : 10.1016/S0022-2836(05)80360-2
URL : https://hal.archives-ouvertes.fr/hal-00868822

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

R. Staden, A mew computer method for the storage and manipulation of DNA gel reading data, Nucleic Acids Research, vol.8, issue.16, 1980.
DOI : 10.1093/nar/8.16.3673

S. Batzoglou, ARACHNE: A Whole-Genome Shotgun Assembler, Genome Research, vol.12, issue.1, pp.177-189, 2002.
DOI : 10.1101/gr.208902

E. W. Myers, A Whole-Genome Assembly of Drosophila, Science, vol.287, issue.5461, pp.5461-2196, 2000.
DOI : 10.1126/science.287.5461.2196

X. Huang and A. Madan, CAP3: A DNA Sequence Assembly Program, Genome Research, vol.9, issue.9, pp.868-877, 1999.
DOI : 10.1101/gr.9.9.868

X. Huang, PCAP: A Whole-Genome Assembly Program, Genome Research, vol.13, issue.9, pp.2164-2170, 2003.
DOI : 10.1101/gr.1390403

M. De-la-bastide, W. R. Andreas, and D. Baxevanis, Assembling Genomic DNA Sequences with PHRAP, 2007.
DOI : 10.1016/0022-2836(81)90087-5

J. C. Mullikin and Z. Ning, The Phusion Assembler, Genome Research, vol.13, issue.1, pp.81-90, 2003.
DOI : 10.1101/gr.731003

M. Margulies, Genome sequencing in microfabricated high-density picolitre reactors, Nature, vol.2, issue.7057, 2005.
DOI : 10.1089/cmb.1995.2.275

J. T. Simpson and R. Durbin, Efficient de novo assembly of large genomes using compressed data structures, Genome Research, vol.22, issue.3, pp.549-556, 2012.
DOI : 10.1101/gr.126953.111

N. Välimäki, S. Ladra, and V. Mäkinen, Approximate all-pairs suffix/prefix overlaps, Information and Computation, vol.213, pp.49-58, 2012.
DOI : 10.1016/j.ic.2012.02.002

J. Kärkkäinen and J. C. Na, Faster Filters for Approximate String Matching, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX), pp.84-90, 2007.
DOI : 10.1137/1.9781611972870.8

G. Kucherov and D. Tsur, Improved Filters for the Approximate Suffix-Prefix Overlap Problem, String Processing and Information Retrieval: 21st International Symposium, SPIRE 2014, Ouro Preto, Brazil, pp.139-148978, 2014.
DOI : 10.1007/978-3-319-11918-2_14
URL : https://hal.archives-ouvertes.fr/hal-01086208

P. A. Pevzner, H. Tang, and M. S. Waterman, An Eulerian path approach to DNA fragment assembly, Proc. Natl. Acad. Sci. U.S.A. 98, pp.9748-9753, 2001.
DOI : 10.1126/science.1058040

M. G. Grabherr, Full-length transcriptome assembly from RNA-Seq data without a reference genome, Nature Biotechnology, vol.30, issue.7, pp.644-652, 2011.
DOI : 10.1101/GR.229202. ARTICLE PUBLISHED ONLINE BEFORE MARCH 2002

G. Sacomoto, KISSPLICE: de-novo calling alternative splicing events from RNA-seq data, BMC Bioinformatics, vol.13, issue.6, p.5, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00784407

Y. Peng, Meta-IDBA: a de Novo assembler for metagenomic data, Bioinformatics, vol.4, issue.12, pp.94-101, 2011.
DOI : 10.1371/journal.pone.0008407

T. Conway and A. Bromage, Succinct data structures for assembling large genomes, Bioinformatics, vol.18, issue.Suppl. 1, pp.479-486, 2011.
DOI : 10.1101/gr.074492.107

C. Ye, Exploiting sparseness in de novo genome assembly, S1. url, p.55, 2012.
DOI : 10.1093/bioinformatics/btr319

R. Chikhi and G. Rizk, Space-Efficient and Exact de Bruijn Graph Representation Based on a Bloom Filter, Algorithms in Bioinformatics -12th International Workshop, WABI 2012, pp.236-248, 2012.
DOI : 10.1007/978-3-642-33122-0_19
URL : https://hal.archives-ouvertes.fr/hal-00868805

A. Bowe, Succinct de Bruijn Graphs, Algorithms in Bioinformatics -12th International Workshop, WABI 2012, pp.225-235, 2012.
DOI : 10.1007/978-3-642-33122-0_18

J. Pell, Scaling metagenome sequence assembly with probabilistic de Bruijn graphs, Proceedings of the National Academy of Sciences, vol.54, issue.2, pp.13272-13277, 2012.
DOI : 10.1090/S0002-9947-1943-0012401-3

E. Drezen, GATB: Genome Assembly & Analysis Tool Box, Bioinformatics, vol.18, issue.20, pp.2959-2961, 2014.
DOI : 10.1101/gr.074492.107
URL : https://hal.archives-ouvertes.fr/hal-01088571

C. Boucher, Variable-Order de Bruijn Graphs, 2015 Data Compression Conference, pp.383-392, 2015.
DOI : 10.1109/DCC.2015.70
URL : http://arxiv.org/pdf/1411.2718.pdf

D. Belazzougui, Bidirectional Variable-Order de Bruijn Graphs, LATIN 2016: Theoretical Informatics -12th Latin American Symposium, pp.164-178978, 2016.
DOI : 10.1007/978-3-662-49529-2_13

R. Chikhi, On the Representation of De Bruijn Graphs, Proceedings of the 18th Annual International Conference on Research in Computational Molecular Biology, pp.35-55978, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01524525

D. Belazzougui, Fully Dynamic de Bruijn Graphs, String Processing and Information Retrieval -23rd International Symposium, SPIRE 2016, pp.145-152978, 2016.
DOI : 10.1101/gr.074492.107
URL : http://arxiv.org/pdf/1607.04909

G. Rizk, D. Lavenier, and R. Chikhi, DSK: k-mer counting with very low memory usage, Bioinformatics, vol.12, issue.6, pp.652-655, 2013.
DOI : 10.1186/1471-2105-12-333
URL : https://hal.archives-ouvertes.fr/hal-00778473

F. R. Blattner, The Complete Genome Sequence of Escherichia coli K-12, Science, vol.277, issue.5331, pp.1453-1462, 1997.
DOI : 10.1126/science.277.5331.1453

E. Porat, An Optimal Bloom Filter Replacement Based on Matrix Solving, Proceedings. Lecture Notes in Computer Science, vol.32, issue.1, pp.263-273, 2009.
DOI : 10.1109/TIT.1986.1057137

R. Rozov, R. Shamir, and E. Halperin, Fast lossless compression via cascading Bloom filters, BMC Bioinformatics, vol.15, issue.Suppl 9, pp.70-72, 2014.
DOI : 10.1038/nmeth.1923
URL : https://bmcbioinformatics.biomedcentral.com/track/pdf/10.1186/1471-2105-15-S9-S7?site=bmcbioinformatics.biomedcentral.com

J. K. Bonfield and M. V. Mahoney, Compression of FASTQ and SAM Format Sequencing Data, PLoS ONE, vol.32, issue.3, 2013.
DOI : 10.1371/journal.pone.0059190.s001

M. H. Fritz, Efficient storage of high throughput DNA sequencing data using reference-based compression, Genome Research, vol.215, pp.734-740, 2011.

D. C. Jones, Compression of next-generation sequencing reads aided by highly efficient de novo assembly, Nucleic Acids Research, vol.26, issue.7, 2012.
DOI : 10.1186/1471-2105-12-354

C. Kingsford and R. Patro, Reference-based compression of short-read sequences using path encoding, Bioinformatics, vol.31, issue.12, 2015.
DOI : 10.1007/978-3-319-05269-4_31

C. Kozanitis, Compressing Genomic Sequence Fragments Using SlimGene Lecture Notes in Computer Science, Computational Molecular Biology. Ed. by B. Berger, vol.6044, issue.20, pp.310-324978, 2010.

G. Benoit, Reference-free compression of high throughput sequencing data with a probabilistic de Bruijn graph, BMC Bioinformatics, vol.43, issue.2, pp.12859-12874, 2015.
DOI : 10.1093/nar/gku1187
URL : https://hal.archives-ouvertes.fr/hal-01214682

A. J. Cox, Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform, Bioinformatics, vol.6, issue.17, 2012.
DOI : 10.1186/1748-7188-6-23

S. Deorowicz and S. Grabowski, Compression of DNA sequence reads in FASTQ format, Bioinformatics, vol.26, issue.6, 2011.
DOI : 10.1093/bioinformatics/btq346

S. Grabowski, S. Deorowicz, and ?. Roguski, Disk-based compression of data from genome sequencing, Bioinformatics, vol.6, issue.9, 2014.
DOI : 10.1186/1748-7188-6-23

F. Hach, SCALCE: boosting sequence compression algorithms using locally consistent encoding, Bioinformatics, vol.24, issue.23, 2012.
DOI : 10.1109/TIT.1978.1055934
URL : https://academic.oup.com/bioinformatics/article-pdf/28/23/3051/18530674/bts593.pdf

L. Janin, O. Schulz-trieglaff, and A. J. Cox, BEETL-fastq: a searchable compressed archive for DNA reads, Bioinformatics, vol.32, issue.5, 2014.
DOI : 10.1038/nbt.2835

R. Patro and C. Kingsford, Data-dependent bucketing improves reference-free compression of sequencing reads, Bioinformatics, vol.31, issue.17, 2015.
DOI : 10.1038/nbt.3170

D. H. Huson, Integrative analysis of environmental sequences using MEGAN4, Genome Research, vol.21, issue.9, p.75, 2011.
DOI : 10.1101/gr.120618.111

N. Segata, Metagenomic microbial community profiling using unique cladespecific marker genes, pp.811-814, 2012.
DOI : 10.1038/nmeth.2066
URL : http://europepmc.org/articles/pmc3443552?pdf=render

B. Liu, MetaPhyler: Taxonomic profiling for metagenomic sequences, 2010 IEEE International Conference on Bioinformatics and Biomedicine (BIBM)
DOI : 10.1109/BIBM.2010.5706544

J. Pell, Scaling metagenome sequence assembly with probabilistic de Bruijn graphs, Proceedings of the National Academy of Sciences, vol.54, issue.2, 2012.
DOI : 10.1090/S0002-9947-1943-0012401-3
URL : http://www.pnas.org/content/109/33/13272.full.pdf

J. Berendzen, Rapid phylogenetic and functional classification of short genomic fragments with signature peptides, BMC Research Notes, vol.5, issue.1, 2012.
DOI : 10.1371/journal.pone.0003373

S. K. Ames, Scalable metagenomic taxonomy classification using a reference genome database, Bioinformatics, vol.304, issue.18, 2013.
DOI : 10.1126/science.1093857

T. Tatusova, RefSeq microbial genomes database: new representation and annotation strategy, Nucleic Acids Research, vol.42, pp.1-553, 2014.
DOI : 10.1093/nar/gkv278
URL : https://academic.oup.com/nar/article-pdf/43/7/3872/7211719/gkv278.pdf

D. E. Wood and S. L. Salzberg, Kraken: ultrafast metagenomic sequence classification using exact alignments R46. doi: 10.1186/ gb-2014-15-3-r46. url: http://www.pubmedcentral.nih.gov/articlerender, In: Genome biology, vol.153, p.94, 2014.
DOI : 10.1186/gb-2014-15-3-r46
URL : https://genomebiology.biomedcentral.com/track/pdf/10.1186/gb-2014-15-3-r46?site=genomebiology.biomedcentral.com

D. Kim, Centrifuge: rapid and sensitive classification of metagenomic sequences In: bioRxiv preprints, 2016.

B. Langmead and S. L. Salzberg, Fast gapped-read alignment with Bowtie 2, Nature methods 9, pp.357-366, 2012.
DOI : 10.1093/bioinformatics/btp352

P. Menzel, K. L. Ng, and A. Krogh, Fast and sensitive taxonomic classification for metagenomics with Kaiju, Nature Communications, vol.7, 2016.

H. Stranneheim, Classification of DNA sequences using Bloom filters, Bioinformatics, vol.7, issue.13, 2010.
DOI : 10.1089/10665270050081478

J. Kawulok and S. Deorowicz, CoMeta: Classification of Metagenomes Using kmers, PLOS ONE, vol.10, issue.4, 2015.

S. Lindgreen, K. L. Adair, and P. P. Gardner, An evaluation of the accuracy and speed of metagenome analysis tools, In: Scientific Reports, vol.6, 2016.

R. J. Randle-boggis, Evaluating techniques for metagenome annotation using simulated sequence data, FEMS Microbiology Ecology, vol.15, issue.7, 2016.
DOI : 10.1093/bioinformatics/btr595

D. O. Ricke, A. Shcherbina, and N. Chiu, Evaluating performance of metagenomic characterization algorithms using in silico datasets generated with FASTQSim, 2016.
DOI : 10.1101/046532

M. A. Peabody, Evaluation of shotgun metagenomics sequence classification methods using in silico and in vitro simulated communities, BMC Bioinformatics, vol.4, issue.3, p.363, 2015.
DOI : 10.6026/97320630004046

H. Vinje, Comparing K-mer based methods for improved classification of 16S sequences, BMC Bioinformatics, vol.6, issue.1, 2015.
DOI : 10.1038/ismej.2011.82

. Pavlopoulos, Metagenomics: Tools and Insights for Analyzing Next-Generation Sequencing Data Derived from Biodiversity Studies: http://www.la-press. com/metagenomics-tools-and-insights-for-analyzing-next-generation- sequenci-article-a4809, Bioinformatics and Biology Insights, 2015.

D. Clark, Compact Pat Trees, 1996.