. Hence, Theorem 18-(i) (applied with r := 3) ensures that LCCS D and LCUCS D are W[1]-hard for parameter k

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

M. D. Adams, J. M. Kelley, J. D. Gocayne, M. Dubnick, M. H. Polymeropoulos et al., Complementary DNA sequencing: expressed sequence tags and human genome project, Science, vol.42, issue.1, pp.1651-1656, 1991.
DOI : 10.1016/S0092-8674(85)80099-4

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

G. Peris and A. , Fast cyclic edit distance computation with weighted edit costs in classification, Object recognition supported by user interaction for service robots, pp.184-187, 2002.
DOI : 10.1109/ICPR.2002.1047428

A. Marzal and G. Peris, Normalized Cyclic Edit Distances: An Efficient Algorithm, Proceedings of the 10th Conferencia de la Asociación Española Para la Inteligencia Artificial (CAEPIA'03), pp.435-444, 2004.
DOI : 10.1007/978-3-540-25945-9_43

D. S. Hirschberg, Algorithms for the Longest Common Subsequence Problem, Journal of the ACM, vol.24, issue.4, pp.664-675, 1977.
DOI : 10.1145/322033.322044

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

E. W. Myers, AnO(ND) difference algorithm and its variations, Algorithmica, vol.21, issue.1, pp.251-266, 1986.
DOI : 10.1007/BF01840446

M. Crochemore, G. M. Landau, and M. , A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices, SIAM Journal on Computing, vol.32, issue.6, pp.1654-1673, 2003.
DOI : 10.1137/S0097539702402007
URL : https://hal.archives-ouvertes.fr/hal-00619573

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

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

G. M. Landau, E. W. Myers, and J. P. Schmidt, Incremental String Comparison, Incremental string comparison, pp.557-582, 1998.
DOI : 10.1137/S0097539794264810
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.1766

S. Y. Itoga, The string merging problem, BIT, vol.23, issue.1, pp.20-30, 1981.
DOI : 10.1007/BF01934067

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

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

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

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, pp.1-2, 1995.

K. Räihä and E. Ukkonen, The shortest common supersequence problem over binary alphabet is NP-complete, Theoretical Computer Science, vol.16, issue.2, pp.187-198, 1981.
DOI : 10.1016/0304-3975(81)90075-X

V. G. Timkovskii, Complexity of common subsequence and supersequence problems and related problems, Cybernetics, vol.2, issue.No. 1, pp.565-580, 1990.
DOI : 10.1007/BF01075212

M. Middendorf, More on the complexity of common superstring and supersequence problems, Theoretical Computer Science, vol.125, issue.2, pp.205-228, 1994.
DOI : 10.1016/0304-3975(92)00074-2

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

M. M. Halldòrsson, Approximations of Weighted Independent Set and Hereditary Subset Problems, Journal of Graph Algorithms and Applications, vol.4, issue.1, pp.1-16, 2000.
DOI : 10.7155/jgaa.00020

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

J. Håstad, Clique is hard to approximate within n1?????, Acta Mathematica, vol.182, issue.1, pp.105-142, 1999.
DOI : 10.1007/BF02392825

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
DOI : 10.1016/S0304-3975(02)00535-2

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