F. Nicolas and E. Rivals, Hardness of Optimal Spaced Seed Design, Proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching (CPM'05), pp.144-155, 2005.
DOI : 10.1007/11496656_13
URL : https://hal.archives-ouvertes.fr/lirmm-00106448

S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman, Basic local alignment search tool, Journal of Molecular Biology, vol.215, issue.3, pp.403-410, 1990.
DOI : 10.1016/S0022-2836(05)80360-2

A. Califano and I. Rigoutsos, FLASH: a fast look-up algorithm for string homology, Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pp.56-64, 1993.
DOI : 10.1109/CVPR.1993.341106

S. Burkhardt, A. Crauser, P. Ferragina, H. Lenhof, E. Rivals et al., Vingron, q-gram Based Database Searching Using a Suffix Array (QUASAR), Proceedings of the 3rd Annual International Conference on Computational Molecular Biology (RECOMB'99), pp.77-83, 1999.

R. M. Karp and M. O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, vol.31, issue.2, pp.249-260, 1987.
DOI : 10.1147/rd.312.0249

E. Ukkonen, Approximate string-matching with q-grams and maximal matches, Theoretical Computer Science, vol.92, issue.1, pp.191-211, 1992.
DOI : 10.1016/0304-3975(92)90143-4

W. I. Chang and E. L. Lawler, Sublinear approximate string matching and biological applications, Algorithmica, vol.8, issue.6, pp.327-344, 1994.
DOI : 10.1007/BF01185431

S. Burkhardt and J. Kärkkäinen, Better Filtering with Gapped q-Grams, Fundamenta Informaticae, vol.56, issue.12, pp.51-70, 2003.
DOI : 10.1007/3-540-48194-X_6

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

M. Li, B. Ma, D. Kisman, and J. Tromp, PATTERNHUNTER II: HIGHLY SENSITIVE AND FAST HOMOLOGY SEARCH, Journal of Bioinformatics and Computational Biology, vol.02, issue.03, pp.417-439, 2004.
DOI : 10.1142/S0219720004000661

L. Noé and G. Kucherov, Improved hit criteria for DNA local alignment, BMC Bioinformatics, vol.5, issue.149, 2004.

G. Kucherov, L. Noé, and M. Roytberg, Multiseed Lossless Filtration, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.2, issue.1, pp.51-61, 2005.
DOI : 10.1109/TCBB.2005.12
URL : https://hal.archives-ouvertes.fr/inria-00354810

K. P. Choi and L. Zhang, Sensitivity analysis and efficient method for identifying optimal spaced seeds, Journal of Computer and System Sciences, vol.68, issue.1, pp.22-40, 2004.
DOI : 10.1016/j.jcss.2003.04.002

B. Brejová, D. G. Brown, and T. Vinar, OPTIMAL SPACED SEEDS FOR HOMOLOGOUS CODING REGIONS, Journal of Bioinformatics and Computational Biology, vol.01, issue.04, pp.595-610, 2004.
DOI : 10.1142/S0219720004000326

G. Kucherov, L. Noé, and Y. Ponty, Estimating seed sensitivity on homogeneous alignments, Proceedings. Fourth IEEE Symposium on Bioinformatics and Bioengineering, pp.387-394, 2004.
DOI : 10.1109/BIBE.2004.1317369
URL : https://hal.archives-ouvertes.fr/inria-00001163

Y. Sun and J. Buhler, Designing Multiple Simultaneous Seeds for DNA Similarity Search, Journal of Computational Biology, vol.12, issue.6, pp.847-861, 2005.
DOI : 10.1089/cmb.2005.12.847

J. Buhler, U. Keich, and Y. Sun, Designing seeds for similarity search in genomic DNA, Journal of Computer and System Sciences, vol.70, issue.3, pp.342-363, 2005.
DOI : 10.1016/j.jcss.2004.12.003

M. Li, B. Ma, and L. Zhang, Superiority and complexity of the spaced seeds, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm , SODA '06, pp.444-453, 2006.
DOI : 10.1145/1109557.1109607

B. Ma and M. Li, On the complexity of the spaced seeds, Journal of Computer and System Sciences, vol.73, issue.7, pp.1024-1034, 2007.
DOI : 10.1016/j.jcss.2007.03.008

D. Mak, Y. Gelfand, and G. Benson, Indel seeds for homology search, Bioinformatics, vol.22, issue.14, pp.341-349, 2006.
DOI : 10.1093/bioinformatics/btl263

G. Kucherov, L. Noé, and M. Roytberg, A UNIFYING FRAMEWORK FOR SEED SENSITIVITY AND ITS APPLICATION TO SUBSET SEEDS, Journal of Bioinformatics and Computational Biology, vol.04, issue.02, pp.553-570, 2006.
DOI : 10.1142/S0219720006001977
URL : https://hal.archives-ouvertes.fr/inria-00001164

M. Farach-colton, G. M. Landau, S. C. Sahinalp, and D. Tsur, Optimal spaced seeds for faster approximate string matching, Journal of Computer and System Sciences, vol.73, issue.7, pp.1035-1044, 2007.
DOI : 10.1016/j.jcss.2007.03.007

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

D. Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , STOC '06, pp.681-690, 2006.
DOI : 10.1145/1132516.1132612

W. C. Babcock, Intermodulation Interference in Radio Systems, Bell System Technical Journal, vol.32, issue.1, pp.63-73, 1953.
DOI : 10.1002/j.1538-7305.1953.tb01422.x

U. Feige, A threshold of ln n for approximating set cover, Journal of the ACM, vol.45, issue.4, pp.634-652, 1998.
DOI : 10.1145/285055.285059

J. Edmonds, Paths, trees, and flowers, Journal canadien de math??matiques, vol.17, issue.0, pp.449-467, 1965.
DOI : 10.4153/CJM-1965-045-4

D. Beauquier, M. Nivat, E. Rémila, and M. Robson, Tiling figures of the plane with two bars, Computational Geometry, vol.5, issue.1, pp.1-25, 1995.
DOI : 10.1016/0925-7721(94)00015-N