Longest Common Subsequence Problem for Unoriented and Cyclic Strings

François Nicolas 1 Eric Rivals 1
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Given a finite set of strings X, the Longest Common Subsequence problem (LCS) consists in finding a subsequence common to all strings in X that is of maximal length. LCS is a central problem in stringology and finds broad applications in text compression, conception of error-detecting codes, or biological sequence comparison. However, in numerous contexts words represent cyclic or unoriented sequences of symbols and LCS must be generalized to consider both orientations and/or all cyclic shifts of the strings involved. This occurs especially in computational biology when genetic material is sequenced from circular DNA or RNA molecules. In this work, we define three variants of LCS when the input words are unoriented and/or cyclic. We show that these problems are NP-hard, and W[1]-hard if parameterized in the number of input strings. Both results still hold even if the three LCS variants are restricted to input languages over a binary alphabet. We also settle the parameterized complexity of our problems for most relevant parameters. Moreover, we study the approximability of these problems: we discuss the existence of approximation bounds depending on the cardinality of the alphabet, on the length of the shortest sequence, and on the number of input sequences. For this we prove that Maximum Independent Set in r-uniform hypergraphs is W[1]-hard if parameterized in the cardinality of the sought independent set and at least as hard to approximate as Maximum Independent Set in graphs.
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00120152
Contributeur : Eric Rivals <>
Soumis le : mercredi 13 décembre 2006 - 14:33:38
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mardi 6 avril 2010 - 19:23:21

Identifiants

Collections

Citation

François Nicolas, Eric Rivals. Longest Common Subsequence Problem for Unoriented and Cyclic Strings. Theoretical Computer Science, Elsevier, 2007, 370 (1-3), pp.1-18. 〈http://dx.doi.org/10.1016/j.tcs.2006.10.002〉. 〈10.1016/j.tcs.2006.10.002〉. 〈lirmm-00120152〉

Partager

Métriques

Consultations de la notice

219

Téléchargements de fichiers

129