M. D. Adams, J. M. Kelley, J. D. Gocayne, M. Dubnick, M. H. Polymeropoulos et al., then return the set I of letters occurring in s, References 1 Complementary DNA sequencing: expressed sequence tags and human genome project, Science, vol.5, issue.5013, pp.2521651-1656, 1991.

H. L. Bodlaender, R. G. Downey, M. R. Fellows, M. T. Hallett, and H. T. Wareham, Parameterized complexity analysis in computational biology, Bioinformatics, vol.11, issue.1, pp.49-57, 1995.
DOI : 10.1093/bioinformatics/11.1.49

H. L. Bodlaender, R. G. Downey, M. R. Fellows, and H. T. Wareham, The parameterized complexity of sequence alignment and consensus, Theoretical Computer Science, vol.147, issue.1-2, pp.31-54, 1995.
DOI : 10.1016/0304-3975(94)00251-D

R. Boppana and M. M. Halldòrsson, Approximating maximum independent sets by excluding subgraphs, BIT, vol.30, issue.4, pp.180-196, 1992.
DOI : 10.1007/BF01994876

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

H. Bunke and U. Buehler, Applications of approximate string matching to 2D shape recognition, Pattern Recognition, vol.26, issue.12, pp.1797-1812, 1993.
DOI : 10.1016/0031-3203(93)90177-X

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2001.

M. Crochemore, G. M. Landau, and M. Ziv-ukelson, A sub-quadratic sequence alignment algorithm for unrestricted cost matrices, Proceedings of the 13th Annual ACM-SIAM Symposium On Discrete Mathematics, pp.679-688, 2002.
DOI : 10.1137/s0097539702402007

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

L. Engebretsen and J. Holmerin, Towards optimal lower bounds for clique and chromatic number, Theoretical Computer Science, vol.299, issue.1-3, pp.1-3, 2003.
DOI : 10.1016/S0304-3975(02)00535-2

URL : http://doi.org/10.1016/s0304-3975(02)00535-2

M. M. Halldòrsson, Approximations of weighted independent set and hereditary subset problems Clique is hard to approximate within n 1?, Journal of Graph Algorithms and Applications Acta Mathematica, vol.4, issue.182, pp.105-142, 1999.

T. Jiang and M. Li, On the Approximation of Shortest Common Supersequences and Longest Common Subsequences, SIAM Journal on Computing, vol.24, issue.5, pp.1122-1139, 1995.
DOI : 10.1137/S009753979223842X

M. Krivelevich and B. Sudakov, Approximate coloring of uniform hypergraphs, Journal of Algorithms, vol.49, issue.1, pp.2-12, 2003.
DOI : 10.1016/S0196-6774(03)00077-4

M. Maes, On a cyclic string-to-string correction problem, Information Processing Letters, vol.35, issue.2, pp.73-78, 1990.
DOI : 10.1016/0020-0190(90)90109-B

D. Maier, The Complexity of Some Problems on Subsequences and Supersequences, Journal of the ACM, vol.25, issue.2, pp.322-336, 1978.
DOI : 10.1145/322063.322075

W. J. Masek and M. S. Paterson, A faster algorithm computing string edit distances, Journal of Computer and System Sciences, vol.20, issue.1, pp.18-31, 1980.
DOI : 10.1016/0022-0000(80)90002-1

URL : http://doi.org/10.1016/0022-0000(80)90002-1

K. Pietrzak, On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems, Journal of Computer and System Sciences, vol.67, issue.4, pp.757-771, 2003.
DOI : 10.1016/S0022-0000(03)00078-3

D. Sankoff and J. B. , Time Warps, String Edits and Macromolecules: the Theory and Practice of Sequence Comparison, 1999.

J. P. Schmidt, All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings, SIAM Journal on Computing, vol.27, issue.4, pp.972-992, 1998.
DOI : 10.1137/S0097539795288489