DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2017.14

The Longest Filled Common Subsequence Problem

Authors: Mauro Castelli, Riccardo Dondi, Giancarlo Mauri, and Italo Zoppis

Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)

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.

Cite as

Mauro Castelli, Riccardo Dondi, Giancarlo Mauri, and Italo Zoppis. The Longest Filled Common Subsequence Problem. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{castelli_et_al:LIPIcs.CPM.2017.14,
  author =	{Castelli, Mauro and Dondi, Riccardo and Mauri, Giancarlo and Zoppis, Italo},
  title =	{{The Longest Filled Common Subsequence Problem}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{14:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.14},
  URN =		{urn:nbn:de:0030-drops-73293},
  doi =		{10.4230/LIPIcs.CPM.2017.14},
  annote =	{Keywords: longest common subsequence, approximation algorithms, computational complexity, fixed-parameter algorithms}
}

Search Results

Documents authored by Mauri, Giancarlo

The Longest Filled Common Subsequence Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message