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

M. I. Abouelhoda, E. Ohlebusch, and S. Kurtz, Optimal Exact String Matching Based on Suffix Arrays, Lecture Notes in Computer Science, vol.2476, pp.31-43, 2002.
DOI : 10.1007/3-540-45735-6_4

K. R. Abrahamson, Generalized String Matching, SIAM Journal on Computing, vol.16, issue.6, pp.1039-1051, 1987.
DOI : 10.1137/0216067

S. Alstrup, G. S. Brodal, and T. Rauhe, New data structures for orthogonal range searching, Proceedings 41st Annual Symposium on Foundations of Computer Science, pp.198-207, 2000.
DOI : 10.1109/SFCS.2000.892088

A. Amir, D. Keselman, G. M. Landau, M. Lewenstein, N. Lewenstein et al., Text Indexing and Dictionary Matching with One Error, Journal of Algorithms, vol.37, issue.2, pp.309-325, 2000.
DOI : 10.1006/jagm.2000.1104

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

R. A. Baeza-yates and G. H. Gonnet, Fast String Matching with Mismatches, Information and Computation, vol.108, issue.2, pp.187-199, 1994.
DOI : 10.1006/inco.1994.1007

P. Bille, I. L. Gørtz, H. W. Vildhøj, and S. Vind, String indexing for patterns with wildcards, Theory Comput. Syst, 2013.

M. Burrows and D. Wheeler, A block-sorting loss-less data compression algorithm, SRC Research Report, vol.124, 1994.

L. Cartegni and A. Krainer, Disruption of an SF2/ASF-dependent exonic splicing enhancer in SMN2 causes spinal muscular atrophy in the absence of SMN1, Nature Genetics, vol.30, issue.4, pp.377-384, 2002.
DOI : 10.1038/ng854

C. Charras and T. Lecroq, Handbook of Exact String Matching Algorithms. Texts in Algorithmics. King's College London, 2004.

P. Clifford and R. Clifford, Self-normalised Distance with Don???t Cares, Lecture Notes in Computer Science, vol.4580, pp.63-70, 2007.
DOI : 10.1007/978-3-540-73437-6_9

R. Cole, L. Gottlieb, and M. Lewenstein, Dictionary matching and indexing with errors and don't cares, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing , STOC '04, pp.91-100, 2004.
DOI : 10.1145/1007352.1007374

R. Cole and R. Hariharan, Verifying candidate matches in sparse and wildcard matching, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , STOC '02, pp.592-601, 2002.
DOI : 10.1145/509907.509992

M. Crochemore, C. Epifanio, A. Gabriele, and F. Mignosi, From Nerode???s congruence to suffix automata with mismatches, Theoretical Computer Science, vol.410, issue.37, pp.4103471-3480, 2009.
DOI : 10.1016/j.tcs.2009.03.011

M. Crochemore, C. Hancart, and T. Lecroq, Algorithms on Strings, 2007.
DOI : 10.1017/CBO9780511546853

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

M. Crochemore, M. Kubica, T. Walen, C. S. Iliopoulos, and M. S. Rahman, Finding Patterns in Given Intervals, Fundam. Inform, vol.101, issue.3, pp.173-186, 2010.
DOI : 10.1007/978-3-540-74456-6_57

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

A. Dermouche, A fast algorithm for string matching with mismatches, Information Processing Letters, vol.55, issue.2, pp.105-110, 1995.
DOI : 10.1016/0020-0190(95)00043-C

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

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

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

P. Ferragina, G. Manzini, V. Mäkinen, and G. Navarro, An Alphabet-Friendly FM-Index, Lecture Notes in Computer Science, vol.3246, pp.150-160, 2004.
DOI : 10.1007/978-3-540-30213-1_23

M. Fischer and M. Paterson, String matching and other products, SIAM AMS Proceedings, pp.113-125, 1974.

L. Foschini, R. Grossi, A. Gupta, and J. S. Vitter, When indexing equals compression, ACM Transactions on Algorithms, vol.2, issue.4, pp.611-639, 2006.
DOI : 10.1145/1198513.1198521

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

Z. Galil and R. Giancarlo, Parallel string matching with k mismatches, Theoretical Computer Science, vol.51, issue.3, pp.341-348, 1987.
DOI : 10.1016/0304-3975(87)90042-9

D. Gusfield, Algorithms on Strings, Trees, and Sequences -Computer Science and Computational Biology, 1997.

J. Holub, W. F. Smyth, and S. Wang, Fast pattern-matching on indeterminate strings, Journal of Discrete Algorithms, vol.6, issue.1, pp.37-50, 2008.
DOI : 10.1016/j.jda.2006.10.003

C. S. Iliopoulos, L. Mouchard, and M. S. Rahman, A New Approach to Pattern Matching in Degenerate DNA/RNA Sequences and Distributed Pattern Matching, Mathematics in Computer Science, vol.1, issue.4, pp.557-569, 2008.
DOI : 10.1007/s11786-007-0029-z

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

