License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2020.9
URN: urn:nbn:de:0030-drops-121344
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12134/
Go to the corresponding LIPIcs Volume Portal

Charalampopoulos, Panagiotis ; Kociumaka, Tomasz ; Mozes, Shay

Dynamic String Alignment

pdf-format:
LIPIcs-CPM-2020-9.pdf (0.5 MB)

Abstract

We consider the problem of dynamically maintaining an optimal alignment of two strings, each of length at most n, as they undergo insertions, deletions, and substitutions of letters. The string alignment problem generalizes the longest common subsequence (LCS) problem and the edit distance problem (also with non-unit costs, as long as insertions and deletions cost the same). The conditional lower bound of Backurs and Indyk [J. Comput. 2018] for computing the LCS in the static case implies that strongly sublinear update time for the dynamic string alignment problem would refute the Strong Exponential Time Hypothesis. We essentially match this lower bound when the alignment weights are constants, by showing how to process each update in ?̃(n) time. When the weights are integers bounded in absolute value by some w=n^{?(1)}, we can maintain the alignment in ?̃(n ⋅ min {√ n,w}) time per update. For the ?̃(nw)-time algorithm, we heavily rely on Tiskin’s work on semi-local LCS, and in particular, in an implicit way, on his algorithm for computing the (min,+)-product of two simple unit-Monge matrices [Algorithmica 2015]. As for the ?̃(n√n)-time algorithm, we employ efficient data structures for computing distances in planar graphs.

BibTeX - Entry

@InProceedings{charalampopoulos_et_al:LIPIcs:2020:12134,
  author =	{Panagiotis Charalampopoulos and Tomasz Kociumaka and Shay Mozes},
  title =	{{Dynamic String Alignment}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{9:1--9:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-149-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{161},
  editor =	{Inge Li G{\o}rtz and Oren Weimann},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12134},
  URN =		{urn:nbn:de:0030-drops-121344},
  doi =		{10.4230/LIPIcs.CPM.2020.9},
  annote =	{Keywords: string alignment, edit distance, longest common subsequence, (unit-)Monge matrices, (min,+)-product}
}

Keywords: string alignment, edit distance, longest common subsequence, (unit-)Monge matrices, (min,+)-product
Collection: 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
Issue Date: 2020
Date of publication: 09.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI