DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2025.13

Doubly-Periodic String Comparison

Authors: Nikita Gaevoy, Boris Zolotov, and Alexander Tiskin

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract

The longest common subsequence (LCS) problem is a fundamental algorithmic problem. Given a pair of strings, the problem asks for the length of the longest string that is a subsequence in both input strings. Among the many relatives of this problem, there is its natural version where one or both of input strings have periodic structure. The case where only one of the input strings is periodic has been considered before; in this work, we develop an efficient algorithm for the more difficult case where both input strings are periodic. The algorithm is based on the existing algebraic framework for the LCS problem, developed by the third author; in particular, we extend this framework to dealing with affine (i.e. doubly-infinite periodic) permutations instead of finite ones. Given input strings that are a k-repeat of a period of length m and an 𝓁-repeat of a period of length n, the resulting algorithm runs in time O(mn+n log n log k), which is a substantial improvement over existing approaches. The algorithm has been implemented by the first author; by running his code, one can process pairs of periodic input strings with lengths far beyond the reach of all known alternative algorithms.

Cite as

Nikita Gaevoy, Boris Zolotov, and Alexander Tiskin. Doubly-Periodic String Comparison. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gaevoy_et_al:LIPIcs.CPM.2025.13,
  author =	{Gaevoy, Nikita and Zolotov, Boris and Tiskin, Alexander},
  title =	{{Doubly-Periodic String Comparison}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.13},
  URN =		{urn:nbn:de:0030-drops-231079},
  doi =		{10.4230/LIPIcs.CPM.2025.13},
  annote =	{Keywords: String Comparison, periodic Strings, Longest common Subsequence, affine Hecke Monoid, affine sticky Braids}
}

Document

DOI: 10.4230/LIPIcs.ESA.2022.86

Fast RSK Correspondence by Doubling Search

Authors: Alexander Tiskin

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract

The Robinson-Schensted-Knuth (RSK) correspondence is a fundamental concept in combinatorics and representation theory. It is defined as a certain bijection between permutations and pairs of Young tableaux of a given order. We consider the RSK correspondence as an algorithmic problem, along with the closely related k-chain problem. We give a simple, direct description of the symmetric RSK algorithm, which is implied by the k-chain algorithms of Viennot and of Felsner and Wernisch. We also show how the doubling search of Bentley and Yao can be used as a subroutine by the symmetric RSK algorithm, replacing the default binary search. Surprisingly, such a straightforward replacement improves the asymptotic worst-case running time for the RSK correspondence that has been best known since 1998. A similar improvement also holds for the average running time of RSK on uniformly random permutations.

Cite as

Alexander Tiskin. Fast RSK Correspondence by Doubling Search. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 86:1-86:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{tiskin:LIPIcs.ESA.2022.86,
  author =	{Tiskin, Alexander},
  title =	{{Fast RSK Correspondence by Doubling Search}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{86:1--86:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.86},
  URN =		{urn:nbn:de:0030-drops-170249},
  doi =		{10.4230/LIPIcs.ESA.2022.86},
  annote =	{Keywords: combinatorics of permutations, Robinson-Schensted-Knuth correspondence, k-chains, RSK algorithm}
}

Document

DOI: 10.4230/LIPIcs.WABI.2019.16

Bounded-Length Smith-Waterman Alignment

Authors: Alexander Tiskin

Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)

Abstract

Given a fixed alignment scoring scheme, the bounded length (respectively, bounded total length) Smith-Waterman alignment problem on a pair of strings of lengths m, n, asks for the maximum alignment score across all substring pairs, such that the first substring’s length (respectively, the sum of the two substrings' lengths) is above the given threshold w. The latter problem was introduced by Arslan and Eğecioğlu under the name "local alignment with length threshold". They proposed a dynamic programming algorithm solving the problem in time O(mn^2), and also an approximation algorithm running in time O(rmn), where r is a parameter controlling the accuracy of approximation. We show that both these problems can be solved exactly in time O(mn), assuming a rational scoring scheme; furthermore, this solution can be used to obtain an exact algorithm for the normalised bounded total length Smith - Waterman alignment problem, running in time O(mn log n). Our algorithms rely on the techniques of fast window-substring alignment and implicit unit-Monge matrix searching, developed previously by the author and others.

Cite as

Alexander Tiskin. Bounded-Length Smith-Waterman Alignment. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{tiskin:LIPIcs.WABI.2019.16,
  author =	{Tiskin, Alexander},
  title =	{{Bounded-Length Smith-Waterman Alignment}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{16:1--16:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-123-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{143},
  editor =	{Huber, Katharina T. and Gusfield, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.16},
  URN =		{urn:nbn:de:0030-drops-110461},
  doi =		{10.4230/LIPIcs.WABI.2019.16},
  annote =	{Keywords: sequence alignment, local alignment, Smith, Waterman alignment, matrix searching}
}

Search Results

Documents authored by Tiskin, Alexander

Doubly-Periodic String Comparison

Abstract

Cite as

Fast RSK Correspondence by Doubling Search

Abstract

Cite as

Bounded-Length Smith-Waterman Alignment

Abstract

Cite as

Thanks for your feedback!

Could not send message