C. S. Iliopoulos and M. S. Rahman, Indexing Circular Patterns, Lecture Notes in Computer Science, vol.4921, pp.46-57, 2008.
DOI : 10.1007/978-3-540-77891-2_5

C. S. Iliopoulos and M. S. Rahman, Indexing Factors with Gaps, Algorithmica, vol.14, issue.3, pp.60-70, 2009.
DOI : 10.1007/s00453-007-9141-3

P. Indyk, Faster algorithms for string matching problems: matching the convolution bound, Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pp.166-173, 1998.
DOI : 10.1109/SFCS.1998.743440

A. Kalai, Efficient pattern-matching with don't cares, ACM/SIAM, pp.655-656, 2002.

J. Kärkkäinen, P. Sanders, and S. Burkhardt, Simple Linear Work Suffix Array Construction, J. ACM, vol.53, issue.6, pp.918-936, 2006.
DOI : 10.1007/3-540-45061-0_73

D. K. Kim, J. S. Sim, H. Park, and K. Park, Constructing suffix arrays in linear time, Journal of Discrete Algorithms, vol.3, issue.2-4, pp.126-142, 2005.
DOI : 10.1016/j.jda.2004.08.019

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

P. Ko and S. Aluru, Space efficient linear time construction of suffix arrays, Journal of Discrete Algorithms, vol.3, issue.2-4, pp.143-156, 2005.
DOI : 10.1016/j.jda.2004.08.002

J. Kwoka, G. M. Hallidaybc, W. S. Brooksbd, G. Doliose, H. Laudonf et al., Presenilin-1 Mutation L271V Results in Altered Exon 8 Splicing and Alzheimer's Disease with Non-cored Plaques and No Neuritic Dystrophy, Journal of Biological Chemistry, vol.278, issue.9, pp.2786748-6754, 2003.
DOI : 10.1074/jbc.M211827200

T. W. Lam, W. Sung, S. Tam, and S. Yiu, Space Efficient Indexes for String Matching with Don???t Cares, Lecture Notes in Computer Science, vol.4835, pp.846-857, 2007.
DOI : 10.1007/978-3-540-77120-3_73

G. M. Landau and U. Vishkin, Efficient string matching with k mismatches, Theoretical Computer Science, vol.43, pp.239-249, 1986.
DOI : 10.1016/0304-3975(86)90178-7

M. Lewenstein, Orthogonal Range Searching for Text Indexing, Space-Efficient Data Structures, Streams, and Algorithms, pp.267-302, 2013.
DOI : 10.1007/978-3-642-40273-9_18

U. Manber and E. W. Myers, Suffix Arrays: A New Method for On-Line String Searches, SIAM Journal on Computing, vol.22, issue.5, pp.935-948, 1993.
DOI : 10.1137/0222058

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

A. E. Minoche, J. C. Dohm, and H. Himmelbauer, Evaluation of genomic high-throughput sequencing data generated on Illumina HiSeq and Genome Analyzer systems, Genome Biology, vol.12, issue.11, pp.1-15, 2011.
DOI : 10.1093/bioinformatics/btp666

J. C. Na, H. Park, S. Lee, M. Hong, T. Lecroq et al., Suffix Array of Alignment: A Practical Index for Similar Data, Lecture Notes in Computer Science, vol.8214, pp.243-254, 2013.
DOI : 10.1007/978-3-319-02432-5_27

E. Ohlebusch, Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction, 2013.

R. Y. Pinter, Efficient String Matching with Don???t-Care Patterns, Combinatorial ALgorithms on Words, NATO ASI Series, vol.12, pp.11-29, 1985.
DOI : 10.1007/978-3-642-82456-2_2

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

M. S. Rahman and C. S. Iliopoulos, Pattern matching algorithms with don't cares, pp.116-126, 2007.

W. F. Smyth and S. Wang, AN ADAPTIVE HYBRID PATTERN-MATCHING ALGORITHM ON INDETERMINATE STRINGS, International Journal of Foundations of Computer Science, vol.20, issue.06, pp.985-1004, 2009.
DOI : 10.1142/S0129054109007005

W. F. Smyth, S. Wang, and M. Yu, AN ADAPTIVE HYBRID PATTERN-MATCHING ALGORITHM ON INDETERMINATE STRINGS, Stringology, pp.95-107, 2008.
DOI : 10.1142/S0129054109007005

A. Tam, E. Wu, T. W. Lam, and S. Yiu, Succinct Text Indexing with Wildcards, Lecture Notes in Computer Science, vol.42, issue.4, pp.39-50, 2009.
DOI : 10.1016/j.comgeo.2008.09.001

C. Thachuk, Succincter Text Indexing with Wildcards, Lecture Notes in Computer Science, vol.39, issue.1, pp.27-40, 2011.
DOI : 10.1145/1216370.1216372

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