On the parameterized complexity of the repetition free longest common subsequence problem

被引：12

作者：

Blin, Guillaume ^{[2
]}

Bonizzoni, Paola ^{[3
]}

Dondi, Riccardo ^{[1
]}

Sikora, Florian ^{[2
,4
]}

机构：

[1] Univ Bergamo, Dipartimento Sci Linguaggi Comunicaz & Culturali, I-24129 Bergamo, Italy

[2] Univ Paris Est, LIGM UMR CNRS 8049, Paris, France

[3] Univ Milano Bicocca, DISCo, Milan, Italy

[4] Univ Jena, Lehrstuhl Bioinformat, D-6900 Jena, Germany

来源：

INFORMATION PROCESSING LETTERS | 2012年 / 112卷 / 07期

关键词：

Algorithms; Combinatorial problems; Repetition free longest common subsequence; Longest common subsequence; Parameterized complexity;

D O I：

10.1016/j.ipl.2011.12.009

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Longest common subsequence is a widely used measure to compare strings, in particular in computational biology. Recently, several variants of the longest common subsequence have been introduced to tackle the comparison of genomes. In particular, the Repetition Free Longest Common Subsequence (RFLCS) problem is a variant of the LCS problem that asks for a longest common subsequence of two input strings with no repetition of symbols. In this paper, we investigate the parameterized complexity of RFLCS. First, we show that the problem does not admit a polynomial kernel. Then, we present a randomized FPT algorithm for the RFLCS problem, improving the time complexity of the existent FPT algorithm. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：272 / 276

页数：5

共 18 条

[1] Repetition-free longest common subsequence [J].

Adi, Said S. ;

Braga, Marilia D. V. ;

Fernandes, Cristina G. ;

Ferreira, Carlos E. ;

Martinez, Fabio Viduani ;

Sagot, Marie-France ;

Stefanes, Marco A. ;

Tjandraatmadja, Christian ;

Wakabayashi, Yoshiko .

DISCRETE APPLIED MATHEMATICS, 2010, 158 (12) :1315-1324

[2] A survey of longest common subsequence algorithms [J].

Bergroth, L ;

Hakonen, H ;

Raita, T .

SPIRE 2000: SEVENTH INTERNATIONAL SYMPOSIUM ON STRING PROCESSING AND INFORMATION RETRIEVAL - PROCEEDINGS, 2000, :39-48

[3]

Bodlaender HL, 2009, LECT NOTES COMPUT SC, V5757, P635, DOI 10.1007/978-3-642-04128-0_57

[4] On problems without polynomial kernels [J].

Bodlaender, Hans L. ;

Downey, Rodney G. ;

Fellows, Michael R. ;

Hermelin, Danny .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2009, 75 (08) :423-434

[5] Exemplar longest common subsequence [J].

Bonizzoni, Paola ;

Della Vedova, Gianluca ;

Dondi, Riccardo ;

Fertin, Guillaume ;

Rizzi, Raffaella ;

Vialette, Stephane .

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 2007, 4 (04) :535-543

[6] Variants of constrained longest common subsequence [J].

Bonizzoni, Paola ;

Della Vedova, Gianluca ;

Dondi, Riccardo ;

Pirola, Yuri .

INFORMATION PROCESSING LETTERS, 2010, 110 (20) :877-881

[7] A simple algorithm for the constrained sequence problems [J].

Chin, FYL ;

De Santis, A ;

Ferrara, AL ;

Ho, NL ;

Kim, SK .

INFORMATION PROCESSING LETTERS, 2004, 90 (04) :175-179

[8]

Downey R. G., 1999, MG COMP SCI

[9] Infeasibility of instance compression and succinct PCPs for NP [J].

Fortnow, Lance ;

Santhanam, Rahul .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2011, 77 (01) :91-106

[10]

Fu B, 2011, LECT N BIOINFORMAT, V6674, P297, DOI 10.1007/978-3-642-21260-4_29

← 1 2 →