The longest filled common subsequence problem

Mauro Castelli, Riccardo Dondi, Giancarlo Mauri, Italo Zoppis

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Citations (Scopus)
12 Downloads (Pure)

Abstract

Inspired by a recent approach for genome reconstruction from incomplete data, we consider a variant of the longest common subsequence problem for the comparison of two sequences, one of which is incomplete, i.e. it has some missing elements. The new combinatorial problem, called Longest Filled Common Subsequence, given two sequences A and B, and a multiset M of symbols missing in B, asks for a sequence B obtained by inserting the symbols of M into B so that B induces a common subsequence with A of maximum length. First, we investigate the computational and approximation complexity of the problem and we show that it is NP-hard and APX-hard when A contains at most two occurrences of each symbol. Then, we give a 3/5-approximation algorithm for the problem. Finally, we present a fixed-parameter algorithm, when the problem is parameterized by the number of symbols inserted in B that "match" symbols of A.

Original languageEnglish
Title of host publication28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume78
ISBN (Electronic)9783959770392
DOIs
Publication statusPublished - 1 Jul 2017
Event28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017 - Warsaw, Poland
Duration: 4 Jul 20176 Jul 2017

Conference

Conference28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017
CountryPoland
CityWarsaw
Period4/07/176/07/17

Keywords

  • Approximation algorithms
  • Computational complexity
  • Fixed-parameter algorithms
  • Longest common subsequence

Fingerprint Dive into the research topics of 'The longest filled common subsequence problem'. Together they form a unique fingerprint.

Cite this