Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00120152
Contributor : Eric Rivals <>
Submitted on : Wednesday, December 13, 2006 - 2:33:38 PM
Last modification on : Friday, January 8, 2021 - 11:22:05 AM
Long-term archiving on: : Tuesday, April 6, 2010 - 7:23:21 PM

Identifiers

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. ⟨10.1016/j.tcs.2006.10.002⟩. ⟨lirmm-00120152⟩

Share

Metrics

Record views

905

Files downloads

318